01 背包问题
问题描述：
如果有n个项目，则项目权重为w[i]，项目值为c[i]。然后选择该物品并将其放入背包中。令V为背包可支撑的最大重量。如何选择放入背包的物品才能使背包中物品的总价值最大化？
我曾多次试图理解这个问题，研究过各种解法，但无论读多少遍，它仍然很抽象，我只是记住了解法的状态转移方程。我没有“理解”其背后的逻辑。直到读到这篇文章，才向作者表示感谢，记录在此。
01 背包问题的另一种解释方式：
假设您是一名小偷，背着一个可容纳4 磅材料的背包。可能被盗的物品包括：
您应该选择哪件物品才能最大限度地提高被盗物品的价值？
暴力解法
最简单的算法是尝试不同可能的产品组合并找到价值最高的组合。
这显然是可能的，但非常耗时。如果只有3 个项目，则需要计算8 个不同的集合，如果有4 个项目，则需要计算16 个不同的集合。每增加一个项目，计算的组数就会增加一倍。对于每个项目，有两种可能性：选择或不选择。这意味着该算法的运行时间为O(2)。
动态规划
此类问题的答案是使用动态规划。让我们看看动态规划是如何工作的。动态规划首先解决部分问题，然后逐步解决更大的问题。
对于背包问题，首先解决一个小背包（子背包）问题，然后逐步解决原始问题。
一句有趣的话是：所有动态规划都从网格开始。 （由此可见，学习网格求导非常重要，而有些题解写得不好的原因就是没有给出网格求导过程，即不清楚为什么会这样。）（因为没有解释）网格应该“像这样”设计。这篇文章正好解答了我长期以来对这一点的困惑。 ）
背包问题的网格如下：
网格的行代表产品，列代表各种容量（1 至4 磅）的背包。所有这些列都是必需的，因为它们帮助我们计算子背包的价值。
网格最初是空的。填写所有单元格并填写网格以找到问题的答案。
1. 吉他行
稍后我将列出计算此网格中单元格值的公式，但现在让我们逐步进行。让我们从第一行开始。
这意味着吉他排，意味着将吉他塞进背包里。在每个牢房中，你必须做出一个简单的决定：是否偷吉他。请记住，您想要找到具有最佳价值的项目集合。
第一个单元格代表背包的容量1 磅。吉他重1 磅，适合放入背包中。所以这个牢房里有一把价值1,500 美元的吉他。
让我们填写网格。
像这个单元一样，每个单元都包含当前适合您背包的所有物品。
让我们看看下一个单元格。这个单元格表明背包的容量为2磅，足以容纳一把吉他。
该行中的其他单元格也是如此。请不要忘记。这是第一行，唯一的选择是吉他。换句话说，你假装你还没有偷走另外两件物品。
此时您可能想知道。最初的问题是关于4 磅的背包，那么我为什么要考虑容量为1 磅、2 磅等的背包呢？如前所述，动态规划部分是我们从小问题开始，逐渐转向解决更大的问题。这里解决的子问题将有助于解决更大的问题。
请记住，您要做的就是最大化背包中物品的价值。该线代表当前最大值。如果您有一个4 磅的背包，则说明背包中物品的最大价值为1,500 美元。
你知道这不是最终的解决方案。随着算法的退化逐渐改变最大值。
2. 音响行
下一行—— 让我们填写音频行。你现在在第二排，你可以偷的物品是吉他和立体声音响。
我们首先看第一个单元格，它代表一个容量为1 磅的背包。此前，一磅背包中可容纳物品的最高价值为1,500 美元。
我应该偷立体声吗？
背包的容量为1磅，但显然不能容纳音响。 1 磅重的背包无法容纳扬声器，因此最高价格仍为1,500 美元。
接下来的两个单元格也是如此。这些电池的背包容量分别为2 磅和3 磅，而之前的最高价格为1,500 美元。这些背包不能容纳立体声音响，因此它们仍然是最有价值的。
如果背包的承重能力为4 磅怎么办？我终于可以安装扬声器了！最初的最高价格是1,500 美元，但如果你在背包里放一个立体声音响而不是吉他，价格就会增加到3,000 美元。那么我们来偷一下立体声音响吧。
更新了最大值。一个容量为4 磅的背包可以容纳至少价值3,000 美元的商品。该网格逐步更新最大值。
3. 笔记本电脑行
现在在笔记本电脑上执行相同的步骤。由于笔记本电脑重3 磅，而且无法装入1 或2 磅的背包中，因此前两块电池的最高价值仍然是1,500 美元。
对于一个3 磅重的背包，原来的最高限额为1,500 美元，但现在您可以选择偷窃一台2,000 美元的笔记本电脑而不是吉他，因此新的最高限额为2,000 美元。
对于容量为4 磅的背包来说，这种情况很有趣。这是一个非常重要的部分。当前最高限额为3,000 美元。你可以偷一台笔记本电脑而不是立体声音响，但它只值2,000 美元。
它不像原来那么值钱，但笔记本电脑仅重3 磅，而背包还有1 磅的浪费重量。
一磅容量中可以装载的产品的最大价值是多少？您之前已经计算过！
根据之前计算的最大值，这把吉他的容量为1 磅，价值1,500 美元。因此，应进行以下比较：
ge?_iz=58558&from=article.pc_detail&lk3s=953192f4&x-expires=1717695724&x-signature=h4fWMQszsNrJEc9pV9LnmQvGvbI%3D” />
你可能始终心存疑惑：为何计算小背包可装入的商品的最大价值呢？但愿你现在明白了其中的原因！当出现部分剩余空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品。笔记本电脑和吉他的总价值为3500美元，因此偷它们是更好的选择。
最终的网格类似于下面这样。
答案如下：将吉他和笔记本电脑装入背包时价值更高，为3500美元。
你可能认为，计算最后一个单元格的价值时，我使用了不同的公式。那是因为填充之前的单元格时，我故意避开了一些复杂的因素。其实，计算每个单元格的价值时，使用的公式都相同。这个公式如下。
你可以使用这个公式来计算每个单元格的价值，最终的网格将与前一个网格相同。现在你明白了为何要求解子问题了吧？——因为你可以合并两个子问题的解来得到更大问题的解。
4. 等等，再增加一件商品将如何变化呢？
假设你发现还有第四件商品可偷——一个iPhone！（或许你会毫不犹豫的拿走，但是请别忘了问题的本身是要拿走价值最大的商品）
此时需要重新执行前面所做的计算吗？不需要。别忘了，动态规划逐步计算最大价值。到目前为止，计算出的最大价值如下：
这意味着背包容量为4磅时，你最多可偷价值3500美元的商品。但这是以前的情况，下面再添加表示iPhone的行。
我们还是从第一个单元格开始。iPhone可装入容量为1磅的背包。之前的最大价值为1500美元，但iPhone价值2000美元，因此该偷iPhone而不是吉他。
在下一个单元格中，你可装入iPhone和吉他。
对于第三个单元格，也没有比装入iPhone和吉他更好的选择了。
对于最后一个单元格，情况比较有趣。当前的最大价值为3500美元，但你可以偷iPhone，这将余下3磅的容量。
3磅容量的最大价值为2000美元！再加上iPhone价值2000美元，总价值为4000美元。新的最大价值诞生了！
最终的网格如下：
相信看到这里，并且亲手推导过网格，应该对动态规划的状态转移方程背后的逻辑有了更深的理解。现在，再回头看01背包问题的经典描述，并实现代码。
问题描述：
给定 3 件物品，物品的重量为 weight[]={1,3,1}，对应的价值为 value[]={15,30,20}。现挑选物品放入背包中，假定背包能承受的最大重量 W 为 4，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
令 dp[i][w] 表示前 i 件物品放入容量为 w 的背包中可获得的最大价值。为了方便处理，我们约定下标从 1 开始。初始时，网格如下：
根据之前已经引出的状态转移方程，我们再来理解一遍，对于编号为 i 的物品：
如果选择它，那么，当前背包的最大价值等于” i 号物品的价值“ 加上 ”减去 i 号物品占用的空间后剩余的背包空间所能存放的最大价值“，即dp[i][k] = value[i] + dp[i-1][k-weight[i]]；如果不选择它，那么，当前背包的价值就等于前 i-1 个物品存放在背包中的最大价值，即 dp[i][k] = dp[i-1][k]dp[i][k] 的结果取两者的较大值，即：
dp[i][k] = max(value[i] + dp[i-1][k-weight[i]], dp[i-1][k])
动态规划
代码实现如下：
public class BeiBao01 { public int maxValue(int[] weight, int[] value, int W) { //这里假定传入的weight和values数组长度总是一致的 int n = weight.length; if (n == 0) return 0; int[][] dp = new int[n + 1][W + 1]; for (int i = 1; i <= n; i++) { for (int k = 1; k <= W; k++) { // 存放 i 号物品（前提是放得下这件物品） int valueWith_i = (k-weight[i-1] >= 0) ? (value[i-1]+dp[i-1][k-weight[i-1]]) : 0; // 不存放 i 号物品 int valueWithout_i = dp[i – 1][k]; dp[i][k] = Math.max(valueWith_i, valueWithout_i); } } return dp[n][W]; } public static void main(String[] args) { BeiBao01 obj = new BeiBao01(); int[] w = {1, 4, 3}; int[] v = {15, 30, 20}; int W = 4; System.out.println(obj.maxValue(w, v, W)); }}
下面实现的版本稍有不同：
public int maxValue(int[] weight, int[] value, int W) { int n = weight.length; if (n == 0) return 0; int[][] dp = new int[n][W + 1]; // 先初始化第 0 行，也就是尝试把 0 号物品放入容量为 k 的背包中 for (int k = 1; k <= W; k++) { if (k >= weight[0]) dp[0][k] = value[0]; else dp[0][k] = 0; // 这一步其实没必要写，因为dp[][]数组默认就是0 } for (int i = 1; i < n; i++) { for (int k = 1; k <= W; k++) { // 存放 i 号物品（前提是放得下这件物品） int valueWith_i = (k-weight[i] >= 0) ? (value[i] + dp[i-1][k-weight[i]]) : 0; // 不存放 i 号物品 int valueWithout_i = dp[i-1][k]; dp[i][k] = Math.max(valueWith_i, valueWithout_i); } } return dp[n-1][W]; }对应的初始化网格如下：
（个人更喜欢第二种实现方式，感觉理解起来更友好）
时间复杂度：O(nW)；空间复杂度：O(nW)
动态规划+压缩空间
观察上面的代码，会发现，当更新dp[i][..]时，只与dp[i-1][..]有关，也就是说，我们没有必要使用O(n*W)的空间，而是只使用O(W)的空间即可。下面先给出代码，再结合图例进行说明。
public int maxValue(int[] weight, int[] value, int W) { int n = weight.length; if (n == 0) return 0; // 辅助空间只需要O(W)即可 int[] dp = new int[W + 1]; for (int i = 0; i < n; i++) { // 注意这里必须从后向前！！！ for (int k = W; k >= 1; k–) { int valueWith_i = (k – weight[i] >= 0) ? (dp[k – weight[i]] + value[i]) : 0; int valueWithout_i = dp[k]; dp[k] = Math.max(valueWith_i, valueWithout_i); } } return dp[W]; }这里的状态转移方程变成了：dp[k](新值) = max(value[i]+dp[k-weight[i]](旧值), dp[k](旧值))
为什么说这里必须反向遍历来更新dp[]数组的值呢？原因是索引较小的元素可能会被覆盖。我们来看例子，假设我们已经遍历完了第 i=1 个元素（即weight=3, value=30），如下图所示：
现在要更新第 i=2 个元素（即weight=1, value=20），由于我们只申请了一维空间的数组，因此对dp[]数组的修改会覆盖上一轮dp[]数组的值，这里用浅色代表上一轮的值，深色代表当前这一轮的值。
鉴于上面出现的问题，因此必须采用反向遍历来回避这个问题。仍然假设第 i=1 个元素已经更新完毕，现在更新第 i=2 个元素。示意图如下：
可以看到，反向遍历就可以避免这个问题了！
事实上，我们还可以进一步简化上面的代码，如下：
public int maxValue(int[] weight, int[] value, int W) { int n = weight.length; if (n == 0) return 0; int[] dp = new int[W + 1]; for (int i = 0; i < n; i++) { //只要确保 k>=weight[i] 即可，而不是 k>=1，从而减少遍历的次数 for (int k = W; k >= weight[i]; k–) { dp[k] = Math.max(dp[k – weight[i]] + value[i], dp[k]); } } return dp[W]; }为什么可以这样简化呢？我们重新看一下这段代码：
for (int k = W; k >= 1; k–) { int valueWith_i = (k – weight[i] >= 0) ? (dp[k – weight[i]] + value[i]) : 0; int valueWithout_i = dp[k]; dp[k] = Math.max(valueWith_i, valueWithout_i);}如果k>=weight[i] 不成立，则valueWith_i 的值为0，那么显然有：
dp[k] = Math.max(valueWith_i, valueWithout_i) = max(0, dp[k]) = dp[k] 也就是dp[k]没有更新过，它的值还是上一轮的值，因此就没必要执行了，可以提前退出循环！
原创文章，作者：小条，如若转载，请注明出处：https://www.sudun.com/ask/79915.html
