题解 P1507 【NASA的食物计划】

龘龘龘龘龘龘 · 2017-08-05 11:01:45 · 题解

//这一题和01背包大径相同，只要考虑清楚其中的关系，直接就可以套用01背包中f[j]=max{f[j],f[j-a[i]]+c[i]然后因为有两个关键变量所以设一个二维数组f[j][l];然后f[l]也可以直接套用上面那个公式，只要稍微变动一下就行了，这就不说了；

鄙人是个新手昨晚8.00才正式学背包，代码有点不清楚的请多多包涵；

以下是代码，请各位笑纳：

#include<iostream>
using namespace std;
int a[51],b[51],c[51];//题目中有三个变量就设三个变量；
int f[501][501];
int main()
{
    int i,j,l,m,n,k;
    cin>>m>>n>>k;//输入
    for(i=1;i<=k;i++)
      cin>>a[i]>>b[i]>>c[i];//表示每个食品的体积质量和卡路里；
    for(i=1;i<=k;i++)
      for(j=m;j>=a[i];j--)
        for(l=n;l>=b[i];l--)//记住j和l不能同时写在一起，刚开始我就写在一起，调了1分钟才发现
          f[j][l]=max(f[j][l],f[j-a[i]][l-b[i]]+c[i]);//公式；直接套用就是的
      cout<<f[m][n];//输出最优解
      return 0;
}