題目中附件不超過2個，因而主附件存在4種不同的存取情況，可以轉化為分組背包問題.[狀態]f[k][v]表示添加前k組物品，剩余空間為v時的最大值[方程]f[k][v] = max{f[k-1][v], f[k-1][v-c[i]]+w[i]}注意循環順序.(參見《背包九講》)需要注意的問題(2次WA):1.仔細讀題，確定編號對應的物品.2.注意到方程中的參數非負(背包類問題需注意).
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 using namespace std;
5 int c[65][4], w[65][4], f[32000], set[70] = {0};
6 int max(int a, int b){return a > b ? a : b;}
7 int main(){
8 int n, m, v, p, q, i, j, t = 0;
9 FILE *fout = fopen("budget.out", "w");
10 memset(c, -1, sizeof(c));
11 memset(w, -1, sizeof(w));
12 memset(f, 0, sizeof(f));
13 scanf("%d%d", &n, &m);
14 for (i = 0; i < m; i++){
15 scanf("%d%d%d", &v, &p, &q);
16 j = 0;
17 if (!q) {
18 c[++t][0] = v;
19 w[t][0] = v*p;
20 set[i+1] = t;
21 }
22 else{
23 q = set[q];
24 if (w[q][1] == -1){
25 //printf("dgfdgds\n");
26 c[q][1] = c[q][0] + v;
27 w[q][1] = w[q][0] + v*p;
28 }
29 else if (w[q][2] == -1){
30 c[q][2] = c[q][0] + v;
31 w[q][2] = w[q][0] + v*p;
32 c[q][3] = c[q][1] + v;
33 w[q][3] = w[q][1] + v*p;
34 }
35 }
36 }
37 for (i = 1; i <= t; i++)
38 for (v = n; v >= 0; v--)
39 for (j = 0; j < 4; j++)
40 if (c[i][j] != -1 && v-c[i][j] >= 0){
41 f[v] = max(f[v], f[v-c[i][j]]+w[i][j]);
42 }
43 printf("%d\n", f[n]);
44 }
45