引用：
题解
分析
此题是01背包问题的变形。
物品的重要度乘以价格是背包问题中的价值，物品的价格是背包问题中的体积。
一、我们可以把如何在众多主件与附件之中选择购买的问题转变为看成购买的5种方案：
什么都不买
只买主件
买主件和附件1
买主件和附件2
买主件和两个附件。
二、有些主件有附件，而有些没有，这为我们思考带来了负担，我们完全可以假设任何主件都有两个附件，也就是说如果题目没有给出某个主件的附件的话，我们就假设这个主件的附件是存在的，且价格和重要度都等于0。
这个假设首先不会影响到程序的正确性，也不会增加多少运算时间，且这种假设使得我们想问题和写程序都变得简单多了。
三、题目中的价格都是10的这个条件，可以减少一些时间和空间的开销。
此题和01背包问题有2个主要的区别：
区别一：01背包问题对当前物品考虑的只有买和不买两种情况，而此题需要考虑上面所说的5种不同的购买方案。
区别二：01背包问题是用v[i]来保存第i个物品的价值，而此题需要用v[i]来保存第i个物品和它的两个附件的价值，此时我们需要二维数组来实现，物品体积w同样需要用二维数组来保存。
v[i][0]表示第i个物品的主件价值， v[i][1]表示第i个物品的第一个附件的价值，v[i][2]表示第i个物品的第二个附件的价值。w[i][0..2]表示同样的物品的体积。
f[i,j]表示给定i个物品和j的空间能够获得的最大价值总合。
则：
f[i,j]=max{f[i?1,j],
f[i?1,j?w[i,0]]+v[i,0],
f[i?1,j?w[i,0]w[i,1]]+v[i,0]+v[i,1],
f[i?1,j?w[i,0]?w[i,2]]+v[i,0]+v[i,2],
f[i?1,j?w[i,0]?w[i,1]?w[i,2]]+v[i,0]+v[i,1]+v[i,2]}
其实，此题还有一个关键点，就是输入数据的处理。
根据题目的意思，q是物品的编号，但是这个编号是在考虑附件时统计的编号，而我们认为附件和主件是一体的，因此附件编号因该和主件一致，所以我们需要对题目给出的编号进行转换。
当是主件的时候，编号直接进入累计，而是附件的时候，则需要对应到相应的主件之下。
//题解：
#include<iostream>
using namespace std;
//一维数组不超过 3000 0000
//!!!聪明把最多2件物品的重要度、价格都保存在主件上-这样看每个物品有3个
//v[4][0]-v[4][1]-v[4][2]表示第4件物品的主件价格-第4件物品第1件附件价格
//v-p都变成了二维 [61][3]
int n,m;//n是总的钱--相当于以前的c， 有m件物品---相当于n
int v[61][3];//第i件物品的价格：每个物品最多有2个附件下标全部从1开始
//每件物品的价格,v[i][0]表示主件编号i的价格
//v[i][1]表示主件编号i的附件1的价格
//v[i][2] 示主件编号i的附件2的价格
int p[61][3];//第i件物品中的重要度
//每件物品的重要度,p[i][0]表示主件编号i的重要度
//p[i][1]表示主件编号i的附件1的重要度 p[i][1]
//p[i][2] 表示主件编号i的附件2的重要度 p[i][2]
//f[i][j]=前i件物品总花费为j的选择物品的总和价值最大
/*f[i][j]=max{
f[i-1][j];//1、不背第i件物品
f[i-1][j-v[i][0]]+p[i][0]*v[i][0]; //2、只背主件
f[i-1][j-v[i][0]-v[i][1]]+p[i][0]*v[i][0]+p[i][1]*v[i][1] //3、背主件只要附件1
f[i-1][j-v[i][0]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2]//4、背主件只要附件2
f[i-1][j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2] +p[i][1]*v[i][1];//5、背主件加两个附件
} 1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
*/ int f[61*3][32000];//f[i][j]前i件物品总钱为j的价值和最大:61*3个附件
void read()
{ int i,j,a,b,c,num=0;//num计主件的个数
int map[61]={0};
cin>>n>>m;//读入总钱数和m件物品
n=n/10;//每件物品都是10的整数倍，可以优化程序
for(i=1;i<=m;i++)
{ cin>>a>>b>>c;//先用变量保存--判断好是主还是附近再赋值
if(c==0) //先填主件，c才是主件
{ num++;//！！计一共有多少个主件，附件都记在主件第二维下标[1][2]
v[num][0]=a/10;
p[num][0]=b;//i=4，是第4件其实不是的-因为前面的有可能是附件，而附件不记数
map[i]=num;//记下第i个物品的主件序号
continue;
}
//c是物品的序号是i，不是num，而本题所有的附件要放在num主件上
c=map[c];//i=2,c=1时 c=map[1]=1, i=3时，c=1 ,c=map[1]=1
//i=4,map[4]=2,i=5,map[5]=3
if(v[c][1]==0)//如果第c件物品的第1个附件还没有
{ v[c][1]=a/10; p[c][1]=b;
continue;
}
else { v[c][2]=a/10;p[c][2]=b;
}
}//填好 v,p两个数组
//用背包;--主件和附件最多只被1次-
for(i=1;i<=num;i++)//穷举所有的主件物品:
{
for(j=n;j>=0;j--) //j是总重量总价格n：！！这是修改j>=0因为j<v[i][0]也要算
{ //情况1：不选主件 :这里把j<v[i][0]的情况也要计算吧
f[i][j]=f[i-1][j];//这时候f[i][j]=f[i-1][j]这个要执行.
//情况2：只选主件
//背得动
if(j>=v[i][0]) //重要度*价格
f[i][j]=max(f[i][j],f[i-1][j-v[i][0]]+p[i][0]*v[i][0]);
//情况3：选主件和附件1
if(j>=v[i][0]+v[i][1])
f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][1]]+p[i][0]*v[i][0]+p[i][1]*v[i][1]);
//情况4：选主件和附件2
if(j>=v[i][0]+v[i][2])
f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2]);
//情况5：主件+2个附件
if(j>=v[i][0]+v[i][1]+v[i][2])
f[i][j]=max(f[i][j],f[i-1][j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]*v[i][0]+
p[i][1]*v[i][1]+p[i][2]*v[i][2]); // if(a[i]>x) x=a[i] x=max(x,a[i]);
} //end for j
}//end for i
cout<<f[num][n]*10;
}
int main()
{read();
return 0;
}