0-1背包问题

- 日理万妓 2024-03-26 19:24 32阅读 0赞

#### 目录 ####

*   *  问题描述
     *  0-1背包问题
     *  动态规划(图片版)
     *  动态规划(代码+图片版)

### 问题描述 ###

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

### 0-1背包问题 ###

假设你是一个小偷，背着一个可装下4磅东西的背包，你可以偷窃的物品如下：![在这里插入图片描述][a907f2fa0de14c86ac4a1cd731ea6d89.png]  
为了让偷窃的商品价值最高，你该选择哪些商品？  
\*\*最简单的算法是：\*\*尝试各种可能的商品组合，并找出价值最高的组合。  
![在这里插入图片描述][a697b37eb0114447abb5fc2f146b15d4.png]  
这样显然是可行的，但是速度非常慢。在只有3件商品的情况下，你需要计算8个不同的集合；当有4件商品的时候，你需要计算16个不同的集合。每增加一件商品，需要计算的集合数都将翻倍！这种算法的运行时间是O(2ⁿ)，真的是慢如蜗牛。

### 动态规划(图片版) ###

先把公式摆出来

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

解决这样问题的答案就是使用动态规划！下面来看看动态规划的工作原理。动态规划先解决子问题，再逐步解决大问题。  
对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。  
![在这里插入图片描述][ac8ba961e8ce434c9eb6d23bf7c1e569.png]  
比较有趣的一句话是：每个动态规划都从一个网格开始。  
背包问题的网格如下：  
![在这里插入图片描述][7ef699e518d849f4868f2a1e5691d858.png]  
网格的各行为商品，各列为不同容量（1~4磅）的背包。所有这些列你都需要，因为它们将帮助你计算子背包的价值。  
网格最初是空的。你将填充其中的每个单元格，网格填满后，就找到了问题的答案！  
**1.吉他**  
后面会列出计算这个网格中单元格值得公式，但现在我们先来一步一步做。首先来看第一行。  
![在这里插入图片描述][38d9ecbbe4534eeda6179ee92bcced1f.png]

这是吉他行，意味着你将尝试将吉他装入背包。在每个单元格，都需要做一个简单的决定：偷不偷吉他？别忘了，你要找出一个价值最高的商品集合。  
第一个单元格表示背包的的容量为1磅。吉他的重量也是1磅，这意味着它能装入背包！因此这个单元格包含吉他，价值为1500美元。  
下面来填充网格。  
![在这里插入图片描述][afa2d679fea6470283c23fb3aba9567a.png]  
与这个单元格一样，每个单元格都将包含当前可装入背包的所有商品。  
来看下一个单元格。这个单元格表示背包容量为2磅，完全能够装下吉他！  
![在这里插入图片描述][edc3920554dc47d9aab6aa7a045e01dd.png]  
这行的其他单元格也一样。别忘了，这是第一行，只有吉他可供你选择，换而言之，你假装现在还没发偷窃其他两件商品。  
![在这里插入图片描述][3e7a7f7620eb4129b236595005a72b3e.png]  
此时你很可能心存疑惑：原来的问题说的额是4磅的背包，我们为何要考虑容量为1磅、2磅等得背包呢？前面说过，动态规划从小问题着手，逐步解决大问题。这里解决的子问题将帮助你解决大问题。  
![在这里插入图片描述][821dd8219b654af1b9aa933061386e65.png]  
别忘了，你要做的是让背包中商品的价值最大。这行表示的是当前的最大价值。它指出，如果你有一个容量4磅的背包，可在其中装入的商品的最大价值为1500美元。  
你知道这不是最终解。随着算法往下执行，你将逐步修改最大价值。  
**2.音响行**  
我们来填充下一行——音响行。你现在处于第二行，可以偷窃的商品有吉他和音响。  
我们先来看第一个单元格，它表示容量为1磅的背包。在此之前，可装入1磅背包的商品最大价值为1500美元。  
![在这里插入图片描述][e586432720224ec091762105f3d807d3.png]  
该不该偷音响呢？  
背包的容量为1磅，显然不能装下音响。由于容量为1磅的背包装不下音响，因此最大价值依然是1500美元。  
![在这里插入图片描述][4cdc6d801f73499fa5c957003253f086.png]  
接下来的两个单元格的情况与此相同。在这些单元格中，背包的容量分别为2磅和3磅，而以前的最大价值为1500美元。由于这些背包装不下音响，因此最大的价值保持不变。  
![在这里插入图片描述][5036b0ecdd9a43b8a3508580f258a123.png]  
背包容量为4磅呢？终于能够装下音响了！原来最大价值为1500美元，但如果在背包中装入音响而不是吉他，价值将为3000美元！因此还是偷音响吧。  
![在这里插入图片描述][185f233ffb474b16b16f8d5123ca5686.png]  
你更新了最大价值。如果背包的容量为4磅，就能装入价值至少3000美元的商品。在这个网格中，你逐步地更新最大价值。  
![在这里插入图片描述][bf8f815c995b4498b7d68f2043d1c222.png]  
**3.笔记本电脑**

下面以同样的方式处理笔记本电脑。笔记本电脑重3磅，没法将其装入1磅或者2磅的背包，因此前两个单元格的最大价值仍然是1500美元。  
![在这里插入图片描述][c07b2183679c4e0b93c5fbfcba2b0fd3.png]  
对于容量为3磅的背包，原来的最大价值为1500美元，但现在你可以选择偷窃价值2000美元的笔记本电脑而不是吉他，这样新的最大价值将为2000美元。  
![在这里插入图片描述][fca20c11cb5a43b8b42af7967211b0c9.png]  
对于容量为4磅的背包，情况很有趣。这是非常重要的部分。当前的最大价值为3000美元，你可不偷音响，而偷笔记本电脑，但它只值2000美元。  
![在这里插入图片描述][3daea3d06a324a5b8336f9dbfaafcc8f.png]  
价值没有原来高，但是等一等，笔记本电脑的重量只有3磅，背包还有1磅的重量没用！

![在这里插入图片描述][6fc8e74495854186b7b5e1713d625a74.png]  
在1磅的容量中，可装入的商品的最大价值是多少呢？你之前计算过。  
![在这里插入图片描述][ca21916977454c47be74988d0816e82a.png]  
根据之前计算的最大价值可知，在1磅的容量中可装入吉他，价值1500美元。因此，你需要做如下的比较：  
![在这里插入图片描述][11f102c02a0a4a41b3732f952b466176.png]  
你可能始终心存疑惑：为何计算小背包可装入的商品的最大价值呢？但愿你现在明白了其中的原因！余下了空间时，你可根据这些子问题的答案来确定余下的空间可装入哪些商品。笔记本电脑和吉他的总价值为3500美元，因此偷它们是更好的选择。  
最终的网格类似于下面这样。  
![在这里插入图片描述][df1a3360c3134a739fadab4cad5119a1.png]  
答案如下：将吉他和笔记本电脑装入背包时价值更高，为3500美元。  
**如果还没懂，接下来用代码的例子让你完全明白**

### 动态规划(代码+图片版) ###

我举一个例子：  
背包最大重量为4。

*  1.确定dp数组以及下标的含义

对于背包问题，有一种写法， 是使用二维数组，即dp\[i\]\[j\] 表示从下标为\[0-i\]的物品里任意取，放进容量为j的背包，价值总和最大是多少。  
![在这里插入图片描述][a72b244a56274c939d563e324bbd7ab8.png]

*  2.确定递推公式

**不放物品i**：由dp\[i - 1\]\[j\]推出，即背包容量为j，里面不放物品i的最大价值，此时dp\[i\]\[j\]就是dp\[i - 1\]\[j\]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。)  
**放物品i**：由dp\[i - 1\]\[j - weight\[i\]\]推出，dp\[i - 1\]\[j - weight\[i\]\] 为背包容量为j - weight\[i\]的时候不放物品i的最大价值，那么dp\[i - 1\]\[j - weight\[i\]\] + value\[i\] （物品i的价值），就是背包放物品i得到的最大价值  
所以递归公式： dp\[i\]\[j\] = Math.max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]);

*  3.dp数组如何初始化

首先从dp\[i\]\[j\]的定义出发，如果背包容量j为0的话，即dp\[i\]\[0\]，无论是选取哪些物品，背包价值总和一定为0。如图：![在这里插入图片描述][ae866807320c4e84aa08eaebe570fd62.png]  
状态转移方程 dp\[i\]\[j\] = Math.max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。  
dp\[0\]\[j\]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。  
那么很明显当 j < weight\[0\]的时候，dp\[0\]\[j\] 应该是 0，因为背包容量比编号0的物品重量还小。  
当j >= weight\[0\]时，dp\[0\]\[j\] 应该是value\[0\]，因为背包容量放足够放编号0物品。  
代码初始化如下：

// 初始化dp数组
            // 创建数组后，其中默认的值就是0
            for (int j = weight[0]; j <= bagSize; j++) {
        
                dp[0][j] = value[0];
            }

此时dp数组初始化情况如图所示：  
![在这里插入图片描述][adf23123c26d476f8d3a843505bd67dd.png]  
dp\[0\]\[j\] 和 dp\[i\]\[0\] 都已经初始化了，那么其他下标应该初始化多少呢？  
其实从递归公式： dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]); 可以看出dp\[i\]\[j\] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。  
统一把dp数组统一初始为0，更方便一些。  
![在这里插入图片描述][fe97534c4591425592ed2df38cc59163.png]

*  4.确定遍历顺序

在如下图中，可以看出，有两个遍历的维度：物品与背包重量  
先给出先遍历物品，然后遍历背包重量的代码。

// 填充dp数组
            for (int i = 1; i < weight.length; i++) {
        
                for (int j = 1; j <= bagSize; j++) {
        
                    if (j < weight[i]) {
        
                        /**
                         * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                         * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                         */
                        dp[i][j] = dp[i-1][j];
                    } else {
        
                        /**
                         * 当前背包的容量可以放下物品i
                         * 那么此时分两种情况：
                         *    1、不放物品i
                         *    2、放物品i
                         * 比较这两种情况下，哪种背包中物品的最大价值最大
                         */
                        dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                    }
                }
            }

*  5.举例推导dp数组

![在这里插入图片描述][db7a67eca68d4a24a993dd98c037eccb.png]  
整体代码

public class BagProblem {
        
        public static void main(String[] args) {
        
            int[] weight = {
        1,3,4};
            int[] value = {
        15,20,30};
            int bagSize = 4;
            testWeightBagProblem(weight,value,bagSize);
        }
    
        /**
         * 动态规划获得结果
         * @param weight  物品的重量
         * @param value   物品的价值
         * @param bagSize 背包的容量
         */
        public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
        
    
            // 创建dp数组
            int goods = weight.length;  // 获取物品的数量
            int[][] dp = new int[goods][bagSize + 1];
    
            // 初始化dp数组
            // 创建数组后，其中默认的值就是0
            for (int j = weight[0]; j <= bagSize; j++) {
        
                dp[0][j] = value[0];
            }
    
            // 填充dp数组
            for (int i = 1; i < weight.length; i++) {
        
                for (int j = 1; j <= bagSize; j++) {
        
                    if (j < weight[i]) {
        
                        /**
                         * 当前背包的容量都没有当前物品i大的时候，是不放物品i的
                         * 那么前i-1个物品能放下的最大价值就是当前情况的最大价值
                         */
                        dp[i][j] = dp[i-1][j];
                    } else {
        
                        /**
                         * 当前背包的容量可以放下物品i
                         * 那么此时分两种情况：
                         *    1、不放物品i
                         *    2、放物品i
                         * 比较这两种情况下，哪种背包中物品的最大价值最大
                         */
                        dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                    }
                }
            }
    
            // 打印dp数组
            for (int i = 0; i < goods; i++) {
        
                for (int j = 0; j <= bagSize; j++) {
        
                    System.out.print(dp[i][j] + "\t");
                }
                System.out.println("\n");
            }
        }
    }

![在这里插入图片描述][ec45e40f85d84965a766f5e1a46e9c82.png]

[a907f2fa0de14c86ac4a1cd731ea6d89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4925d903e12943cfbbbfc1dcf2ba31bc.png
[a697b37eb0114447abb5fc2f146b15d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d6e3479722e34b978912130504760983.png
[ac8ba961e8ce434c9eb6d23bf7c1e569.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1f42bf9c076f457bafb38ed071b726be.png
[7ef699e518d849f4868f2a1e5691d858.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/3f7971f1626e4cebbe2bcb9acb3e8080.png
[38d9ecbbe4534eeda6179ee92bcced1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4ae57f07745c41fcb4867b38543c27ec.png
[afa2d679fea6470283c23fb3aba9567a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e7af1105756a422c9c9df8e636ab6109.png
[edc3920554dc47d9aab6aa7a045e01dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a77a6e2953e9454fbbf1c052b23e309c.png
[3e7a7f7620eb4129b236595005a72b3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/df8370d3e6d847dda08de7f342f6966b.png
[821dd8219b654af1b9aa933061386e65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f45409f583ef47279bd333eb503064f1.png
[e586432720224ec091762105f3d807d3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8de56130d6664f56b99dae9e872fcea7.png
[4cdc6d801f73499fa5c957003253f086.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/890d89628adf4b86871b88e318685b86.png
[5036b0ecdd9a43b8a3508580f258a123.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a4569651d7ea4052911ea24ce3682f35.png
[185f233ffb474b16b16f8d5123ca5686.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8684cb12025e4eb8a4c5c038a0dc987b.png
[bf8f815c995b4498b7d68f2043d1c222.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/f2a682187fc648ff8534813b0efebcaf.png
[c07b2183679c4e0b93c5fbfcba2b0fd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/577b2fb4c35a408396070affa82b4c7f.png
[fca20c11cb5a43b8b42af7967211b0c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ce701e46328743db81eee6e246210dbc.png
[3daea3d06a324a5b8336f9dbfaafcc8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/594b02208baa4da99cae6361cdd325a2.png
[6fc8e74495854186b7b5e1713d625a74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/812c6683d2364a56bb4a0cd6eef54320.png
[ca21916977454c47be74988d0816e82a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/1d21313cef53433a828964ce4ea9292f.png
[11f102c02a0a4a41b3732f952b466176.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/b6f5cf68ec494b93b1ba5ab23940a290.png
[df1a3360c3134a739fadab4cad5119a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/c3f3cb4b7c164e33b8b52640949a30df.png
[a72b244a56274c939d563e324bbd7ab8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/12a4ef4389a44fa391e486235cd8c11b.png
[ae866807320c4e84aa08eaebe570fd62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4ee00d6080be4788889c331b91e16498.png
[adf23123c26d476f8d3a843505bd67dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a00f0fdcffe74c559e0e3731c89d693e.png
[fe97534c4591425592ed2df38cc59163.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7dc838543da94b67a7cd8bdac3c6f8ae.png
[db7a67eca68d4a24a993dd98c037eccb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2dec556ee0b242ea9b563b74a3dee153.png
[ec45e40f85d84965a766f5e1a46e9c82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/268c347265e34c929e219ac47a424448.png