李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
GO
正文
golang算法篇之0-1背包算法介绍
Leefs
2024-04-06 PM
368℃
0条
[TOC] ### 前言 本篇是基于《代码随想录》加上自己做题时的一些思考整理出来的。希望对大家理解0-1背包问题有所帮助。 ### 一、0-1背包问题引入 + **问题描述**： 给定一组物品，每个物品都有自己的重量和价值，以及一个固定的容量的背包。目标是找到一个最佳的组合，使得放入背包的物品的总重量不超过背包容量，且总价值最大。 + **基本思想**： 将问题划分为若干个子问题，通过解决子问题得到原问题的最优解。对于每个物品，可以选择**放入背包**或**不放入背包**，从而形成递归结构。 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。**每件物品只能用一次**，求解将哪些物品装入背包里物品价值总和最大。  上方示例是标准的背包问题。 ### 二、示例 + **有如下三个物品**： | | 重量 | 价值 | | ----- | ---- | ---- | | 物品0 | 1 | 15 | | 物品1 | 3 | 20 | | 物品2 | 4 | 30 | + 背包最大重量为4。 + 问背包能背的物品最大价值是多少？ 以下讲解和图示中出现的数字都是以这个例子为例。 ### 三、二维dp数组0-1背包 #### 3.1 动规五部曲 **1. 确定dp数组以及下标的含义** + **`dp[i][j]` 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少**。 通过下方的表格来进行说明会显得更加直观。  如果此时背包重量是4，则可以产生如下情况： + 刚好放进入物品2，测试背包的价值是30 + 也可以同时放入物品0和物品1，两个物品，所产生的价值为15+20=35，比只放入物品2产生的价值大。 即`dp[2][4]=35`,暂时不理解也没关系，继续向下看 **2. 确定递推公式** 通过上方dp数组的含义，可以想出`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数组的定义吻合，否则到递推公式的时候就会越来越乱**。 + **情况一：背包容量为0，即：j = 0,`dp[i][0]`** 无论是选取哪些物品，背包价值总和一定为0。如下图所示：  + **情况二：对只取物品0进行初始化，即，i = 0,`dp[0][j]`** 首先大家可以有一个问题，为什么一定要对 i = 0进行初始化？ 我们在一起看状态转移方程： `dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);` 从方程中可以看出，i 是由 i-1 推导出来，也就是说在后续物品遍历中，i一定不能从0开始遍历，那么 i 为 0 的时候就一定要初始化。 初始化过程： `dp[0][j]`，即：i 为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。 + 当 `j < weight[0]`的时候，`dp[0][j]` 应该是 0，因为背包容量比编号0的物品重量还小（物品0放不下）。 + 当`j >= weight[0]`时，`dp[0][j]` 应该是value[0]，因为背包容量足够放编号0物品。 代码初始化如下： ```go for (int j = 0 ; j < weight[0]; j++) { // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略。 dp[0][j] = 0; } // 正序遍历 // 只对背包容量可以装入物品0开始的后续值进行初始化 for (int j = weight[0]; j <= bagweight; j++) { dp[0][j] = value[0]; } ``` 此时dp数组初始化情况如图所示：  这里默认系统空间初始值都是0。 **4. 确定遍历顺序** 在如下图中，可以看出，有两个遍历的维度：**物品**与**背包重量**  + **先遍历物品，再遍历背包重量** 从上方递归公式中可以看出`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]`的左上角方向（包括正上方向）  + 代码示例 ```go // 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]); } } ``` + **先遍历背包，再遍历物品**  ```go // 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]); } } ``` **大家可以看出，虽然两个for循环遍历的次序不同，但是`dp[i][j]`所需要的数据就是左上角，根本不影响`dp[i][j]`公式的推导** **5. 举例推导dp数组** 来看一下对应的dp数组的数值  最终结果就是`dp[2][4]`。 #### 3.2 代码实现 ```go func test_2_wei_bag_problem1(weight, value []int, bagweight int) int { // 定义 dp 数组 dp := make([][]int, len(weight)) for i, _ := range dp { dp[i] = make([]int, bagweight+1) } // 初始化 // 创建数组后，其中默认的值就是0 // j < weight[0] 已在上方被初始化为0 // j >= weight[0] 的值就初始化为 value[0] for j := bagweight; j >= weight[0]; j-- { dp[0][j] = dp[0][j-weight[0]] + value[0] } fmt.Println("打印初始化后的dp数组:") for _, num := range dp { fmt.Println(num) } // 递推公式 // weight数组的大小 就是物品个数 for i := 1; i < len(weight); i++ { // 遍历物品 // 正序 for j := 0; j <= bagweight; j++ { // 遍历背包容量 // 如果装不下这个物品,那么就继承dp[i - 1][j]的值 if j < weight[i] { dp[i][j] = dp[i-1][j] } else { /** * 当前背包的容量可以放下物品i * 那么此时分两种情况： * 1、不放物品i * 2、放物品i * 比较这两种情况下，哪种背包中物品的最大价值最大 */ // 如果能装下,就将值更新为不装这个物品的最大值和装这个物品的最大值中的最大值 // 装这个物品的最大值由容量为j - weight[i]的包任意放入序号为[0, i - 1]的最大值 + 该物品的价值构成 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]) } } } fmt.Println("打印填充后的dp数组:") for _, num := range dp { fmt.Println(num) } return dp[len(weight)-1][bagweight] } func max(a, b int) int { if a > b { return a } return b } func main() { weight := []int{1, 3, 4} value := []int{15, 20, 30} num := test_2_wei_bag_problem1(weight, value, 4) fmt.Println(num) } ``` **输出结果** ``` 打印初始化后的dp数组: [0 15 15 15 15] [0 0 0 0 0] [0 0 0 0 0] 打印填充后的dp数组: [0 15 15 15 15] [0 15 15 20 35] [0 15 15 20 35] 35 ``` ### 四、一维dp数组0-1背包 #### 4.1 压缩二维数组 在使用二维数组的时候，递推公式：`dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])`; **其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：`dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])`;** **与其把`dp[i - 1]`这一层拷贝到`dp[i]`上，不如只用一个一维数组了**，只用`dp[j]`（一维数组，也可以理解是一个滚动数组）。 这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。 #### 4.2 动规五部曲 **1. 确定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，指定是取最大的。 + **递推公式** ```go dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ``` 可以看出相对于二维dp数组的写法，就是把dp[i][j]中i的维度去掉了。 **3. 一维dp数组如何初始化** `dp[j]`表示：容量为 j 的背包，所背的物品价值可以最大为`dp[j]`，那么`dp[0]`就应该是0，因为背包容量为0所背的物品的最大价值就是0。 那么dp数组除了下标0的位置，初始为0，其他下标应该初始化多少呢？ 看一下递归公式：`dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);` dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。 **这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了**。 那么我假设物品价值都是大于0的，所以dp数组初始化的时候，都初始为0就可以了。 **4. 一维dp数组遍历顺序** **示例代码** ```go for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } } ``` 从上方的代码中大家心中可能会产生两个疑问。 + **问题一：对背包的遍历顺序为什么是倒序的？** **结论**：**倒序遍历是为了保证物品 i 只被放入一次！**。但如果一旦正序遍历了，那么物品0就会被重复加入多次！ **举例说明** 物品0的重量`weight[0] = 1`，价值`value[0] = 15` 如果正序遍历 + `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 - weight[0]] + value[0] = 15` （dp数组已经都初始化为0） + `dp[1] = dp[1 - weight[0]] + value[0] = 15` 所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。 **那么问题又来了，为什么二维dp数组遍历的时候不用倒序呢？** 因为对于二维dp，`dp[i][j]`都是通过上一层即`dp[i - 1][j]`计算而来，本层的`dp[i][j]`并不会被覆盖！ + **问题二：可不可以先遍历背包容量嵌套遍历物品呢？** 不可以! 因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个`dp[j]`就只会放入一个物品，即：背包里只放入了一个物品。 倒序遍历的原因是，本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。 **所以一维dp数组的背包在遍历顺序上和二维其实是有很大差异的！** **5. 举例推导dp数组** 一维dp，分别用物品0，物品1，物品2 来遍历背包，最终得到结果如下：  #### 4.3 代码实现 ```go func test_1_wei_bag_problem(weight, value []int, bagWeight int) int { // 定义 dp 和初始化 dp := make([]int, bagWeight+1) fmt.Println("打印初始化后的dp数组:") fmt.Println(dp) fmt.Println("打印填充后的dp数组:") // 递推顺序 for i := 0; i < len(weight); i++ { // 遍历物品 // 这里必须倒序,区别二维,因为二维 dp 保存了 i 的状态 for j := bagWeight; j >= weight[i]; j-- { // 遍历背包容量 // 递推公式 dp[j] = max3and(dp[j], dp[j-weight[i]]+value[i]) } // 打印 dp 数组 fmt.Println(dp) } return dp[bagWeight] } func max3and(a, b int) int { if a > b { return a } return b } func main() { weight := []int{1, 3, 4} // 物品价值 value := []int{15, 20, 30} // 物品重量 bagWeight := 4 num := test_1_wei_bag_problem(weight, value, bagWeight) fmt.Println(num) } ``` **运行结果** ``` 打印初始化后的dp数组: [0 0 0 0 0] 打印填充后的dp数组: [0 15 15 15 15] [0 15 15 20 35] [0 15 15 20 35] 35 ```
标签:
Golang
非特殊说明，本博所有文章均为博主原创。
如若转载，请注明出处：
https://lilinchao.com/archives/2908.html
上一篇
golang算法篇之kmp算法介绍
下一篇
没有了
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
锁
Azkaban
二叉树
DataX
随笔
并发线程
LeetCode刷题
数据结构和算法
Java编程思想
数据结构
Shiro
Java阻塞队列
MyBatisX
MyBatis
工具
容器深入研究
散列
Ubuntu
gorm
Elastisearch
Flink
数学
Beego
Java工具类
Flume
Http
高并发
链表
Spark SQL
Sentinel
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞