1. 01背包
例题 https://www.luogu.com.cn/problem/P2871
题意概要：有 n个物品和一个容量为 W的背包，每个物品有重量w和价值 v两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。
在上面的题目中，每个物体有两种状态，要么被选中，要么没选中，对应二进制的0和1 ，故称为01背包问题
思路
例题中已知条件有每个物体的重量w，价值v，以及背包的总容量W
- 设DP状态F[i][j]含义为在只能放前i个物体的时候，容量为j的背包所能达到的最大总价值
- 考虑状态转移。假设现在已经处理好前i-1个物体的状态，那么对于第i个物体，
- 当其不放入背包时，背包的剩余容量不变，背包的总价值也不变，故这时候的最大价值为F[i - 1][j]，
- 当其放入背包时，背包的剩余容量会减小w，背包的物品总价值会增大v，这时候的最大价值为F[i - 1][j - w] + v
- 状态转移方程
- 这里可以看到其实状态转移方程与 i 其实没有关系，故可以进行空间优化
- 状态转移方程
- 这个方程很重要
核心代码
// C++ Versionfor (int i = 1; i <= n; i++)for (int l = W; l >= w[i]; l--)f[l] = max(f[l], f[l - w[i]] + v[i]);
注意点：内循环的变量枚举顺序是从大往小， 小的会影响大的，所以从大的开始，避免影响
理解：比如说只有一个大小为2的物体，背包总容量为9
空间未优化
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();int[] W = new int[N];int[] D = new int[N];for (int i = 0; i < N; i++) {W[i] = scanner.nextInt();D[i] = scanner.nextInt();}int[][] dp = new int[N][M + 1];if (W[0] <= M) {dp[0][W[0]] = D[0];}for (int i = 1; i < N; i++) {for (int j = 0; j <= M; j++) {if (j - W[i] >= 0) {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - W[i]] + D[i]);} else {dp[i][j] = dp[i - 1][j];}}}int max = 0;for (int i = M; i >= 0; i--) {if (max < dp[N - 1][i]) {max = dp[N - 1][i];}}System.out.println(max);}
优化
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int M = scanner.nextInt(); int[] W = new int[N]; int[] D = new int[N]; for (int i = 0; i < N; i++) { W[i] = scanner.nextInt(); D[i] = scanner.nextInt(); } int[] dp = new int[M + 1]; for (int i = 0; i < N; i++) { for (int j = M; j >= 0; j--) { if (j - W[i] >= 0) { dp[j] = Math.max(dp[j], dp[j - W[i]] + D[i]); } } } int max = 0; for (int i = M; i >= 0; i--) { if (max < dp[i]) { max = dp[i]; } } System.out.println(max); }2. 完全背包
例题 https://www.luogu.com.cn/problem/P1616
题意概要：有 n种物品和一个容量为 W的背包，每个物品有重量w和价值 v两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量，每种物体的数量无限
完全背包是01背包的变形，区别在于完全背包能无限选取，而01背包只能选取一次
思路
与01背包类似
- 设DP状态F[i][j]含义为在只能放前 i 种物体的时候，容量为 j 的背包所能达到的最大总价值
- 状态转移方程：假设现在已经处理好前i-1种物体的状态，那么对于第i种物体，
- 第 i 种物体可以选取 0 或无限个，所以方程为
- 考虑优化，其实，对于 F[i][j] ，其实只要通过 F[i][j-w]转移就可以，所以方程为
- 理解：F[i][j-w]其实已经考虑到了F[i - 1][j - w]， F[i - 1][j - 2w]等，是一个局部的最优子结构，所以直接简化为上面那个公式
- 考虑和01背包一样的优化，得到状态转移方程
- 第 i 种物体可以选取 0 或无限个，所以方程为
核心代码
// C++ Version for (int i = 1; i <= n; i++) for (int l = w[i]; l <= W; l++) f[l] = max(f[l], f[l - w[i]] + v[i]);注意点：这里内循环的变量枚举顺序是从小到大，01背包注意点中有解释
例题代码
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); int m = scanner.nextInt(); long[] a = new long[m]; long[] b = new long[m]; for (int i = 0; i < m; i++) { a[i] = scanner.nextLong(); b[i] = scanner.nextLong(); } long[] dp = new long[t + 1]; for (int i = 0; i < m; i++) { for (int j = 0; j <= t; j++) { if (j - a[i] >= 0) { dp[j] = Math.max(dp[j], dp[(int) (j - a[i])] + b[i]); } } } long max = 0; for (int i = t; i >= 0; i--) { if (max < dp[i]) { max = dp[i]; } } System.out.println(max); }3. 多重背包
概要：有 n种物品和一个容量为 W的背包，每种物品有重量w和价值 v两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量，每种物体的数量为k[i]
多重背包是01背包的变形，区别在于每种物体最多能选取k[i]个
思路
与01背包类似
- 设DP状态F[i][j]含义为在只能放前 i 种物体的时候，容量为 j 的背包所能达到的最大总价值
- 状态转移方程：假设现在已经处理好前i-1种物体的状态，那么对于第i种物体，
- 第 i 种物体最多可以选取k[i]个，所以方程为
- 这个公式无法像完全背包一样优化，因为它是选取多个物体，无法保证 F[i][j-w] 恰好考虑到了 F[i][j] 的其他情况
- 二进制分组优化 ： 使用
A[i][j]表示第 i 种物体拆分出来的第 j 个物体，对于暴力搜索来说，之所以效率低是因为做了很多类似于A[i][1] + A[[i][2]和A[i][2] + A[i][3]的等效情况，所以令A[i][j]的含义为第 i 种物体拆分出来的2^j个物体捆绑在一起的大物体，最后若是不满足2的幂次方，增加一个物体补齐 - 例子：6 = 1 + 2 + 3， 8 = 1 + 2 + 4 + 1
- 这样划分之后可以表示出任意 小于 k[i] 个物体的情况
- 将上述的物体都拆分为该种形式，再使用01背包解决问题
- 第 i 种物体最多可以选取k[i]个，所以方程为
核心代码
// C++ Version 二进制分组代码 index = 0; for (int i = 1; i <= m; i++) { int c = 1, p, h, k; cin >> p >> h >> k; while (k - c > 0) { k -= c; list[++index].w = c * p; list[index].v = c * h; c *= 2; } list[++index].w = p * k; list[index].v = h * k; }4. 混合背包
概要：有 n种物品和一个容量为 W的背包，每种物品有重量w和价值 v两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量，每种物体有些可以取1次，有些取无限次，有些取k次
混合背包是混合了上面三种背包的情况，这需要将其合并就可以
- 核心代码
for (循环物品种类) { if (是 0 - 1 背包) 套用 0 - 1 背包代码; else if (是完全背包) 套用完全背包代码; else if (是多重背包) 套用多重背包代码; }
， 只能拿一次
5.二维费用背包
例题：https://www.luogu.com.cn/problem/P1855
- 题目概要：这道题是很明显的 0-1 背包问题，可是不同的是选一个物品会消耗两种价值（经费、时间）
思路
- 这是01背包的变形，区别在于一个物体消耗的是两种价值，所以我们只需要在一维的基础上再开一维来表示第二种价值就可
代码
// C++ Version for (int k = 1; k <= n; k++) { for (int i = m; i >= mi; i--) // 对经费进行一层枚举 for (int j = t; j >= ti; j--) // 对时间进行一层枚举 dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1); }6. 分组背包
例题：https://www.luogu.com.cn/problem/P1757
概要：所谓分组背包，就是将物品分组，每组的物品相互冲突，最多只能选一个物品放进去。
01背包是对全部物体中的每一件，要么取，要么不取，而分组背包是对全部组的每一组，要么取一件，要么不取，相当于对分组进行01背包，只是取的情况比较复杂
思路
使用
t[k][i]表示第 k 组的第 i 件物品的编号是多少，再用cnt[ki]表示第k组的物品有多少个核心代码
// C++ Version for (int k = 1; k <= ts; k++) // 循环每一组 for (int i = m; i >= 0; i--) // 循环背包容量 大到小 for (int j = 1; j <= cnt[k]; j++) // 循环该组的每一个物品 if (i >= w[t[k][j]]) dp[i] = max(dp[i], dp[i - w[t[k][j]]] + c[t[k][j]]); // 像0-1背包一样状态转移7. 依赖背包
例题：https://www.luogu.com.cn/problem/P1064
题目概要：这类题目就是如果选择第 i 件物品， 就要选择第 j 类物品，保证不会循环引用，一些题目会出现多叉树的引用形式。我们将不依赖于别的物品的物品称为主件，依赖于某主件的物品称为附件
思路
- 对于包含一个主件和若干个附件的集合来说，有以下的可能性：不选择，仅选择主件，选择主件和一个附件，选择一个主件和两个附件，将以上的所有可能的容量和价值转换成一件件物品，因为这些可能性中只能选择一种，所以可以将其看成分组背包
8. 泛化物品的背包
- 此类背包没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包问题容量为V的背包问题中，当分配给它的费用为 v[i] 时，能得到的机制就是 h(v[i]) 。这是，只需要将固定的价值换成函数的引用即可
9. 背包问题变种
9.1 输出方案
- 输出方案就是记录下来背包中的某一个状态是怎么推出来的
- 使用 g[i][v] 表示第 i 件物品占用空间为 v 的时候是否选择了此物体，然后在转移的时候记录是选用了哪一种策略
- 输出伪代码 ```java int v = V; // 记录当前的存储空间
// 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环 for (从最后一件循环至第一件) { if (g[i][v]) { 选了第 i 项物品; v -= 第 i 项物品的价值; } else 未选第 i 项物品; }
<a name="wHe6Q"></a>
### 9.2 求方案数
- 对于给定的一个背包容量，物品费用，其他关系等的问题，求装到一定容量的方案总数
- 这个问题就是将求最大值的问题换成了求和的问题
- 例如01背包问题的状态转移方程就变成了 
- 初始条件dp[0] = 1，即容量为0的时候也有一个方案，那就是什么都不装
<a name="uD7H5"></a>
### 9.3 求最优方案总数
- 求最优方案的总数，我们不仅要记录最大价值，还要记录最大价值时的方案数
- dp状态 f[i][j] 表示是只能放前 i 个物品的情况下，容量为 j 背包能正好装满的最大总价值
- dp状态 g[i][j] 表示是只能放前 i 个物品的情况下，容量为 j 背包能正好装满的方案数
- 转移方程
- 如果 f[i][j] = f[i - 1][j] 且 f[i][j] != f[i - 1][j - v] + w 说明我们此时不选择把物品放入背包更优，方案数由 g[i-1][j] 转移过来，
- 如果 f[i][j] = f[i - 1][j - v] + w 且 f[i][j] != f[i - 1][j] 说明我们此时选择把物品放入背包更优，方案数由 g[i-1][j - v] 转移过来，
- 如果 f[i][j] = f[i - 1][j - v] + w 且 f[i][j] = f[i - 1][j] 说明我们此时选择把物品放入背包或者不放入背包都能取得最优解，方案数由 g[i-1][j - v] 和 g[i-1][j] 转移过来。
- 初始条件
```c
memset(f, 0x3f3f, sizeof(f)); // 避免没有装满而进行了转移
f[0] = 0;
g[0] = 1; // 什么都不装是一种方案
核心代码
for (int i = 0; i < N; i++) { for (int j = V; j >= v[i]; j--) { int tmp = max(dp[j], dp[j - v[i]] + w[i]); int c = 0; if (tmp == dp[j]) c += cnt[j]; // 如果从dp[j]转移 if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]]; // 如果从dp[j-v[i]]转移 dp[j] = tmp; cnt[j] = c; } } int max = 0; // 寻找最优解 for (int i = 0; i <= V; i++) { max = max(max, dp[i]); } int res = 0; for (int i = 0; i <= V; i++) { if (dp[i] == max) { res += cnt[i]; // 求和最优解方案数 } }9.4 背包的第k优解
普通的01背包是要求最优解，求第k优解的时候，增加一维记录当前状态下的第k优解
- dp[i][j][k]：第 i 个物体，选择的物品的总体积为 j 时，能够得到的第 k 大的价值和
若有收获，就点个赞吧
0 人点赞
