题解 P1507 【NASA的食物计划】

· · 题解

像我这样的蒟蒻往这儿看！

这道题很简单，特别是题目最下方说明中点明这是一道背包题，更是削弱了这道题的难度。

好了言归正传，先定义dp[i][j][k]为取到第i个，花费j体积，k质量得到的最大卡路里。方程和二维的一样，只是多了一个质量。

当这个物品能取时，也就是j>=v[i]&&k>=w[i]时

f[i][j][k]=max(f[i-1][j][k],f[i-1][j-v[i]][k-w[i]]);

否则

f[i][j][k]=f[i-1][j][k];

否则的情况不加会出错，自己想想为什么。程序如下：

#include<bits/stdc++.h>
using namespace std;
int V,W,K,n,v[524],w[524],kl[524],dp[52][52][52];
int main()
{
    cin>>V>>W>>n;
    for(int i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&kl[i]);
    for(int i=1;i<=n;i++){
        for(int j=V;j>=0;j--){
            for(int k=W;k>=0;k--){
                if(j>=v[i]&&k>=w[i])
                    dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-v[i]][k-w[i]]+kl[i]);
                else dp[i][j][k]=dp[i-1][j][k];
            }
        }
    }
    cout<<dp[n][V][W];
    return 0;
}

好了，前面的就是用了三维的背包，本题数据较弱，n<50，不会爆空间，但是万一n<1000就凉凉了！于是我们就要思考如何优化空间。

其实和普通背包一样，只要反着推，就可以了。

方程就是：f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]); 程序如下：

#include<bits/stdc++.h>
using namespace std;
int V,W,K,n,v[524],w[524],kl[524],dp[524][524];
int main()
{
    cin>>V>>W>>n;
    for(int i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&kl[i]);
    for(int i=1;i<=n;i++){
        for(int j=V;j>=v[i];j--){
            for(int k=W;k>=w[i];k--){
                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-w[i]]+kl[i]);
            }
        }
    }
    cout<<dp[V][W];
    return 0;
}