题解 P1507 【NASA的食物计划】

· · 题解

01背包+2个限定条件

这题是引导经典的01背包问题，只不过比01背包多了一组限定条件（体积和质量），卡路里就是背包中的价值。

我们先来看看背包模板：

   for (i=1;i<=m;i++)
    for (j=V;j>=v[i];j--)
      f[j]=max(f[j],f[j-v[i]]+c[i]);

将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[j]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[j-v[i]]再加上通过放入第i件物品获得的价值c[i]。

我们再来看看这题的代码：

#include <bits/stdc++.h>
using namespace std;
int f[1005][1005],w[10005],v[10005],c[10005];
int main()
{
   int n,m,i,j,k,V,W;
   cin>>V>>W;
   cin>>n;
   for (i=1;i<=n;i++)
   cin>>v[i]>>w[i]>>c[i];
   //memset(f,0,sizeof(f));
   for (i=1;i<=W;i++)
    for (j=V;j>=v[i];j--)
     for (k=W;k>=w[i];k--)   //这题需要多加一层循环，多加一维数组
      f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+c[i]);
      cout<<f[V][W];
return 0;
}

背包详解见Here

♥Find Your Joy♥