首先要考虑的是，如果没有主件和附件的话，那题目将会非常的简单，那这就是最简单的01背包了，但是麻烦的是题目有主件和附件。那我们怎么办呢？不做了？开玩笑，既然你走了OI这条路，那就千万别回头！那我能不能用01背包来处理这个题目呢？当然是能的，注意题目中的这句话“每个主件可以有0个、1个或2个附件。附件不再有从属于自己的附件。”额，这个条件有什么用呢？当然有用啦，那么我就可以转化为01背包了，先只考虑主件，那就可以进行01背包了，然后对每个主件进行记录，每个主件拥有多少个附件，哪些附件，然后再进行动态规划就能解决了。
我把思路再整理一下，就是说先判断主件是否该买，如果它有一个附件的话，那么再考虑是否要购买这一个附件；如果有两个附件的话，那么就考虑是否购买第一个附件，第二个附件或者两个附件一起买（考虑他们的时候就一定要加上主件！）
代码如下，提交了两次，问题出在一个符号上：
#define max(a, b) ((a)>(b)?(a):(b))
struct thing{
int priece, cost;
struct {
int priece, cost;
}sub[2];
int len;
}buy[60];
int num[60];
int len;
int f[32001];
int main(void)
{
int m, n;
int i, j, k;
int a, b, c;
struct thing t;
scanf("%d%d", &m, &n);
for(i = 0; i < n; i++){
scanf("%d%d%d", &a, &b, &c);
if(c == 0){
num[len++] = i;
buy[i].priece = a b;
buy[i].cost = a;
}else{
t = &buy[c – 1];
t->sub[t->len].priece = a * b;
t->sub[t->len].cost = a;
t->len++;
}
}
for(i = 0; i < len; i++){
t = &buy[num[i]];
for(j = m; j >= t->cost; j–){
f[j] = max(f[j], f[j – t->cost] + t->priece);
for(k = 0; k < t->len; k++){
if(j – t->cost – t->sub[k].cost >= 0){
f[j] = max(f[j], f[j – t->cost – t->sub[k].cost] + t->priece + t->sub[k].priece);
}
}
if(t->len == 2 && (j – t->cost – t->sub[0].cost – t->sub[1].cost >= 0)){
f[j] = max(f[j], f[j – t->cost – t->sub[0].cost – t->sub[1].cost] + t->priece + t->sub[0].priece + t->sub[1].priece);
//把减法写成了加法,,
}
}
}
printf("%d\n", f[m]);
return 0;
}