问题 B: NASA的食物计划时间限制: 1 Sec 内存限制: 128 MB
提交: 8 解决: 8
[提交][状态][讨论版]题目描述 航天飞机的体积有限,当然如果载过重的物品,燃料会浪费很多钱,每件食品都有各自的体积、质量以及所含卡路里,在告诉你体积和质量的最大值的情况下,请输出能达到的食品方案所含卡路里的最大值,当然每个食品只能使用一次. 输入第一行两个数体积最大值(<400)和质量最大值(<400) 第二行 一个数 食品总数N(<50). 第三行－第3+N行 每行三个数 体积(<400) 质量(<400) 所含卡路里(<500) 输出样例输入320 3504160 40 12080 110 240220 70 31040 400 22 样例输出550 刚开始写成了这样，结果是错的 for(int i=1;i<=n;i++)
for(int j=t,k=w;j>=a[i]&&k>=b[i];j--,k--)
dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+c[i]);
改正：#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[400][400];
int a[55],b[55],c[55];
int t,w;
void Dp(int n){
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=t;j>=0;j--)
for(int k=w;k>=0;k--)
if(j>=a[i]&&k>=b[i]) dp[j][k]=max(dp[j][k],dp[j-a[i]][k-b[i]]+c[i]);
}
int main()
{
int n;
scanf("%d%d",&t,&w);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
Dp(n);
printf("%d\n",dp[t][w]);
return 0;
}
| 
转播
