USACO Shopping Offers

USACO 上给出了两种模型，第一种是最短路，第二种是完全背包问题。其实他们的实质是一样。
个人认为完全背包更易于实现和调试，平均情况下效率更高。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #include <limits.h>
05
06 struct node
07 {
08     int add[5];
09     int p;
10 }offer[100+10] = {};
11 //also regard one item as an offer
12
13 int s,t;
14 int map[1000];  //code to index
15 int need[6];
16 int best[6][6][6][6][6];
17
18 void init()
19 {
20     scanf("%d",&s);
21     int i,j;
22     int cnt = 0;
23     int code,num,n;
24     for(i = 0;i < 1000;i ++)
25         map[i] = -1;
26     for(i = 0;i < s;i ++)
27     {
28         scanf("%d",&n);
29         for(j = 0;j < n;j ++)
30         {
31             scanf("%d%d",&code,&num);
32             if(map[code] == -1)
33                 map[code] = cnt ++;
34             offer[i].add[map[code]] = num;
35         }
36         scanf("%d",&offer[i].p);
37     }
38     scanf("%d",&t);
39     for(i = s;i < s + t;i ++)
40     {
41         scanf("%d%d%d",&code,&num,&offer[i].p);
42         if(map[code] == -1)
43             map[code] = cnt ++;
44         offer[i].add[map[code]] = 1;
45         need[map[code]] = num;
46     }
47 }
48
49 void solve()
50 {
51     int i,a,b,c,d,e;
52     for(a = 0;a < 6;a ++)
53     for(b = 0;b < 6;b ++)
54     for(c = 0;c < 6;c ++)
55     for(d = 0;d < 6;d ++)
56     for(e = 0;e < 6;e ++)
57         best[a][b][c][d][e] = INT_MAX;
58     best[0][0][0][0][0] = 0;
59
60     for(a = 0;a <= need[0];a ++)
61     {
62         for(b = 0;b <= need[1];b ++)
63         {
64             for(c = 0;c <= need[2];c ++)
65                 for(d = 0;d <= need[3];d ++)
66                     for (e = 0;e <= need[4];e ++)
67                     {
68                         for(i = 0;i < t + s;i ++)
69                         {
70                             if(a + offer[i].add[0] <= need[0] && b + offer[i].add[1] <= need[1] && c + offer[i].add[2] <= need[2] && d + offer[i].add[3] <= need[3] && e + offer[i].add[4] <= need[4])
71                                 if(best[a][b][c][d][e] < INT_MAX && best[a + offer[i].add[0]][b + offer[i].add[1]][c + offer[i].add[2]][d + offer[i].add[3]][e + offer[i].add[4]] > (best[a][b][c][d][e] + offer[i].p))
72                                 {
73                                     best[a + offer[i].add[0]][b + offer[i].add[1]][c + offer[i].add[2]][d + offer[i].add[3]][e + offer[i].add[4]] = best[a][b][c][d][e] + offer[i].p;
74                                 }
75                         }
76                     }
77         }
78     }
79     printf("%d\n",best[need[0]][need[1]][need[2]][need[3]][need[4]]);
80 }
81
82 int main()
83 {
84     freopen("shopping.in","r",stdin);
85     freopen("shopping.out","w",stdout);
86     init();
87     solve();
88     return 0;
89 }