P1507 NASA的食物计划

发布时间 2023-08-23 23:14:35作者: 失控D大白兔

有n种候选食物,且只有一样,分别给出对应食物的体积、质量、卡路里
飞船空间和载重都有限,分别为v和m,求能承载食物的最大卡路里

1. 动态规划

void maxval(int v,int m,vector<int>&weight,vector<int>&volume,vector<int>&w){ 
    int n = w.size();
    int dp[v+1][m+1];
    memset(dp,0,sizeof(dp));
    int res = 0;
    for(int i=0;i<n;i++)
        for(int j=v;j>=volume[i];j--)
            for(int k=m;k>=weight[i];k--){
                dp[j][k] = max(dp[j][k],dp[j-volume[i]][k-weight[i]]+w[i]);
                res = max(res,dp[j][k]);
            }
    cout<<res;
    return;
}