使用动态规划示例解决 0/1 背包问题
陈莎拉
什么是背包问题？
此 背包问题 这是一个经典的组合优化问题。超市商店 n 包裹数（n ≤ 100）。包裹 i 包裹的重量 W[i] ≤ 100，价值 V[i] ≤ 100。窃贼携带的重量不能超过其最大携带量 M (M ≤ 100)。窃贼应该拿走哪些包裹才能使总价值最大化？
输入：
- 最大重量M和包裹数量n。
- 权重数组 W[i] 和相应的值 V[i]。
输出：
- 在产能范围内可获得的最大总价值。
- 小偷应该拿走的具体包裹种类。
背包算法分为两个众所周知的变体：
- 0/1 背包问题 采用动态规划法求解。每个包裹要么完整取走，要么全部留下——没有零碎部分，也没有重复包裹。
- 分数背包问题 可以通过贪婪策略解决。在这里，你可以从任何包裹中取出一部分来填满剩余容量。
如何使用动态规划解决背包问题（附示例）
分治法将一个大问题分解成若干子问题，然后不断分解，直到每个子问题都易于解决。然而，单纯的递归往往会多次解决同一个子问题，造成资源浪费。
背包动态规划的核心思想是将每个已解决的子问题存储在一个表中。重复调用时，只需读取答案而不是重新计算，从而将指数递归转化为多项式时间复杂度。
使用动态规划解决背包问题
要设计动态规划解决方案，您需要遵循以下四个步骤：
- 先解决最小的子问题。
- 推导出能够从较小问题构建较大问题答案的递归式。
- 将子问题的答案存储在一个表格中，该表格是使用递归式自下而上计算得出的。
- 根据完整表格得出最终答案。
分析 0/1 背包问题
最优值取决于两个独立因素：
- 目前还有多少个项目正在考虑中？
- 背包还能装下剩余的重量。
由于目标函数取决于两个量，因此选项表必须是二维的。 B[i][j] 表示在重量限制为 j 的包裹 {1, …, i} 中进行选择时的最大值。
- 最终答案是
B[n][M]容量为 M 的所有 n 个包中的最佳总值。 - 所选总重量始终受当前容量的限制：
B[i][j] ≤ j.
例如：如果 B[4][10] = 8，则容量为 10 的前四个包裹的最佳总重量为 8。这四个包裹中的一些可能会被跳过。
计算 B[i][j] 的公式
W[i],V[i]分别是包裹 i 的重量和价值，其中 i 在 {1, …, n} 中。M这是背包所能承载的最大重量。
基本情况（只有一个包裹）：对于每个容量 j ≥ W[1]：
B[1][j] = W[1]
一般情况下，决定是否将包裹 i 包含在容量 j 下：
- 如果包 i 是 跳过，B[i][j] 等于使用包 {1, …, i-1} 在容量 j 下的最佳值：
B[i][j] = B[i - 1][j]
- 如果包 i 是 拍摄 （仅当 W[i] ≤ j 时允许），B[i][j] 等于 V[i] 加上容量为 j – W[i] 的包 {1, …, i-1} 中的最佳值：
B[i][j] = V[i] + B[i - 1][j - W[i]]
选择体型较大的那个候选人。
动态规划基础
将这两个案例结合起来，即可得出完整的复发情况：
B[i][j] = max(B[i - 1][j], V[i] + B[i - 1][j - W[i]])
基本情况是 B[0][j] = 0 对于每个 j，因为无论容量如何，零个包裹都表示零值。
计算选项表
使用递归构建 B。一旦 B 被填充，同一个表将驱动 trac重建所选数据包的 e-back。表 B 有 n + 1 行和 M + 1 列：
- 第 0 行是基本情况，填充为零。
- 使用第 0 行计算第 1 行，使用第 1 行计算第 2 行，以此类推，直到第 n 行计算完成。
选项表
Trace
B完成后，重点关注 B[n][M]，所有 n 个容量为 M 的包裹的最优总价值。
- If B[n][M] = B[n-1][M]未选择包裹 n，因此继续 trac来自 B[n-1][M]。
- If B[n][M] ≠ B[n-1][M]已选择包裹 n，因此继续 trac来自 B[n-1][M – W[n]]。
重复此步骤，直到到达表格的第 0 行。
查找选项表以查找所选包的算法
注意：每当 B[i][j] = B[i-1][j]未选择软件包 i。值 B[n][M] 是背包中装载的最佳总价值。
步骤 trac正在选择套餐：
- 第三步： 从 i = n，j = M 开始。
- 第三步： 从下往上扫描第 j 列，直到找到满足 B[i][j] > B[i-1][j] 的行 i。将包 i 标记为已选中：
Select[i] = true. - 第三步： 更新 j = j – W[i]。如果 j > 0，则返回步骤 2，否则转到步骤 4。
- 第三步： 打印所有标记为已选的包裹。
Java Code
下列 Java 该方法自底向上填充 B[][]，打印表格以供检查，然后 trac是所选套餐。
public void knapsackDyProg(int W[], int V[], int M, int n) { int B[][] = new int[n + 1][M + 1]; for (int i = 0; i <= n; i++) for (int j = 0; j <= M; j++) { B[i][j] = 0; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= M; j++) { B[i][j] = B[i - 1][j]; if ((j >= W[i - 1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) { B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1]; } System.out.print(B[i][j] + " "); } System.out.print("\n"); } System.out.println("Max Value:\t" + B[n][M]); System.out.println("Selected Packs: "); int j = M; while (n != 0) { if (B[n][j] != B[n - 1][j]) { System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]); j = j - W[n - 1]; } n--; } }
函数 knapsackDyProg() 在 Java
代码说明：
- 分配表
B[][]并将每个单元格初始化为 0。 - 使用上一节中的递归公式，自底向上填充 B[][]。
- 每个单元格以“跳过包 i”值开头
B[i-1][j]. - 如果选择包裹 i 可行且能获得更优的价值，则覆盖该单元格。
- Trac将选定的项目从第 n 行返回到第 0 行。
- 每当选择包装 n 时，剩余容量减去
W[n-1].
修复说明： 原始代码片段的变异参数 M 一边读一边 B[n][M]上面更安全的版本使用了单独的光标。 j 等加工。为 trace.
此 Java 驱动程序使用两个已完成的示例运行该算法：
public void run() { // First Example // int W[] = new int[]{3, 4, 5, 9, 4}; // int V[] = new int[]{3, 4, 4, 10, 4}; // int M = 11; // Second Example int W[] = new int[]{12, 2, 1, 1, 4}; int V[] = new int[]{4, 2, 1, 2, 10}; int M = 15; int n = V.length; knapsackDyProg(W, V, M, n); }
第一个示例的输出结果：
0 0 0 3 3 3 3 3 3 3 3 3 0 0 0 3 4 4 4 7 7 7 7 7 0 0 0 3 4 4 4 7 7 8 8 8 0 0 0 3 4 4 4 7 7 10 10 10 0 0 0 3 4 4 4 7 8 10 10 11 Max Value: 11 Selected Packs: Package 5 with W = 4 and Value = 4 Package 2 with W = 4 and Value = 4 Package 1 with W = 3 and Value = 3
第二个示例的输出结果：
0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15 Max Value: 15 Selected Packs: Package 5 with W = 4 and Value = 10 Package 4 with W = 1 and Value = 2 Package 3 with W = 1 and Value = 1 Package 2 with W = 2 and Value = 2
0/1 背包问题的时间和空间复杂度
- 时间复杂度： O(n · M) — 两个嵌套循环在 M+1 个容量状态下扫描 n 个项目。
- 空间复杂度： 完整表格的时间复杂度为 O(n · M)，通过 kee 可简化为 O(M)。ping 仅上一行 trac无需电子退货。
运行时是 伪多项式：M 的值是多项式的，但编码 M 所用的比特数是指数的。这就是为什么即使动态规划在实践中很高效，0/1 背包问题仍然是 NP 难问题的原因。
0/1背包问题的应用
- 在重量限制范围内进行货物装载、集装箱包装和仓库拣货。
- 在具有固定成本和预期回报的投资项目中分配预算。
- 制造业中无法分割单个零件的裁料问题。
- 基于背包难题的密码学方案，例如 Merkle-Hellman 方案。
- 云计算中的资源受限调度和 CPU 任务放置。
- 在特征预算固定的情况下，机器学习中的特征选择。
