金明的预算方案 解题报告

这题刚拿到手，不知道怎么做，后来看到了题目里说每个主件最多有0，1，2个附件，那也就是说对于每个主件及其附件而言，最多有如下几种情况：不买一件；只买主件；买主件及附件1；买主件及附件2；买主件及附件1，2都买。
这么就好DP了，代码如下：

C语言:

#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[32001];
int v[61], p[61];
int lenth[61];
int have[61][2];
char not[61];

int main(void)
{
 int i, j, k;
 int n, m;
 int a, b, c;
 scanf(%d%d, &n, &m);
 for(i = 1; i <= m; i++){
 scanf(%d%d%d, &a, &b, &c);
 v[i] = a;
 p[i] = a * b;
 if(c != 0){
 have[c][lenth[c]++] = i;
 not[i] = 1;
 }
 }
 for(i = 1; i <= m; i++){
 if(not[i]){
 continue;
 }
 for(j = n; j >= v[i]; j -= 10){
/* if(f[j] > f[j - v[i]] + p[i]){
 //这里必须不能是小于等于
 continue;
 }*/
 f[j] = max(f[j], f[j - v[i]] + p[i]);
 for(k = 0; k < lenth[i]; k++){
 if((j - v[have[i][k]] - v[i]) >= 0){
 //必须要是大于等于0 
 f[j] = max(f[j],
 f[j - v[have[i][k]] - v[i]] + p[i]
 + p[have[i][k]]);
 }
 }
 if((lenth[i] == 2) && ((j - v[i] - v[have[i][0]] - v[have[i][1]]) >= 0)){
 //必须要是大于等于0
 f[j] = max(f[j], f[j - v[i] - v[have[i][0]] - v[have[i][1]]] + p[i] + p[have[i][0]] + p[have[i][1]]);
 }
 }
 }
 printf(%d\\n, f[n]);
 return 0;
}