問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1276思路:
典型的多重背包問題，參考背包九講，一次AC
深刻理解：01背包、完全背包、多重背包
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_VOLUMN 100001
5 #define MAX_N 11
6 #define max(a,b) ((a)>(b) ? (a) : (b))
7 int vol, n;
8 int cv[MAX_N], num[MAX_N], f[MAX_VOLUMN];
9
10 /* f[i][v] = max(f[i-1][v], f[i-1][v-cost[i]]+value[i]) */
11 void
12 ZeroOnePack(int cost, int value)
13 {
14 int v;
15 for(v=vol; v>=cost; v--)
16 f[v] = max(f[v], f[v-cost]+value);
17 }
18
19 /* f[i][v] = max(f[i-1][v], f[i][v-cost[i]]+value[i]) */
20 void
21 CompletePack(int cost, int value)
22 {
23 int v;
24 for(v=cost; v<=vol; v++)
25 f[v] = max(f[v], f[v-cost]+value);
26 }
27
28 void
29 MultiplePack(int cost, int value, int amount)
30 {
31 int k = 1;
32 if(cost*amount >= vol)
33 CompletePack(cost, value);
34 else {
35 while((amount-k) >= 0) {
36 ZeroOnePack(cost*k, value*k);
37 amount -= k;
38 k = k*2;
39 }
40 ZeroOnePack(cost*amount, value*amount);
41 }
42 }
43
44 void
45 dp()
46 {
47 int i;
48 for(i=1; i<=n; i++)
49 MultiplePack(cv[i], cv[i], num[i]);
50 }
51
52 int
53 main(int argc, char **argv)
54 {
55 int i;
56 while(scanf("%d %d", &vol, &n)!=EOF) {
57 memset(f, 0, sizeof(f));
58 for(i=1; i<=n; i++)
59 scanf("%d %d", num+i, cv+i);
60 dp();
61 printf("%d\n", f[vol]);
62 }
63 }