妖人代号：122511851
背包问题
01背包
-
滚动数组
dp [j] ---> 表示背包容量为 j 时所能装下的物品的最大价值
初始化：将数组中的每个值都初始化为0（相当于还没取任何物品情况下的最大价值）
外层循环：遍历每个物品
内层循环：倒序遍历背包容量（不能小于当前物品的重量）
递推公式：dp [j] = max (dp [j] , dp[j - w[i]] + c[i] );
/* 核心代码 */ // w[]表示物品重量， c[]表示物品价值 // 初始化 for(int i = 0; i <= v; i++){dp[i] = 0; } // 状态转移 for(int i = 1; i <= n; i++){for(int j = v; j >= w[i]; j--){dp[j] = max(dp[j], dp[j - w[i]] + c[i]);} }我的理解：①选与不选的逻辑：如果当前正在选物品3，那么dp[j]表示的是选择或者不选物品3之后，dp[j]的最大值（也就是前三个物品选完之后，所可能达到的最大值），那么对于递推式中max函数里面的两个值，dp[j]表示不选择物品3，那么此时dp[j]就继承了上一轮的dp[j]（也就是上一层循环，选择物品2后的dp[j]，dp[j - w[i]] + c[i]表示选择物品3，那选择过程是什么呢？为了让选择完物品3之后，所选择的物品总重量为当前背包所允许的最大重量，所以就是在上一轮处理完物品2后，背包容量为j - w[i]的那个背包里面放入物品3。②那至于为什么必须要将背包容量进行倒序遍历呢？从上面的叙述中可以得知，选择物品3的时候，用到了上一轮的背包，而这个背包的容量一定小于当前的背包容量，这样一来，如果进行正序遍历，则会先将背包容量小的，待会要用到的上一轮的背包覆盖掉。那假如就是正序遍历了，即覆盖了，会出现什么结果呢？比如先处理了dp[5]，在处理dp[6]的时候，如果当前物品重量w[i]为1，就会用到dp[6-1]，也就是dp[5]，但是此时你会发现，在前面处理dp[5]的时候已经加上了当前物品的价值c[i]，就导致处理dp[6]的时候这个物品的价值会重复添加，那如果重复添加以后的结果比上一轮处理完之后的dp[6]大，就会影响结果。③为什么不能将外层循环和内层循环对调（也就是先遍历背包容量，再遍历物品）呢？不妨试一下，假设先容量后物品，如果此时对于容量选择正序遍历，那出现的问题和之前一样，会导致重复选择物品（覆盖上一轮的背包），如果对于容量选择倒序遍历，会出现状态割裂的情况，也就是需要用到的子状态还没有被处理过。
如果要求是在背包必须装满的情况下求最大价值，那一开始给dp数组除了dp[0]之外的元素都设置为负无穷大，dp[0] = 0，然后进行正常的状态转移，如果最后dp[v] < 0的话，说明没用能将背包装满的方法，这样为什么行呢，对于每个物品在不同容量的背包情况下进行选择时，如果能将当前背包装满才选择（第一次的合法选择为dp[j - w[i]] + c[i] = dp[0] +c[i] = c[i]，其他装不满的情况得到的结果还是负无穷大，所以这个装不满的物品就不会被选择。
-
二维dp数组
dp [i] [j] ---> 表示在前i个物品中选择若干物品，使得将其放入容量为j的背包以后，价值最大
初始化：将数组中的每个值都初始化为0（相当于还没取任何物品情况下的最大价值）
外层循环：遍历每个物品
内层循环：正序遍历背包容量（从大于等于当前物品的重量开始）
递推公式：d [i] [j] = max (d [i-1] [j] , d[i-1] [j - w[i]] + c[i] );
/* 核心代码 */ // 初始化：将dp数组全部初始化为0 // 状态转移 for(int i = 1; i <= n; i++){ // 先物品后容量，且容量正序遍历for(int j = w[i]; j <= v; j++){dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);} } for(int i = 1; i <= n; i++){ // 先物品后容量，且容量倒序遍历for(int j = v; j >= w[i]; j--){dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);} } for(int j = 1; j <= v; j++){ // 先容量后物品，且容量正序遍历（只能正序）for(int i = 1; i <= n; i++){if(j < w[i]) dp[i][j] = dp[i - 1][j]; // 这种情况下，必须要有这行判断代码else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]);} }我的理解：①选与不选的逻辑和上面一样。②对于容量的遍历顺序以及内外层循环能否调换，我结合起来说明一下，可以先遍历物品后遍历容量，并且此时的容量遍历可以是正序的，也可以是倒序的；也可以先遍历容量后遍历物品，但此时容量的遍历只能是正序的，不能是倒序的。
完全背包（重点是一维数组）
/* 核心代码 */// 二维数组
for(int i = 1; i <= n; i++){for(int j = 1; j <= v; j++){if(j < w[i]) dp[i][j] = dp[i-1][j]; // 二维要有这一行，因为要用到本轮次的小容量背包else dp[i][j] = max(dp[i-1][j], dp[i][j - w[i]] + c[i]);}
}// 一维数组，先物品后容量
for(int i = 1; i <= n; i++){for(int j = w[i]; j <= v; j++){ // 只能正序遍历，保证每一个物品能被放入多次dp[j] = max(dp[j], dp[j - w[i]] + c[i]);}
}// 一维数组，先容量后物品
for(int j = 1; j <= v; j++){for(int i = 1; i <= n; i++){ if(j >= w[i]){d[j] = max(d[j], d[j - w[i]] + c[i]);}}
}
我的理解：①完全背包问题对于容量的遍历顺序只能是正序的（保证每个物品能被选择多次）；②对于先遍历物品还是先遍历容量，如果题目就是求解最大价值，那这两种遍历结果都正确，但如果题目要求解的是装满背包的方法数等等，那先遍历物品所得到的是组合数，而先遍历容量得到的是排列数。
多重背包
二进制拆分思想：比如说有 7 个物品 a，那如果选择物品 a的话，结果无非是选 1 个，选 2 个，……，选 7 个，所以想到将 7分成 1 2 4，这三个数任意组合可以得到1~7，所以也就是说，将 7 个 a，分成了三组可选择的不可拆分组合，即 1个a，2个a，4个a。如果不是7，是别的数量，那就按照这个逻辑分完之后，再处理剩下的。
处理逻辑：如果当前物品数量 * 物品重量 >= 背包容量，说明这个物品可以无限取，直接走完全背包；否则，对其进行二进制拆分，然后走01背包。
// 通用模板代码
#include <bits/stdc++.h>
using namespace std;int dp[2005];
int v; // 01背包核心单元
void ZeroOnePack(int weight, int value) {for (int j = v; j >= weight; j--) {dp[j] = max(dp[j], dp[j - weight] + value);}
}// 完全背包核心单元
void CompletePack(int weight, int value) {for (int j = weight; j <= v; j++) {dp[j] = max(dp[j], dp[j - weight] + value);}
}// 多重背包核心单元
void MultiplePack(int weight, int value, int num) {// 1. 如果数量 * 重量 >= 背包总容量，相当于这个物品可以无限取，直接走完全背包if (num * weight >= v) {CompletePack(weight, value);return;}// 2. 二进制拆分优化int k = 1;while (k < num) {ZeroOnePack(k * weight, k * value);num -= k;k *= 2;}// 处理剩下的余数部分if (num > 0) {ZeroOnePack(num * weight, num * value);}
}int main() {int n; cin >> n >> v;// 初始化for (int i = 0; i <= v; i++) dp[i] = 0;for (int i = 0; i < n; i++) {int w, c, s;cin >> w >> c >> s; // 重量, 价值, 数量MultiplePack(w, c, s);}cout << dp[v] << endl;return 0;
}
结束