hdu 2191 【背包问题】

时间:2021-08-20 08:58:02

题目

请输出能够购买大米的最多重量,注意是重量不是价值。

把每一种物品拧出来,用01背包解决。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int Max = 110;
int N,W,w[Max],v[Max],num[Max];
int f[Max]; int solve()
{
memset(f,0,sizeof(f));
for(int k=1;k<=N;k++)
{
for(int i=1;i<=num[k];i++)
{
for(int j=W;j>=v[k];j--)
f[j]=max(f[j],f[j-v[k]]+w[k]);
}
}
return f[W];
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>W>>N;
for(int i=1;i<=N;i++)
cin>>v[i]>>w[i]>>num[i];
cout<<solve()<<endl;
}
return 0;
}