背包问题之0-1背包，多重背包，完全背包简单模板（个人笔记，可能有误）

 1 /*
 2     背包问题简单的三类 0-1背包 多重背包 完全背包板子 
 3 */
 4 
 5 /*
 6     0-1背包 
 7 */ 
 8 //普通做法
 9 for(int i = 1; i <= n; i++){
10     for(int j = w[i]; j <= c; j++){
11         dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);        //前者为取 后者为不取 
12     }
13 } 
14 
15 //空间复杂度优化 
16 for(int i = 1; i <= n; i++){
17     for(int j = c; j >= w[i]; j--){                                 
18         dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
19     }
20 }
21 
22 /*
23     多重背包 多重背包的解题思路是将相同的物品i看做是独立的个体从而将问题转换至0-1背包 
24 */
25 //普通做法（待验证） 
26 for(int i = 1; i <= n; i++){
27     for(int k = 1; k <= num[i]; k++){
28         for(int j = w[i], j <= c; j++){
29             if(w[i]*k <= j){
30                 dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*w[i]] + k*v[i]);        //同理前者为取 后者为不取 
31             }
32         }
33     }
34 }
35 
36 //优化空间复杂度 （待验证） 
37 for(int i = 1; i <= n; i++){
38     for(int k = 1; k <= num[i]; k++){
39         for(int j = c; j >= w[i]; j--){
40             if(j >= k*w[i]){
41                 dp[j] = max(dp[j], dp[j-k*w[i]] + k*v[i]);                    //同理前者为取 后者为不取 
42             }
43         }
44     }
45 } 
46 
47 /*
48     完全背包 
49 */
50 //普通做法（待验证） 
51 for(int i = 1; i <= n; i++){
52     for(int k = 1; k <= c/w[i]; k++){
53         for(int j = w[i]; j <= c; j++){
54             if(k*w[i] <= j){
55                 dp[i][j] = max(dp[i-1][j], dp[i-1][j-k*w[i]] + k*v[i]);        //同理前者为取 后者为不取 
56             }
57         }
58     }
59 }
60 
61 //优化空间复杂度（待验证） 
62 for(int i = 1; i <= n; i++){
63     for(int k = 1; k <= c/w[i]; k++){
64         for(int j = c; j >= w[i]; j--){
65             if(j >= k*w[i]){
66                 dp[j] = max(dp[j], dp[j-k*w[i]] + k*v[i]);                    //同理前者为取 后者为不取
67             }
68         }
69     } 
70 } 
71 
72 //完全背包优化空间后更方便的写法
73 for(int i = 1; i <= n; i++){
74     for(int j = w[i]; j <= c; j++){
75         dp[j] = max(dp[j], dp[j-w[i]] + v[i]);        //当物品为无限时顺序取正好满足无限的特性 
76     }
77 }