【多重バックパック】HDOJ 2191
多重バックパックの特徴:
受け取る品物の数に制限があります.
テーマ:
cグループのデータを入力、総資産nとmグループの選択可能なものを入力、資産v[]、価値w[]、袋数num[]を入力.最大値を出力します.
受け取る品物の数に制限があります.
テーマ:
cグループのデータを入力、総資産nとmグループの選択可能なものを入力、資産v[]、価値w[]、袋数num[]を入力.最大値を出力します.
#include
using namespace std;
const int maxn=500;
int c;
int n,m;
int v[maxn],w[maxn],num[maxn];
int f[maxn];
int main()
{
while(scanf("%d",&c)!=EOF)
{
memset(v,0,sizeof(v));
memset(w,0,sizeof(w));
memset(num,0,sizeof(num));
while(c--)
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>v[i]>>w[i]>>num[i];
}
memset(f,0,sizeof(f));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=num[i];j++)
{
for(int k=n;k>=v[i];k--)
{
f[k]=max(f[k],f[k-v[i]]+w[i]);
}
}
}
cout<