【动态规划】经典问题第三组---背包问题基础

曾经终败给现在 2023-09-27 17:35 126阅读 0赞

> ## 前言 ##
> 
> 小亭子正在努力的学习编程，接下来将开启算法的学习~~
> 
> 分享的文章都是学习的笔记和感悟，如有不妥之处希望大佬们批评指正~~
> 
> 同时如果本文对你有帮助的话，烦请收藏点赞关注支持一波, 感激不尽~~
> 
> [刷题专栏在这里~~][Link 1]

## 简单介绍一下什么是背包问题： ##

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

每一件物品其实只有两个状态：**取或者不取**

所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。

但是这里我们将详细介绍用动态规划的思想去解题。

> 举个栗子：  
> 背包最大重量为4。  
> 物品为：  
> 重量 | 价值  
> 物品0 1 15  
> 物品1 3 20  
> 物品2 4 30  
> 问背包能背的物品最大价值是多少？
> 
> 以下讲解和图示中出现的数字都是以这个例子为例。

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

> ### 动归五部曲分析： ###
> 
> #### 1.确定dp数组以及下标的含义 ####
> 
> ![15e05e77b54b461a866ceb8cc1c867f0.png][]
> 
> 对于背包问题， 可以使用二维数组，即**dp\[i\]\[j\] ，表示从下标为 0-i 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少**。
> 
> ####  ####
> 
> #### 2.确定递推公式 ####
> 
> 由上图和dp数组的定义可以看出，有两个方向推出来dp\[i\]\[j\]
> 
>  *  **不放物品i**：就是当物品 i 的重量大于背包 j 的重量时，物品 i 无法放进背包中，所以被背包内的价值依然和前面相同，此时dp\[i\]\[j\]就是dp\[i - 1\]\[j\]。**推出公式：dp\[i - 1\]\[j\]**
>  *  **放物品i**：当背包能放下物品 i 的重量时，dp\[i - 1\]\[j - weight\[i\]\] 为背包容量为 j - weight\[i\]的时候不放物品i的最大价值，那么dp\[i - 1\]\[j - weight\[i\]\] + value\[i\] （物品i的价值），就是背包放物品i得到的最大价值，**推出公式**：**dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]**
>  *  最后，dp\[i\]\[j\] 需要在上述两个方向上取出最大值
> 
> 所以递推公式： **dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]);**
> 
> #### 3.dp数组如何初始化 ####
> 
> 首先从dp\[i\]\[j\]的定义出发，如果背包容量j为0的话，即dp\[i\]\[0\]，无论是选取哪些物品，背包价值总和一定为0。
> 
> 然后，由递推公式： **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物品。
> 
> ![20ad690c1873451dba9636d4f18d01dc.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，更方便一些,所以我们把其他位置初始化为0.
> 
> 结果如图：
> 
> ![a5fe8b6d55c7474e80d0cf1e328b1d64.png][]
> 
> ####  ####
> 
> #### 4.确定遍历顺序 ####
> 
> ![b8668e713cd04cf99f368be2222ddfc8.png][]
> 
> 观察上图和递推公式，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\]的左上角方向（包括正上方向），**那么先遍历物品，或者先遍历重量都可以。**
> 
> （我们这里先遍历物品)
> 
> #### 5.举例推导dp数组 ####
> 
> 这一步的作用主要是为了验证一下前面的步骤得出的结果是否符合预期，我个人觉得在前面找公式的时候如果看不出规律也可以先多写几组结果，在观察。
> 
> ![e84788ae3f1e40b6b25f69ace1769c6c.png][]
> 
> #### java代码实现： ####
> 
>     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);
>         }
>     
>        
>         public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){
>     
>             // 创建dp数组
>             int goods = weight.length;  // 获取物品的数量
>             int[][] dp = new int[goods][bagSize + 1];  //这个+1是为了让数组下标和我们需要的下标对齐
>     
>             // 初始化dp数组
>             // 创建数组后，其中默认的值就是0
>             for (int j = weight[0]; j <= bagSize; j++) {
>                 dp[0][j] = value[0];
>             }
>     
>             // 填充dp数组，因为物品和重量的数组下标是从0,开始的，所以这里从下标1开始遍历
>             for (int i = 1; i < weight.length; i++) {
>                 for (int j = 1; j <= bagSize; j++) {
>                     if (j < weight[i]) {
>                         /**
>                          *放不下物品 i 的情况
>                          */
>                         dp[i][j] = dp[i-1][j];
>                     } else {
>                         /**
>                          * 能放下物品 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");
>             }
>         }
>     }

## 一维dp数组（滚动数组） ##

简单介绍下什么是滚动数组：

滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

对于背包问题其实状态都是可以压缩的。

在使用二维数组的时候，递推公式：dp\[i\]\[j\] = max(dp\[i - 1\]\[j\], dp\[i - 1\]\[j - weight\[i\]\] + value\[i\]);

**其实可以发现如果把dp\[i - 1\]\[j\]那一层拷贝到dp\[j\]上，表达式完全可以是：**

**dp\[j\] = max(dp\[j\], dp\[j - weight\[i\]\] + value\[i\] ）**

**dp\[j\] 的含义就是：容量为j的背包，所背的物品价值可以最大为dp\[j\]。**

> ### **动归五部曲分析：** ###
> 
> #### 1.确定dp数组的定义 ####
> 
> 在一维dp数组中，dp\[j\]表示：容量为j的背包，所背的物品价值可以最大为dp\[j\]。
> 
> #### 2.一维dp数组的递推公式 ####
> 
> dp\[j\]可以通过 dp\[j - weight\[i\]\] 推导出来，dp\[j - weight\[i\]\]表示容量为j - weight\[i\]的背包所背的最大价值。
> 
> dp\[j - weight\[i\]\] + value\[i\] ，表示 容量为 j - 物品i重量 的背包 加上 物品 i 的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp\[j\]）
> 
> 此时dp\[j\]有两个选择，一个是取自己dp\[j\] 相当于 二维dp数组中的dp\[i-1\]\[j\]，即不放物品i，
> 
> 另一个是取dp\[j - weight\[i\]\] + value\[i\]，即放物品i，指定是取最大的，毕竟是求最大价值。
> 
> **递推公式：dp\[j\] = max(dp\[j\], dp\[j - weight\[i\]\] + value\[i\] ）**
> 
> #### 3.一维dp数组如何初始化 ####
> 
> dp\[j\]表示：容量为j的背包，所背的物品价值可以最大为dp\[j\]，那么dp\[0\]就应该是0，因为背包容量为0所背的物品的最大价值就是0。
> 
> dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
> 
> **这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了**。
> 
> 那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。
> 
> #### 4.一维dp数组遍历顺序 ####
> 
> 【这一块和二维数组不一样，需要格外注意】
> 
> 使用滚动数组时，我们在遍历背包的时候需要倒序遍历
> 
> 这是为什么呢？
> 
> 举个栗子：
> 
> 物品0的重量weight\[0\] = 1，价值value\[0\] = 15，已经初始化了（dp数组已经都初始化为0）
> 
> 如果正序遍历
> 
> dp\[1\] = dp\[1 - weight\[0\]\] + value\[0\] = 15
> 
> dp\[2\] = dp\[2 - weight\[0\]\] + value\[0\] = 30
> 
> 此时dp\[2\]就已经是30了，意味着物品0，被放入了两次，不符合题目要求
> 
> 倒序就是先算dp\[2\]
> 
> dp\[2\] = dp\[2 - weight\[0\]\] + value\[0\] = 15
> 
> dp\[1\] = dp\[1 - weight\[0\]\] + value\[0\] = 15 （注：dp\[0\] = 0.）
> 
> 所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
> 
> **再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？**
> 
> 答案是：不可以！
> 
> 因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp\[j\]就只会放入一个物品，即：背包里只放入了一个物品。
> 
> **二维数组为什么没有限制？**
> 
> 因为滚动数组需要重复利用（拷贝）上一层的数据
> 
> 而，对于二维dp，dp\[i\]\[j\]都是通过上一层即dp\[i - 1\]\[j\]计算而来，本层的dp\[i\]\[j\]并不会被覆盖
> 
> 【如果还是不理解的话可以写代调试码跑一下观察试试】
> 
> #### 5.举例推导dp数组 ####
> 
> 一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：
> 
> ![324f8669567b42f582a61361f8a9c5db.png][]
> 
> #### java 代码实现： ####
> 
>     public static void main(String[] args) {
>             int[] weight = {1, 3, 4};
>             int[] value = {15, 20, 30};
>             int bagWight = 4;
>             testWeightBagProblem(weight, value, bagWight);
>         }
>     
>         public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
>             int wLen = weight.length;
>             //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
>             int[] dp = new int[bagWeight + 1];
>             //遍历顺序：先遍历物品，再遍历背包容量
>             for (int i = 0; i < wLen; i++){
>                 for (int j = bagWeight; j >= weight[i]; j--){
>                     dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
>                 }
>             }
>             //打印dp数组
>             for (int j = 0; j <= bagWeight; j++){
>                 System.out.print(dp[j] + " ");
>             }
>         }

【本文就到这里了，后面还会持续更新动态规划相关内容，一键三连，一起刷题呀~~】

[Link 1]: http://t.csdn.cn/k3eQU
[15e05e77b54b461a866ceb8cc1c867f0.png]: https://img-blog.csdnimg.cn/15e05e77b54b461a866ceb8cc1c867f0.png
[20ad690c1873451dba9636d4f18d01dc.png]: https://img-blog.csdnimg.cn/20ad690c1873451dba9636d4f18d01dc.png
[a5fe8b6d55c7474e80d0cf1e328b1d64.png]: https://img-blog.csdnimg.cn/a5fe8b6d55c7474e80d0cf1e328b1d64.png
[b8668e713cd04cf99f368be2222ddfc8.png]: https://img-blog.csdnimg.cn/b8668e713cd04cf99f368be2222ddfc8.png
[e84788ae3f1e40b6b25f69ace1769c6c.png]: https://img-blog.csdnimg.cn/e84788ae3f1e40b6b25f69ace1769c6c.png
[324f8669567b42f582a61361f8a9c5db.png]: https://img-blog.csdnimg.cn/324f8669567b42f582a61361f8a9c5db.png