01背包问题 ﹏ヽ暗。殇╰゛Y 2022-10-11 13:40 257阅读 0赞 ## [0-1背包问题][0-1] ## Reference: https://www.jianshu.com/p/a66d5ce49df5 ## 问题描述: ## 0-1背包问题:给定n种物品和一背包。物品 i 的重量似乎 wi,其价值为 vi,背包的容量为 c。问应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大? > 说实在的,书上讲的东西生涩难懂,我更偏向于看一些有趣的东西。我们来换一个风格来描述这一个问题。 > 以下内容大部分来自\*\*《算法图解》\*\*一书。看完之后大有收获。 ## 另一种风格的描述: ## 假设你是一个小偷,背着一个可装下4磅东西的背包,你可以偷窃的物品如下: ![img][] 为了让偷窃的商品价值最高,你该选择哪些商品? #### 简单算法 #### 最简单的算法是:尝试各种可能的商品组合,并找出价值最高的组合。 ![img][img 1] 这样显然是可行的,但是速度非常慢。在只有3件商品的情况下,你需要计算8个不同的集合;当有4件商品的时候,你需要计算16个不同的集合。每增加一件商品,需要计算的集合数都将翻倍!**这种算法的运行时间是O(2ⁿ),真的是慢如蜗牛。** #### 动态规划 #### 解决这样问题的答案就是使用动态规划!下面来看看动态规划的工作原理。动态规划先解决子问题,再逐步解决大问题。 对于背包问题,你先解决小背包(子背包)问题,再逐步解决原来的问题。 ![img][img 2] 比较有趣的一句话是:**每个动态规划都从一个网格开始。** 背包问题的网格如下: ![img][img 3] 网格的各行为商品,各列为不同容量(1~4磅)的背包。所有这些列你都需要,因为它们将帮助你计算子背包的价值。 网格最初是空的。**你将填充其中的每个单元格,网格填满后,就找到了问题的答案!** #### 1.吉他行 #### 后面会列出计算这个网格中单元格值得公式,但现在我们先来一步一步做。首先来看第一行。 ![img][img 4] 这是吉他行,意味着你将尝试将吉他装入背包。在每个单元格,都需要做一个简单的决定:偷不偷吉他?别忘了,你要找出一个价值最高的商品集合。 第一个单元格表示背包的的容量为1磅。吉他的重量也是1磅,这意味着它能装入背包!因此这个单元格包含吉他,价值为1500美元。 下面来填充网格。 ![img][img 5] 与这个单元格一样,每个单元格都将包含当前可装入背包的所有商品。 来看下一个单元格。这个单元格表示背包容量为2磅,完全能够装下吉他! ![img][img 6] 这行的其他单元格也一样。别忘了,这是第一行,只有吉他可供你选择,换而言之,你假装现在还没发偷窃其他两件商品。 ![img][img 7] 此时你很可能心存疑惑:原来的问题说的额是4磅的背包,我们为何要考虑容量为1磅、2磅等得背包呢?前面说过,\*\*动态规划从小问题着手,逐步解决大问题。\*\*这里解决的子问题将帮助你解决大问题。 ![img][img 8] 别忘了,你要做的是让背包中商品的价值最大。\*这行表示的是当前的最大价值。\*它指出,如果你有一个容量4磅的背包,可在其中装入的商品的最大价值为1500美元。 你知道这不是最终解。随着算法往下执行,你将逐步修改最大价值。 #### 2.音响行 #### 我们来填充下一行——音响行。你现在处于第二行,可以偷窃的商品有吉他和音响。 我们先来看第一个单元格,它表示容量为1磅的背包。在此之前,可装入1磅背包的商品最大价值为1500美元。 ![img][img 9] 该不该偷音响呢? 背包的容量为1磅,显然不能装下音响。由于容量为1磅的背包装不下音响,因此最大价值依然是1500美元。 ![img][img 10] 接下来的两个单元格的情况与此相同。在这些单元格中,背包的容量分别为2磅和3磅,而以前的最大价值为1500美元。由于这些背包装不下音响,因此最大的价值保持不变。 ![img][img 11] 背包容量为4磅呢?终于能够装下音响了!原来最大价值为1500美元,但如果在背包中装入音响而不是吉他,价值将为3000美元!因此还是偷音响吧。 ![img][img 12] 你更新了最大价值。如果背包的容量为4磅,就能装入价值至少3000美元的商品。在这个网格中,你逐步地更新最大价值。 ![img][img 13] #### 3.笔记本电脑行 #### 下面以同样的方式处理笔记本电脑。笔记本电脑重3磅,没法将其装入1磅或者2磅的背包,因此前两个单元格的最大价值仍然是1500美元。 ![img][img 14] 对于容量为3磅的背包,原来的最大价值为1500美元,但现在你可以选择偷窃价值2000美元的笔记本电脑而不是吉他,这样新的最大价值将为2000美元。 ![img][img 15] \*\*对于容量为4磅的背包,情况很有趣。\*\*这是非常重要的部分。当前的最大价值为3000美元,你可不偷音响,而偷笔记本电脑,但它只值2000美元。 ![img][img 16] 价值没有原来高,但是等一等,笔记本电脑的重量只有3磅,背包还有1磅的重量没用! ![img][img 17] 在1磅的容量中,可装入的商品的最大价值是多少呢?*你之前计算过。* ![img][img 18] 根据之前计算的最大价值可知,在1磅的容量中可装入吉他,价值1500美元。因此,你需要做如下的比较: ![img][img 19] 你可能始终心存疑惑:为何计算小背包可装入的商品的最大价值呢?但愿你现在明白了其中的原因!\*\*余下了空间时,你可根据这些子问题的答案来确定余下的空间可装入哪些商品。\*\*笔记本电脑和吉他的总价值为3500美元,因此偷它们是更好的选择。 最终的网格类似于下面这样。 ![img][img 20] 答案如下:将吉他和笔记本电脑装入背包时价值更高,为3500美元。 你可能认为,计算最后一个单元格的价值时,我使用了不同的公式。那是因为填充之前的单元格时,我故意避开了一些复杂的因素。其实,计算每个单元格的价值时,使用的公式都相同。这个公式如下。 ![img][img 21] 你可以使用这个公式来计算每个单元格的价值,最终的网格将与前一个网格相同。现在你明白了为何要求解子问题了吧?你可以合并两个子问题的解来得到更大问题的解。 ![img][img 22] ## 代码实现: ## 算法的核心是思想,当清楚了整个过程,那么写代码就简单了,直接来模拟上述的一个过程: /** * @author:我没有三颗心脏 * @create:2017-11-14-10:24 */ public class MaxBag { static int n; // 描述物品个数 static int c; // 描述背包容量 static int[] value; // 描述物品价值 static int[] weight; // 描述物品重量 public static void main(String[] args) { // 初始赋值操作 value = new int[]{1500, 3000, 2000}; weight = new int[]{1, 4, 3}; c = 4; n = 3; // 构造最优解的网格:3行4列 int[][] maxValue = new int[n][c]; for (int i = 0; i < n; i++) { for (int j = 0; j < c; j++) { maxValue[i][j] = 0; } } // end for // 填充网格 for (int i = 0; i < n; i++) { for (int j = 1; j <= c; j++) { if (i == 0) { maxValue[i][j - 1] = (weight[i] <= j ? value[i] : 0); } else { int topValue = maxValue[i - 1][j - 1]; // 上一个网格的值 int thisValue = (weight[i] <= j ? // 当前商品的价值 + 剩余空间的价值 (j - weight[i] > 0 ? value[i] + maxValue[i - 1][j - weight[i]] : value[i]) : topValue); // 返回 topValue和thisValue中较大的一个 maxValue[i][j - 1] = (topValue > thisValue ? topValue : thisValue); } // end if } // end inner for } // end outer for // 打印结果二维数组maxValue for (int i = 0; i < n; i++) { for (int j = 0; j < c; j++) { System.out.printf("%6d", maxValue[i][j]); } System.out.println(); } } } 最后打印出来的结果如下: ![img][img 23] ## 再增加一件商品将如何呢 ## 假设你发现还有第四件商品可偷——一个iPhone!*(或许你会毫不犹豫的拿走,但是请别忘了问题的本身是要拿走价值最大的商品)* ![img][img 24] 此时需要重新执行前面所做的计算吗?不需要。别忘了,动态规划逐步计算最大价值。到目前为止,计算出的最大价值如下: ![img][img 25] 这意味着背包容量为4磅时,你最多可偷价值3500美元的商品。但这是以前的情况,下面再添加表示iPhone的行。 ![img][img 26] 我们还是从第一个单元格开始。iPhone可装入容量为1磅的背包。之前的最大价值为1500美元,但iPhone价值2000美元,因此该偷iPhone而不是吉他。 ![img][img 27] 在下一个单元格中,你可装入iPhone和吉他。 ![img][img 28] 对于第三个单元格,也没有比装入iPhone和吉他更好的选择了。 对于最后一个单元格,情况比较有趣。当前的最大价值为3500美元,但你可以偷iPhone,这将余下3磅的容量。 ![img][img 29] 3磅容量的最大价值为2000美元!再加上iPhone价值2000美元,总价值为4000美元。新的最大价值诞生了! 最终的网格如下。 ![img][img 30] #### 问题:沿着一列往下走,最大价值可能降低吗? #### ![img][img 31] 答案是:不可能。因为每次迭代时,你都存储的是当前的最大价值。**最大价值不可能比以前低!** [0-1]: https://www.cnblogs.com/skying555/p/11119488.html [img]: /images/20221005/3483a2453fad4856a3010758a4e55f3b.png [img 1]: /images/20221005/5f9fd6c2c03b422683b93cdcd50b09d3.png [img 2]: /images/20221005/e0d62e5eaa2c406da3df69ebcf8b6ba1.png [img 3]: /images/20221005/5eab7e35cd2349d69c3af6f950b94d60.png [img 4]: /images/20221005/d742d00687284baf89f5efcbb2a76151.png [img 5]: /images/20221005/d19f4f7984594a5f85c8a2501bcb7337.png [img 6]: /images/20221005/d9f5b0df9fdd43f7b6c0c9e0d986dce7.png [img 7]: /images/20221005/c0e96c93c7cd409eb4297bf6b97a98ec.png [img 8]: /images/20221005/868141a3999346e1b078bbae87d7a336.png [img 9]: /images/20221005/23b501e7ba3c4e4797337b70b2f15dda.png [img 10]: /images/20221005/0c59a1de1ae64222a32c21703615931d.png [img 11]: /images/20221005/4c563d24614041c1b42fa977bb6f5ade.png [img 12]: /images/20221005/6eec98c3e4734c7dbe8f4ed62b1ca0f5.png [img 13]: /images/20221005/8038516b721345ccabb5efaf3692406d.png [img 14]: /images/20221005/424f9beacda54cc0bd0c120362cd2853.png [img 15]: /images/20221005/2c09b798ae584d7ea56485031e5d5d80.png [img 16]: /images/20221005/22eb2d199cd04d7eb6880568d3eeaf00.png [img 17]: /images/20221005/9df8781f4f474a2eb6e9039c82359a15.png [img 18]: /images/20221005/900358add60549f8bec1ca2a1de8a7ae.png [img 19]: /images/20221005/a05cd3113c1149c1a80604de79a4efec.png [img 20]: /images/20221005/983c05dc4e174e9182ac11e2a557dfdc.png [img 21]: /images/20221005/b8934e5245f04f2f817895c7f460e2b6.png [img 22]: /images/20221005/78ee496d161f4df0ab1dec5be8a66439.png [img 23]: /images/20221005/849e18dd84914fafb5a01291ac0531b7.png [img 24]: /images/20221005/6f1b2b8b2026419297bcf30d518ac3a0.png [img 25]: /images/20221005/82ec1697b64a4f86b313fca18997ce4c.png [img 26]: /images/20221005/567878fe779a419a91eaff7cc6ffa3fa.png [img 27]: /images/20221005/43ef1f8be88b4f2bb788f9014d84970b.png [img 28]: /images/20221005/8fa4a9522d79469386f1678067cf3f44.png [img 29]: /images/20221005/2226f0a287ea4290bff88e48cfa5f97a.png [img 30]: /images/20221005/9797570a12954cb2aa1dbcdc53f115a2.png [img 31]: /images/20221005/038f82ee8b9743babd349957f905b530.png
相关 01背包问题 [0-1背包问题][0-1] Reference: https://www.jianshu.com/p/a66d5ce49df5 问题描述: 0-1背包问题:给定 ﹏ヽ暗。殇╰゛Y/ 2022年10月11日 13:40/ 0 赞/ 258 阅读
相关 01背包问题 1.题目 有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大,要求是:物品只能放一次。 2.分 系统管理员/ 2022年09月10日 11:27/ 0 赞/ 220 阅读
相关 背包问题-背包01-苹果 package 动态规划.背包01; import java.util.Scanner; public class 苹果 \{ static class 野性酷女/ 2022年07月12日 12:12/ 0 赞/ 259 阅读
相关 01背包问题 ![Center][] ![Center 1][] [Center]: /images/20220616/e1a67e5ed0214bac8ec5293bc2b54 ╰+攻爆jí腚メ/ 2022年06月16日 14:46/ 0 赞/ 238 阅读
相关 01背包问题 public class package0_1 { int V[][] = new int[200][200];//物品选取,背包承重 int max( 约定不等于承诺〃/ 2022年06月08日 06:15/ 0 赞/ 245 阅读
相关 01背包问题 【例9.11】01背包问题 时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】 一个旅行者有一个最多能装M公斤的背包,现在有n件物 淩亂°似流年/ 2022年06月08日 03:59/ 0 赞/ 240 阅读
相关 背包问题—01背包、完全背包 01背包问题 题目 有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。 思路 这 末蓝、/ 2022年05月30日 10:10/ 0 赞/ 369 阅读
相关 01背包问题 简单背包问题 设有一个背包可以放入的物品重量为S,现有n件物品,重量分别是w1,w2,w3,…wn。 问能否从这n件物品中选择若干件放入背包中,使得放入的重量之和正好为S 痛定思痛。/ 2022年05月26日 12:18/ 0 赞/ 237 阅读
相关 01背包问题 转载:[https://blog.csdn.net/xp731574722/article/details/70766804][https_blog.csdn.net_xp73 怼烎@/ 2022年05月06日 15:00/ 0 赞/ 293 阅读
相关 背包问题01 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\],价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题,特 左手的ㄟ右手/ 2022年01月29日 11:34/ 0 赞/ 329 阅读
还没有评论,来说两句吧...