1. 0 1 背包问题：
1 #pragma GCC optimize("Ofast") 2 #include <iostream> 3 #include <algorithm> 4 #define Maxsize 100 + 1 5 using namespace std; 6 typedef long long ll; 7 struct node{ 8 int v; 9 int w; 10 }; 11 node arr[Maxsize]; 12 ll dp[Maxsize][10000 + 1]; 13 int main(){ 14 ios :: sync_with_stdio(false); 15 cin.tie(0); cout.tie(0); 16 int n,capa; 17 cin >> n >> capa; 18 for(int i = 1; i <= n; i++) 19 cin >> arr[i].w >> arr[i].v; 20 21 for(int i = 1; i <= n; i++){ 22 for(int j = 1; j <= capa; j++){ 23 if(arr[i].w <= j)dp[i][j] = max(dp[i-1][j],dp[i-1][j-arr[i].w] + arr[i].v); 24 else dp[i][j] = dp[i-1][j]; 25 cout<<dp[i][j]<<" "; 26 } 27 cout<<endl; 28 } 29 cout<<dp[n][capa]; 30 return 0; 31 }
1 * Input: 2 * 3 6 3 * 2 5 4 * 3 8 5 * 4 9 6 * 7 * Path: 8 * 0 5 5 5 5 5 9 * 0 5 8 8 13 13 10 * 0 5 8 9 13 14 11 * 12 * Output: 13 * 14
*
* 从填写dp数组的顺序可以看出, 每一次新填写的数组单元 , 只会利用到其左上方的单元所保存的结果
* 转化到实际问题中理解就是 ： 当枚举到 前 i 个物品， 容量为 j 的状态时， 只会用到前 i - 1的状态和 前 j - wi 的状态
* 而不会再用到 i-2 、i-3 的状态了, 同理, 下一次枚举 i + 1 个物品时， 也不会再用 i - 1 状态的结果
* 也就是说，0 1 背包问题的每一个状态， 只与最近一次的外层循环的状态有关.
* 因此可以利用滚动数组优化空间复杂度
* 外层 for 循环 i 为 1 ~ n
* 内层 for 循环 j 为 V ~ 1
* 为什么 j 不是从 1 ～ V 呢 ？
* 假如 j 从 1 ～ V,举个例子：
* 我们先确定了 状态 dp[j-1] , 现在正在确定 dp[j]
* 我们在一维数组中，是写成 dp[i][j] = dp[i-1][j] 或 dp[i-1][j-wi] + vi
* 表示的是 ， dp[i][j] 是通过 前 i-1个物品的状态推导得到的
* 然而我们的 1维dp，会通过用 i 来覆盖 i-1状态, 假如正着遍历 j , 那么会首先将 [i-1][....] 的状态先覆盖成为 [i][...], 再用覆盖后的状态来得到 dp[i][j]
* 那么就会导致原本的 dp[i-1][j-wi] + vi 变成了 dp[i][j-wi] , 也就是通过 i 个物品， j-wi 个容量推导得到了 前 i 个物品， j 个容量的状态
* 这显然是错误的.
用滚动数组优化空间复杂度：
1 #pragma GCC optimize("Ofast") 2 #include <iostream> 3 using namespace std; 4 struct node{ 5 int w; 6 int v; 7 }; 8 node arr[101]; 9 int dp[1000]; 10 int main(){ 11 int n,V; 12 cin >> n >> V; 13 for(int i = 1; i <= n; i++) 14 cin >> arr[i].w >> arr[i].v; 15 16 for(int i = 1; i <= n; i++) 17 for(int j = V; j >= arr[i].w; j--) 18 dp[j] = max(dp[j],dp[j-arr[i].w] + arr[i].v); 19 return 0; 20 }
2. 完全背包问题：
考虑到在对 0 1 背包用滚动数组优化的时候，之所以要求容量 j 必须倒着遍历，就是为了保证在枚举状态 dp[i][j] 时所使用的状态是还没有被 dp[i][j-?] 覆盖的状态（也即dp[i-1][j-??]）
而完全背包恰好就要求每一个物品可以多次使用。 那么，在推导 dp[i][j] 时， 其最优解可能就是由 dp[i][j-??] 推导得到的。
所以，解完全背包问题，只需要将01背包的滚动数组优化的解法中j正着遍历就可以了。
1 完全背包 2 #pragma GCC optimize("Ofast") 3 #include <iostream> 4 using namespace std; 5 struct node{ 6 int w; 7 int v; 8 }; 9 node arr[100]; 10 int dp[10000]; // 不少于最大容量 11 int main(){ 12 int n,V; 13 cin >> n >> V; 14 for(int i = 1; i <= n; i++) 15 cin >> arr[i].w >> arr[i].v; 16 for(int i = 1; i <= n; i++) 17 for(int j = arr[i].w; j <= n; j++) 18 dp[j] = max(dp[j],dp[j-arr[i].w] + arr[i].v); 19 20 cout<<dp[V]; 21 return 0; 22 }
3.多重背包： 三种解法 , 单调队列的解法最优 ， 不过还没完全弄懂 ， 等以后弄懂了再写详细注释。现在先记模版。
1 /* 2 * 多重背包问题的三种解法 3 * 4 */ 5 #include <iostream> 6 #include <vector> 7 #include <queue> 8 #define Maxsize 100 9 using namespace std; 10 void solution1(){ // 最朴素、无优化 11 struct node{ 12 int w; 13 int v; 14 int num; 15 }; 16 int n,v; 17 node arr[Maxsize]; 18 int dp[Maxsize]; 19 cin >> n >> v; 20 for(int i = 1; i <= n; i++) 21 cin >> arr[i].w >> arr[i].v >> arr[i].num; 22 23 for(int i = 1; i <= n; i++){ 24 for(int j = 1; j <= arr[i].num; j++){ 25 for(int p = v; p >= j*arr[i].w; p--){ 26 dp[p] = max(dp[p],dp[p-j*arr[i].w]+j*arr[i].v); 27 } 28 } 29 } 30 31 // 状态转移方程 32 // dp[i][j] = max(dp[i-1][j-k*arr[i].w] + k*arr[i].v) { 其中 0 <= k <= arr[i].num 且 k*arr[i].w <= p } 33 cout<<dp[v]; 34 } 35 void solution2(){ // 二进制优化 36 struct node{ 37 int w; 38 int v; 39 }; 40 int n,v; 41 vector<node> vec; 42 int dp[Maxsize]; 43 cin >> n >> v; 44 int now_w,now_v,now_num; 45 for(int i = 0; i < n; i++){ 46 int base = 1; 47 cin >> now_w >> now_v >> now_num; 48 int sum = 0; 49 while(base * now_w <= v && sum + base <= now_num){ 50 node New; New.w = base * now_w; New.v = base * now_v; 51 vec.push_back(New); 52 sum += base; 53 base <<= 1; 54 } 55 if(sum != now_num && (now_num - sum)*now_w <= v){ 56 node New; New.w = (now_num - sum) * now_w; New.v = (now_num - sum) * now_v; 57 vec.push_back(New); 58 } 59 } 60 61 int s = (int)vec.size(); 62 for(int i = 0; i < s; i++){ // 注意从0开始读入 63 for(int j = v; j >= vec[i].w; j--){ 64 dp[j] = max(dp[j],dp[j-vec[i].w] + vec[i].v); 65 } 66 } 67 cout<<dp[v]; 68 // 状态转移方程 69 // dp[j] = max(dp[j],dp[j-k*arr[i].w] + k*arr[i].v) { 其中 0 <= k <= arr[i].num 且 k*arr[i].w <= p } 70 } 71 void solution3(){ 72 struct node{ 73 int f; 74 int id; 75 }; 76 int dp[20000]; 77 int n,v; 78 cin >> n >> v; 79 int now_w,now_v,now_num; 80 for(int i = 1; i <= n; i++){ // 枚举物品 81 cin >> now_w >> now_v >> now_num; 82 now_num = min(now_num,v/now_w); // 这个物品所能选择的数量 , 需满足不大于背包体积 , 这个 now_num 就是我们的区间大小 83 for(int j = 0; j < now_w; j++){ // 枚举当前余数 84 deque<node> dq; 85 // 由solution2 可以知道, dp[j] 的子问题只包含了 dp[j-k*arr[i].w] , 也就是说,它们是关于 arr[i].w 同余的 86 // 将各个状态按照对 w 取模所得余数进行分类 87 // 那么只有同一类的状态可以相互影响, 不同类的状态无法相互影响 88 for(int k = 0; k * now_w + j <= v; k++){ 89 node New; 90 New.f = dp[k*now_w+j] - k*now_v; 91 New.id = k; 92 while(not dq.empty() and dq.back().f < New.f) 93 dq.pop_back(); 94 95 dq.push_back(New); 96 dp[k*now_w+j] = dq.front().f + k*now_v; 97 if(not dq.empty() and New.id -dq.front().id == now_num) 98 dq.pop_front(); 99 } 100 } 101 } 102 cout<<dp[v]; 103 } 104 int main(){ 105 solution3(); 106 return 0; 107 }