当前位置： 首页 > article >正文

算法数据结构——背包问题详解（第四篇）

article 2025/7/3 20:51:41

5. 混合背包问题

混合背包问题：有 $n$ 种物品和一个最多能装重量为 $W$ 的背包，第 $i$ 种物品的重量为 $weight[i]$，价值为 $value[i]$，件数为 $count[i]$。其中：

  1. 当 $count[i] = -1$ 时，代表该物品只有 $1$ 件。

  2. 当 $count[i] = 0$ 时，代表该物品有无限件。

  3. 当 $count[i] > 0$ 时，代表该物品有 $count[i]$ 件。

请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

思路 1：动态规划

混合背包问题其实就是将「0-1 背包问题」、「完全背包问题」和「多重背包问题」这 $3$ 种背包问题综合起来，有的是能取 $1$ 件，有的能取无数件，有的只能取 $count[i]$ 件。

其实只要理解了之前讲解的这 $3$ 种背包问题的核心思想，只要将其合并在一起就可以了。

并且在「多重背包问题」中，我们曾经使用「二进制优化」的方式，将「多重背包问题」转换为「0-1 背包问题」，那么在解决「混合背包问题」时，我们也可以先将「多重背包问题」转换为「0-1 背包问题」，然后直接再区分是「0-1 背包问题」还是「完全背包问题」就可以了。

思路 1：代码

  1. class Solution:
  2.     def mixedPackMethod1(self, weight: [int], value: [int], count: [int], W: int):
  3. weight_new, value_new, count_new = [], [], []
  4.         
  5.         # 二进制优化
  6.         for i in range(len(weight)):
  7. cnt = count[i]
  8.             # 多重背包问题，转为 0-1 背包问题
  9.             if cnt > 0:
  10. k = 1
  11.                 while k <= cnt:
  12. cnt -= k
  13. weight_new.append(weight[i] * k)
  14. value_new.append(value[i] * k)
  15. count_new.append(1)
  16. k *= 2
  17.                 if cnt > 0:
  18. weight_new.append(weight[i] * cnt)
  19. value_new.append(value[i] * cnt)
  20. count_new.append(1)
  21.             # 0-1 背包问题，直接添加
  22.             elif cnt == -1:
  23. weight_new.append(weight[i])
  24. value_new.append(value[i])
  25. count_new.append(1)
  26.             # 完全背包问题，标记并添加
  27.             else:
  28. weight_new.append(weight[i])
  29. value_new.append(value[i])
  30. count_new.append(0)
  31.                 
  32. dp = [0 for _ in range(W + 1)]
  33. size = len(weight_new)
  34.     
  35.         # 枚举前 i 种物品
  36.         for i in range(1, size + 1):
  37.             # 0-1 背包问题
  38.             if count_new[i - 1] == 1:
  39.                 # 逆序枚举背包装载重量（避免状态值错误）
  40.                 for w in range(W, weight_new[i - 1] - 1, -1):
  41.                     # dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight_new[i - 1] 的背包中，再装入第 i - 1 物品所得的最大价值」两者中的最大值
  42. dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
  43.             # 完全背包问题
  44.             else:
  45.                 # 正序枚举背包装载重量
  46.                 for w in range(weight_new[i - 1], W + 1):
  47.                     # dp[w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」与「前 i 种物品装入载重为 w - weight[i - 1] 的背包中，再装入 1 件第 i - 1 种物品所得的最大价值」两者中的最大值
  48. dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
  49.                     
  50.         return dp[W]

思路 1：复杂度分析

  • 时间复杂度：$O(W \times \sum \log_2{count[i]})$，其中 $W$ 为背包的载重上限，$count[i]$ 是第 $i$ 种物品的数量。

  • 空间复杂度：$O(W)$。

6. 分组背包问题

分组背包问题：有 $n$ 组物品和一个最多能装重量为 $W$ 的背包，第 $i$ 组物品的件数为 $group\underline{}count[i]$，第 $i$ 组的第 $j$ 个物品重量为 $weighti$，价值为 $valuei$。每组物品中最多只能选择 $1$ 件物品装入背包。请问在总重量不超过背包载重上限的情况下，能装入背包的最大价值是多少？

6.1 分组背包问题基本思路

思路 1：动态规划 + 二维基本思路

1. 划分阶段

按照物品种类的序号、当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 $dpi$ 表示为：前 $i$ 组物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。

状态 $dpi$ 是一个二维数组，其中第一维代表「当前正在考虑的物品组数」，第二维表示「当前背包的载重上限」，二维数组值表示「可以获得的最大价值」。

3. 状态转移方程

由于我们可以不选择 $i - 1$ 组物品中的任何物品，也可以从第 $i - 1$ 组物品的第 $0 \sim group\underline{}count[i - 1] - 1$ 件物品中随意选择 $1$ 件物品，所以状态 $dpi$ 可能从以下方案中选择最大值：

  1. 不选择第 $i - 1$ 组中的任何物品：可以获得的最大价值为 $dpi - 1$。

  2. 选择第 $i - 1$ 组物品中第 $0$ 件：可以获得的最大价值为 $dpi - 1[0]] + valuei - 1$。

  3. 选择第 $i - 1$ 组物品中第 $1$ 件：可以获得的最大价值为 $dpi - 1[1]] + valuei - 1$。

  4. ……

  5. 选择第 $i - 1$ 组物品中最后 $1$ 件：假设 $k = group\underline{}count[i - 1] - 1$，则可以获得的最大价值为 $dpi - 1[k]] + valuei - 1$。

则状态转移方程为：

$dpi = max \lbrace dpi - 1，dpi - 1[k]] + valuei - 1 \rbrace , \quad 0 \le k \le group\underline{}count[i - 1]$

4. 初始条件

  • 如果背包载重上限为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即 $dpi = 0，0 \le i \le size$。

  • 无论背包载重上限是多少，前 $0$ 组物品所能获得的最大价值一定为 $0$，即 $dp0 = 0，0 \le w \le W$。

5. 最终结果

根据我们之前定义的状态，$dpi$ 表示为：前 $i$ 组物品放入一个最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dpsize$，其中 $size$ 为物品的种类数，$W$ 为背包的载重上限。

思路 1：代码

  1. class Solution:
  2.     # 思路 1：动态规划 + 二维基本思路
  3.     def groupPackMethod1(self, group_count: [int], weight: [[int]], value: [[int]], W: int):
  4. size = len(group_count)
  5. dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
  6.         
  7.         # 枚举前 i 组物品
  8.         for i in range(1, size + 1):
  9.             # 枚举背包装载重量
  10.             for w in range(W + 1):
  11.                 # 枚举第 i - 1 组物品能取个数
  12. dp[i][w] = dp[i - 1][w]
  13.                 for k in range(group_count[i - 1]):
  14.                     if w >= weight[i - 1][k]:
  15.                         # dp[i][w] 取所有 dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k] 中最大值
  16. dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k])

思路 1：复杂度分析

  • 时间复杂度：$O(n \times W \times C)$，其中 $n$ 为物品分组数量，$W$ 为背包的载重上限，$C$ 是每组物品的数量。因为 $n \times C = \sum group\underline{}count[i]$，所以时间复杂度也可以写成 $O(W \times \sum group\underline{}count[i])$。

  • 空间复杂度：$O(n \times W)$。

6.2 分组背包问题滚动数组优化

思路 2：动态规划 + 滚动数组优化

1. 划分阶段

按照当前背包的载重上限进行阶段划分。

2. 定义状态

定义状态 $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。

3. 状态转移方程

$dp[w] = max \lbrace dp[w], \quad dp[w - weighti - 1] + valuei - 1 \rbrace ，\quad 0 \le k \le group\underline{}count[i - 1]$

4. 初始条件

  • 无论背包载重上限为多少，只要不选择物品，可以获得的最大价值一定是 $0$，即 $dp[w] = 0，0 \le w \le W$。

5. 最终结果

根据我们之前定义的状态， $dp[w]$ 表示为：将物品装入最多能装重量为 $w$ 的背包中，可以获得的最大价值。则最终结果为 $dp[W]$，其中 $W$ 为背包的载重上限。

思路 2：代码

  1. class Solution:
  2.     # 思路 2：动态规划 + 滚动数组优化
  3.     def groupPackMethod2(self, group_count: [int], weight: [[int]], value: [[int]], W: int):
  4. size = len(group_count)
  5. dp = [0 for _ in range(W + 1)]
  6.         
  7.         # 枚举前 i 组物品
  8.         for i in range(1, size + 1):
  9.             # 逆序枚举背包装载重量
  10.             for w in range(W, -1, -1):
  11.                 # 枚举第 i - 1 组物品能取个数
  12.                 for k in range(group_count[i - 1]):
  13.                     if w >= weight[i - 1][k]:
  14.                         # dp[w] 取所有 dp[w - weight[i - 1][k]] + value[i - 1][k] 中最大值
  15. dp[w] = max(dp[w], dp[w - weight[i - 1][k]] + value[i - 1][k])
  16.                         
  17.         return dp[W]

思路 2：复杂度分析

  • 时间复杂度：$O(n \times W \times C)$，其中 $n$ 为物品分组数量，$W$ 为背包的载重上限，$C$ 是每组物品的数量。因为 $n \times C = \sum group\underline{}count[i]$，所以时间复杂度也可以写成 $O(W \times \sum group\underline{}count[i])$。

  • 空间复杂度：$O(W)$。

7. 二维费用背包问题

二维费用背包问题：有 $n$ 件物品和有一个最多能装重量为 $W$、容量为 $V$ 的背包。第 $i$ 件物品的重量为 $weight[i]$，体积为 $volume[i]$，价值为 $value[i]$，每件物品有且只有 $1$ 件。请问在总重量不超过背包载重上限、容量上限的情况下，能装入背包的最大价值是多少？

7.1 二维费用背包问题基本思路

我们可以参考「0-1 背包问题」的状态定义和基本思路，在「0-1 背包问题」基本思路的基础上，增加一个维度用于表示物品的容量。

思路 1：动态规划 + 三维基本思路

1. 划分阶段

按照物品种类的序号、当前背包的载重上限、容量上限进行阶段划分

2. 定义状态

定义状态 $dpi[v]$ 为：前 $i$ 件物品放入一个最多能装重量为 $w$、容量为 $v$ 的背包中，可以获得的最大价值。

3. 状态转移方程

$dpi[v] = max(dpi - 1[v], dpi - 1][v - volume[i - 1]] + value[i - 1]), \quad 0 \le weight[i - 1] \le w, 0 \le volume[i - 1] \le v$

注意：采用这种「状态定义」和「状态转移方程」，往往会导致内存超出要求限制，所以一般我们会采用「滚动数组」对算法的空间复杂度进行优化。

4. 初始条件

  • 如果背包载重上限为 $0$ 或者容量上限为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即：

    • $dpi[0] = 0，0 \le i \le size，0 \le w \le W$

    • $dpi[v] = 0，0 \le i \le size，0 \le v \le V$

  • 无论背包载重上限是多少，前 $0$ 种物品所能获得的最大价值一定为 $0$，即：

    • $dp0[v] = 0，0 \le w \le W，0 \le v \le V$

5. 最终结果

根据我们之前定义的状态， $dpi[v]$ 表示为：前 $i$ 件物品放入一个最多能装重量为 $w$、容量为 $v$ 的背包中，可以获得的最大价值。则最终结果为 $dpsize[V]$，其中 $size$ 为物品的种类数，$W$ 为背包的载重上限，$V$ 为背包的容量上限。

思路 1：代码

  1. class Solution:
  2.     # 思路 1：动态规划 + 三维基本思路
  3.     def twoDCostPackMethod1(self, weight: [int], volume: [int], value: [int], W: int, V: int):
  4. size = len(weight)
  5. dp = [[[0 for _ in range(V + 1)] for _ in range(W + 1)] for _ in range(size + 1)]
  6.     
  7.         # 枚举前 i 组物品
  8.         for i in range(1, N + 1):
  9.             # 枚举背包装载重量
  10.             for w in range(W + 1):
  11.                 # 枚举背包装载容量
  12.                 for v in range(V + 1):
  13.                     # 第 i - 1 件物品装不下
  14.                     if w < weight[i - 1] or v < volume[i - 1]:
  15.                         # dp[i][w][v] 取「前 i - 1 件物品装入装载重量为 w、装载容量为 v 的背包中的最大价值」
  16. dp[i][w][v] = dp[i - 1][w][v]
  17.                     else:
  18.                         # dp[i][w][v] 取所有 dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1] 中最大值
  19. dp[i][w][v] = max(dp[i - 1][w][v], dp[i - 1][w - weight[i - 1]][v - volume[i - 1]] + value[i - 1])
  20.                         
  21.         return dp[size][W][V]

思路 1：复杂度分析

  • 时间复杂度：$O(n \times W \times V)$，其中 $n$ 为物品分组数量，$W$ 为背包的载重上限，$V$ 为背包的容量上限。

  • 空间复杂度：$O(n \times W \times V)$。

7.2 二维费用背包问题滚动数组优化

思路 2：动态规划 + 滚动数组优化

1. 划分阶段

按照当前背包的载重上限、容量上限进行阶段划分。

2. 定义状态

定义状态 $dpw$ 表示为：将物品装入最多能装重量为 $w$、容量为 $v$ 的背包中，可以获得的最大价值。

3. 状态转移方程

$dpw = max \lbrace dpw, \quad dpw - weight[i - 1]] + value[i - 1] \rbrace , \quad 0 \le weight[i - 1] \le w, 0 \le volume[i - 1] \le v$

4. 初始条件

  • 如果背包载重上限为 $0$ 或者容量上限为 $0$，则无论选取什么物品，可以获得的最大价值一定是 $0$，即：

    • $dpw = 0，0 \le w \le W$

    • $dp0 = 0，0 \le v \le V$

5. 最终结果

根据我们之前定义的状态， $dpw$ 表示为：将物品装入最多能装重量为 $w$、容量为 $v$ 的背包中，可以获得的最大价值。则最终结果为 $dpW$，其中 $W$ 为背包的载重上限，$V$ 为背包的容量上限。

思路 2：代码

  1. class Solution:        
  2.     # 思路 2：动态规划 + 滚动数组优化
  3.     def twoDCostPackMethod2(self, weight: [int], volume: [int], value: [int], W: int, V: int):
  4. size = len(weight)
  5. dp = [[0 for _ in range(V + 1)] for _ in range(W + 1)]
  6.         
  7.         # 枚举前 i 组物品
  8.         for i in range(1, N + 1):
  9.             # 逆序枚举背包装载重量
  10.             for w in range(W, weight[i - 1] - 1, -1):
  11.                 # 逆序枚举背包装载容量
  12.                 for v in range(V, volume[i - 1] - 1, -1):
  13.                     # dp[w][v] 取所有 dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1] 中最大值
  14. dp[w][v] = max(dp[w][v], dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1])
  15.                     
  16.         return dp[W][V]

思路 2：复杂度分析

  • 时间复杂度：$O(n \times W \times V)$，其中 $n$ 为物品分组数量，$W$ 为背包的载重上限，$V$ 为背包的容量上限。

  • 空间复杂度：$O(W \times V)$。

http://www.lryc.cn/news/2419938.html

相关文章：

  • 五分钟学会搭建web网站
  • 手把手教你搭建自己的个人博客（图文教程）
  • 9大代理服务器软件的比较与分析
  • 海外电商平台开发流程
  • Milvus的向量索引（内存索引）
  • 【转】3gpp和3gpp2
  • 浏览器HTTP_USER_AGENT汇总——Firefox、Chrome、IE9、IE8、IE7、IE6
  • 软件质量管理体系_软件质量管理概述
  • 个人站长三次网站备案的经历及经验总结
  • 基于智能移动设备的IP电话软件的设计与实现
  • 83102 三种常见网络协议
  • 第二学期无人机操作师结业复习测试
  • OpenFeign不支持{}特殊字符的header解决
  • c语言中pause的作用,c++中的system(pause)的作用和含义解析
  • 微信小程序_介绍
  • 非诚勿扰又来一男程序员
  • 深度全方位盘点你眼中的IT行业现状与未来趋势
  • BZOJ 2462 BeiJing 2011 矩阵模板 二维hash
  • 2023计算机毕业设计SSM最新选题之java体育运动兴趣社区系统8bisy
  • CSS3：3D移动translate3d及3D转换透视效果perspective
  • 分布式系统架构网络之IDC机房
  • 靶向代谢组
  • 【UWB 定位】高精度定位
  • js获取数组长度-length属性的介绍
  • 专访 SphereEx 创始团队：获数百万美金投资，接棒 ShardingSphere 打造全新分布式生态
  • SpringBoot+Flowable 完美结合，优雅实现工作流！
  • EWSA破解WPA无线密码具体图文教程
  • 抓取静态网页数据
  • Hyperledger Fabric2.3 环境搭建及Fabric 测试网络使用
  • 初步了解SequoiaDB数据库