使用动态规划示例解决 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 背包问题
当使用动态规划分析0/1背包问题时，你会发现一些值得注意的点。背包算法的价值取决于两个因素：
- 正在考虑多少包
- 背包所能储存的剩余重量。
因此，您有两个变量。
通过动态规划，您可以获得有用的信息：
- 目标函数将取决于两个变量
- 选项表将是一个二维表。
如果调用 B[i][j] 是通过在包 {1, 2, …, i} 中选择重量限制为 j 的最大可能值。
- 在n个限重M的包裹中选取最大值为B[n][M]。 也就是说：当有i个包裹可供选择时，B[i][j]就是背包最大重量为j时的最优重量。
- 最佳权重总是小于或等于最大权重：B[i][j] ≤ j。
例如：B[4][10] = 8。表示在最优情况下，选择的包裹总重量为8，当有4个第一包可供选择时（第1至第4包）和最大重量背包的数量是 10。没有必要选择所有 4 件物品。
计算 B[i][j] 的公式
输入，你定义：
- W[i]、V[i]依次为包裹i的重量和价值，其中i
![计算 B[i][j] 的公式](data:image/svg+xml,%3Csvg%20xmlns='http://www.w3.org/2000/svg'%20viewBox='0%200%2016%2023'%3E%3C/svg%3E)
{1, …, n}。 - M是背包可以携带的最大重量。
![计算 B[i][j] 的公式](https://www.guru99.com/images/1/043019_0611_KnapsackPro4.png){kind=small}
{1, …, n}。在只有 1 个包可供选择的情况下。 你对每一个j计算B[1][j]：这意味着背包的最大重量≥第一个包裹的重量
B[1][j] = W[1]
在重量限制为 j 的情况下，包裹 {1, 2, …, i – 1, i} 中具有最大值的最优选择将有两种可能性：
- 如果未选择包裹 i，则 B[i][j] 是在重量限制为 j 的包裹 {1, 2, …, i – 1} 中选择的最大可能值。 你有：
B[i][j] = B[i – 1][j]
- 如果选择包i（当然只考虑W[i]≤j的情况）那么B[i][j]等于包i的值V[i]加上最大值可以通过选择得到具有重量限制 (j – W[i]) 的包裹 {1, 2, …, i – 1}。 也就是说，就您拥有的价值而言：
B[i][j] = V[i] + B[i – 1][j – W[i]]
由于创建了最大可能值 B[i][j]，因此 B[i][j] 将是上述 2 个值中的最大值。
动态规划基础
因此，您必须考虑是否选择套餐 i 更好。 从那里你有递归公式如下：
B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]
通过从 0 package = 0 中选择，很容易看出 B[0][j] = 可能的最大值。
计算选项表
您根据上述递归公式构建一个选项表。 检查结果是否正确（如果不正确，则重建目标函数 B[i][j]）。 通过创建目标函数 B[i][j] 和选项表，您将确定跟踪的方向。
选项表 B 包括 n + 1 行，M + 1 列，
- 首先，填充动态规划的基础：第0行包括全零。
- 使用递归公式，使用第 0 行计算第 1 行，使用第 1 行计算第 2 行，等等……直到计算完所有行。
追踪
在计算选项表时，你感兴趣的是B[n][M]，它是在所有n个重量限制为M的包裹中选择时得到的最大值。
- If B[n][M] = B[n – 1][M] 那么包 n 没有被选中，你跟踪 B[n – 1][M]。
- If B[n][M] ≠ B[n – 1][M]，您注意到最优选择包含包 n 和迹线 B[n – 1][M – W[n]]。
继续追踪直到到达选项表的第 0 行。
查找选项表以查找所选包的算法
注意：如果 B[i][j] = B[i – 1][j]，则不选择包 i。 B[n][W]是放入背包的包裹的最优总价值。
追踪步骤：
- 第一步：从 i = n 开始，j = M。
- 第一步：查看第 j 列，从底部向上，您会找到满足 B[i][j] > B[i – 1][j] 的第 i 行。 标记选中的包 i: Select [i] = true;
- 第一步: j = B[i][j] – W[i]。 如果 j > 0，则转到第 2 步，否则转到第 4 步
- 第一步：根据选项表打印所选包。
Java 代码
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: ");
while (n != 0) {
if (B[n][M] != B[n - 1][M]) {
System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
M = M - W[n-1];
}
n--;
}
}
背包代码解释：
- 创建表 B[][]。 为每个单元格设置默认值是 0。
- 以自下而上的方式构建表 B[][]。 用检索公式计算选项表。
- 计算 B[i][j]。 如果不选择 package i。
- 然后评估：如果选择package i，比重新设置B[i][j]更有利。
- 跟踪表格从第 n 行到第 0 行。
- 如果你选择包n。 一旦选择包n，只能添加权重M – W[n – 1]。
在本教程中，您有两个示例。 这是运行上述程序的 java 代码，有两个示例：
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{3, 4, 5, 9, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{3, 4, 4, 10, 4};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 11;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
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