金明的预算方案
显然是个背包问题
把每个主件和它对应的附件放在一组，枚举每一组，有以下几种选法：
1.都不选
2.只选主件
3.一个主件+一个附件
4.一个主件+两个附件
于是就成了01背包。。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,f[],v[][],w[][],pos[]; //pos[i]记录编号为i的物品在数组v,w中的下标
//w[i][0]表示第i个主件的附件个数
int main()
{
scanf("%d%d",&n,&m);
int V,P,Q,sum;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&V,&P,&Q);
if(Q==)
{
v[++sum][]=V;
w[sum][]=P;
pos[i]=sum;
}
else
{
w[pos[Q]][++w[pos[Q]][]+]=P;
v[pos[Q]][w[pos[Q]][]+]=V;
}
}
for(int i=;i<=sum;i++)
for(int j=n;j>=v[i][];j--)
{
f[j]=max(f[j],f[j-v[i][]]+w[i][]*v[i][]);
if(w[i][]>=&&j-v[i][]-v[i][]>=)
f[j]=max(f[j],f[j-v[i][]-v[i][]]+w[i][]*v[i][]+w[i][]*v[i][]);
if(w[i][]==&&j-v[i][]-v[i][]>=)
{
f[j]=max(f[j],f[j-v[i][]-v[i][]]+w[i][]*v[i][]+w[i][]*v[i][]);
if(j-v[i][]-v[i][]-v[i][]>=)
f[j]=max(f[j],f[j-v[i][]-v[i][]-v[i][]]+w[i][]*v[i][]+w[i][]*v[i][]+w[i][]*v[i][]);
}
}
printf("%d\n",f[n]);
return ;
}