```
//背包九讲P07
#include<iostream>
#include<cstdio>
using namespace std;
struct main_item{
int w1,c1,num;//附件数量
}mt[100];
struct annex_item{
int w2,c2;
}a[100][3];
int f[100][40000];//f[i][j]第i个物品组费用为j时最大价值
int opt[40000];//分组背包
int y[100];//每个物品组主件费用
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int v,p,q;
scanf("%d%d%d",&v,&p,&q);
if (q==0)
{
mt[i].w1=v;
mt[i].c1=v*p;
}
else
{
mt[q].num++;
a[q][mt[q].num].w2=v;
a[q][mt[q].num].c2=v*p;
}
}//附件集合归类
int r=0;//物品组数量
for (int e=1;e<=m;e++)
if (mt[e].w1!=0)
{
r++;
y[r]=mt[e].w1;//主件费用
for (int i=1;i<=mt[e].num;i++)
for (int j=n;j>=y[r];j--)
if (j-y[r]>=a[e][i].w2)
f[r][j]=max(f[r][j],f[r][j-a[e][i].w2]+a[e][i].c2);
for (int i=y[r];i<=n;i++)
f[r][i]+=mt[e].c1;
}
for (int i=1;i<=r;i++)
for (int j=n;j>=0;j--)
for (int k=y[i];k<=j;k++)
opt[j]=max(opt[j],opt[j-k]+f[i][k]);
cout<<opt[n]<<endl;
return 0;
}
```
by hatyt @ 2018-05-20 08:10:31
试一试卡时
by CTF无始道长 @ 2018-06-30 13:32:36
试试滚动数组？
by 四糸乃 @ 2018-07-06 09:32:32