题解 P1507 【NASA的食物计划】

zhz小蒟蒻 · 2018-08-04 16:01:37 · 题解

嗯，本蒟蒻也是在练习背包问题时找到了这题，做的过程中还辅助了书，好，切入正题
这道题其实一眼就可以看出，这只是在普通的01背包问题多加了一维,嗯，先呈上01背包问题公式——设f[i][j]为前i个物品中放入容量为j的背包的最优值，则状态转移方程为f[i][j]=max(f[i-1][j],f[i-1][j-w[i]+c[i])
注:w[i]为重量，c[i]为其代表的价值,整个方程的意思是,从前i-1个物品中放入容量为j的背包的最优值(不包括第i-1个物品)和前i-1个物品中放入第i-1个物品的最大值。
一般01背包代码:(不压缩成一维)

#include <iostream>//这是以采药为样例
#include <cstdio>
using namespace std;
int main()
{
    int f[1001][1001]={0};
    int a[101],b[101];  
    int i,j,k,n,m,t;
    cin>>t>>n;
    for(i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    for(i=1;i<=n;i++)
    {
        for(j=t;j>=0;j--)
        {
            if(j>=a[i]) f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i]);
            else f[i][j]=f[i-1][j];
        }
    }
    printf("%d",f[n][t]);
    return 0;
}

我们再来看到本题，因为这是二维的，所以我们设f[i][j][k]为前i个物品中放入体积为j，质量为k的背包的最优值,则只需将01背包的方程做稍微的修改
f[i][j][k]=max(f[i-1][j][k],f[i-1][j-w[i]][k-z[i]]+c[i]);
好了，看到这里，你应该会做了吧(当然，像本蒟蒻一样的人除外) 先去试着做一下，不会做，再来看代码:

#include <iostream>
#include <cstdio>
using namespace std;
int dp[51][401][401];  //因为我太弱了，不会节省空间
int main()
{
    int w[501],z[501],c[501];
    int i,j,k,n,u,v;
    scanf("%d %d %d",&u,&v,&n);
    for(i=1;i<=n;i++)
        scanf("%d %d %d",&w[i],&z[i],&c[i]);//w数组为体积，z数组为重量,c数组为卡路里
    for(i=1;i<=n;i++)
    {
        for(j=u;j>0;j--)
        {
            for(k=v;k>0;k--)
            {
                if(j>=w[i] && k>=z[i])  //如果j和k大于w[i]和z[i]，判断是前i-1个物品的最优值大，还是加上第i-1个数大
                    dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-z[i]]+c[i]);
                else  //如果小了，dp[i][j][k]等于前i-1个数的最优值
                    dp[i][j][k]=dp[i-1][j][k];
            }
        }
    }
    printf("%d",dp[n][u][v]); //这个绝对是最大值
    return 0;//一定要记得打return 0，这是个好习惯
}