动态规划：01背包理论基础

桃扇骨 2023-10-16 16:11 56阅读 0赞

#### 动态规划：01背包理论基础 ####

*  思路
 *   *  01 背包
     *  二维dp数组01背包
     *   *  1. 确定dp数组以及下标的含义
         *  2. 确定递推公式
         *  3. dp数组如何初始化
         *  4. 确定遍历顺序
         *  5. 举例推导dp数组
 *  总结
 *  代码实现

## 思路 ##

对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。  
![在这里插入图片描述][10c77a385bce40ac9f65b5c6f0e83e11.png]  
而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。

**所以背包问题的理论基础重中之重是01背包，一定要理解透！**

leetcode上没有纯01背包的问题，都是01背包应用方面的题目，也就是需要转化为01背包问题。

**所以我先通过纯01背包问题，把01背包原理讲清楚，后续再讲解leetcode题目的时候，重点就是讲解如何转化为01背包问题了**。

### 01 背包 ###

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。**每件物品只能用一次**，求解将哪些物品装入背包里物品价值总和最大。  
![在这里插入图片描述][b35515bfad8545859ec52de2e1350cf6.png]

### 二维dp数组01背包 ###

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

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

只看这个二维数组的定义，大家一定会有点懵，看下面这个图：  
![在这里插入图片描述][5a2ea8f40de94c94aed3099e7cc7728b.png]  
**要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的**，如果哪里看懵了，就来回顾一下i代表什么，j又代表什么。

#### 2. 确定递推公式 ####

再回顾一下dp\[i\]\[j\]的含义：从下标为\[0-i\]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

那么可以有两个方向推出来dp\[i\]\[j\]，

*  **不放物品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\] = max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]);

#### 3. dp数组如何初始化 ####

**关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱**。

首先从dp\[i\]\[j\]的定义出发，如果背包容量j为0的话，即dp\[i\]\[0\]，无论是选取哪些物品，背包价值总和一定为0。如图：  
![在这里插入图片描述][c84ef7f351274f4f91f3738b445c2305.png]  
再看其他情况。

状态转移方程 dp\[i\]\[j\] = 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物品。

代码初始化如下：

for(int j = 0; j < weight[0]; j++){
         // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    	dp[0][j] = 0;
    }
    // 正序遍历
    for(int j = weight[0]; j <= bagweight; j++){
        
    	dp[0][j] = value[0];
    }

此时dp数组初始化情况如图所示：  
![在这里插入图片描述][de77d5eba4e3419babcc10d617709575.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\] 是由左上方数值推导出来了，那么 其他下标初始为什么数值都可以，因为都会被覆盖。

**初始-1，初始-2，初始100，都可以！**

但只不过一开始就统一把dp数组统一初始为0，更方便一些。

如图：  
![在这里插入图片描述][cfecc9bb95e6417bbe436e30909bc3f1.png]  
**费了这么大的功夫，才把如何初始化讲清楚，相信不少同学平时初始化dp数组是凭感觉来的，但有时候感觉是不靠谱的**。

#### 4. 确定遍历顺序 ####

在如下图中，可以看出，有两个遍历的维度：物品与背包重量  
![在这里插入图片描述][8992654e7d984a8c99b3ec981ed9b12b.png]  
那么问题来了，**先遍历 物品还是先遍历背包重量呢？**

**其实都可以！！ 但是先遍历物品更好理解**。

那么我先给出先遍历物品，然后遍历背包重量的代码。

// weight数组的大小 就是物品个数
    for(int i = 1; i < weight.size(); i++) {
         // 遍历物品
        for(int j = 0; j <= bagweight; j++) {
         // 遍历背包容量
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    
        }
    }

**先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）**

例如这样：

// weight数组的大小 就是物品个数
    for(int j = 0; j <= bagweight; j++) {
         // 遍历背包容量
        for(int i = 1; i < weight.size(); i++) {
         // 遍历物品
            if (j < weight[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
        }
    }

为什么也是可以的呢？

**要理解递归的本质和递推的方向**。

dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]); 递归公式中可以看出dp\[i\]\[j\]是靠dp\[i-1\]\[j\]和dp\[i - 1\]\[j - weight\[i\]\]推导出来的。

dp\[i-1\]\[j\]和dp\[i - 1\]\[j - weight\[i\]\] 都在dp\[i\]\[j\]的左上角方向（包括正上方向），那么先遍历物品，再遍历背包的过程如图所示：  
![在这里插入图片描述][54a0b5e425c648758322142f686a8754.png]  
再来看看先遍历背包，再遍历物品呢，如图：  
![在这里插入图片描述][65e37eb34a684a12bf19d2c345b73604.png]  
**大家可以看出，虽然两个for循环遍历的次序不同，但是dp\[i\]\[j\]所需要的数据就是左上角，根本不影响dp\[i\]\[j\]公式的推导！**

但先遍历物品再遍历背包这个顺序更好理解。

**其实背包问题里，两个for循环的先后循序是非常有讲究的，理解遍历顺序其实比理解推导公式难多了。**

#### 5. 举例推导dp数组 ####

来看一下对应的dp数组的数值，如图：  
![在这里插入图片描述][38f9daa82a38484e99c0cc1c6fc96fb9.png]  
最终结果就是dp\[2\]\[4\]。

## 总结 ##

讲了这么多才刚刚把二维dp的01背包讲完，**这里大家其实可以发现最简单的是推导公式了，推导公式估计看一遍就记下来了，但难就难在如何初始化和遍历顺序上**。

可能有的同学并没有注意到初始化和遍历顺序的重要性，我们后面做力扣上背包面试题目的时候，大家就会感受出来了。

下一篇 还是理论基础，我们再来讲一维dp数组实现的01背包（滚动数组），分析一下和二维有什么区别，在初始化和遍历顺序上又有什么差异。

## 代码实现 ##

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");
            }
        }
    }

**参考资料**：[代码随想录-动态规划：01背包理论基础][-_01]

[10c77a385bce40ac9f65b5c6f0e83e11.png]: https://img-blog.csdnimg.cn/10c77a385bce40ac9f65b5c6f0e83e11.png
[b35515bfad8545859ec52de2e1350cf6.png]: https://img-blog.csdnimg.cn/b35515bfad8545859ec52de2e1350cf6.png
[5a2ea8f40de94c94aed3099e7cc7728b.png]: https://img-blog.csdnimg.cn/5a2ea8f40de94c94aed3099e7cc7728b.png
[c84ef7f351274f4f91f3738b445c2305.png]: https://img-blog.csdnimg.cn/c84ef7f351274f4f91f3738b445c2305.png
[de77d5eba4e3419babcc10d617709575.png]: https://img-blog.csdnimg.cn/de77d5eba4e3419babcc10d617709575.png
[cfecc9bb95e6417bbe436e30909bc3f1.png]: https://img-blog.csdnimg.cn/cfecc9bb95e6417bbe436e30909bc3f1.png
[8992654e7d984a8c99b3ec981ed9b12b.png]: https://img-blog.csdnimg.cn/8992654e7d984a8c99b3ec981ed9b12b.png
[54a0b5e425c648758322142f686a8754.png]: https://img-blog.csdnimg.cn/54a0b5e425c648758322142f686a8754.png
[65e37eb34a684a12bf19d2c345b73604.png]: https://img-blog.csdnimg.cn/65e37eb34a684a12bf19d2c345b73604.png
[38f9daa82a38484e99c0cc1c6fc96fb9.png]: https://img-blog.csdnimg.cn/38f9daa82a38484e99c0cc1c6fc96fb9.png
[-_01]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE