04. 背包问题知识(四)
04. 背包问题知识(四)
5. 混合背包问题
混合背包问题:有
种物品和一个最多能装重量为 的背包,第 种物品的重量为 ,价值为 ,件数为 。其中:
- 当
时,代表该物品只有 件。 - 当
时,代表该物品有无限件。 - 当
时,代表该物品有 件。 请问在总重量不超过背包载重上限的情况下,能装入背包的最大价值是多少?
思路 1:动态规划
混合背包问题其实就是将「0-1 背包问题」、「完全背包问题」和「多重背包问题」这
其实只要理解了之前讲解的这
并且在「多重背包问题」中,我们曾经使用「二进制优化」的方式,将「多重背包问题」转换为「0-1 背包问题」,那么在解决「混合背包问题」时,我们也可以先将「多重背包问题」转换为「0-1 背包问题」,然后直接再区分是「0-1 背包问题」还是「完全背包问题」就可以了。
思路 1:代码
class Solution:
def mixedPackMethod1(self, weight: [int], value: [int], count: [int], W: int):
weight_new, value_new, count_new = [], [], []
# 二进制优化
for i in range(len(weight)):
cnt = count[i]
# 多重背包问题,转为 0-1 背包问题
if cnt > 0:
k = 1
while k <= cnt:
cnt -= k
weight_new.append(weight[i] * k)
value_new.append(value[i] * k)
count_new.append(1)
k *= 2
if cnt > 0:
weight_new.append(weight[i] * cnt)
value_new.append(value[i] * cnt)
count_new.append(1)
# 0-1 背包问题,直接添加
elif cnt == -1:
weight_new.append(weight[i])
value_new.append(value[i])
count_new.append(1)
# 完全背包问题,标记并添加
else:
weight_new.append(weight[i])
value_new.append(value[i])
count_new.append(0)
dp = [0 for _ in range(W + 1)]
size = len(weight_new)
# 枚举前 i 种物品
for i in range(1, size + 1):
# 0-1 背包问题
if count_new[i - 1] == 1:
# 逆序枚举背包装载重量(避免状态值错误)
for w in range(W, weight_new[i - 1] - 1, -1):
# dp[w] 取「前 i - 1 件物品装入载重为 w 的背包中的最大价值」与「前 i - 1 件物品装入载重为 w - weight_new[i - 1] 的背包中,再装入第 i - 1 物品所得的最大价值」两者中的最大值
dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
# 完全背包问题
else:
# 正序枚举背包装载重量
for w in range(weight_new[i - 1], W + 1):
# dp[w] 取「前 i - 1 种物品装入载重为 w 的背包中的最大价值」与「前 i 种物品装入载重为 w - weight[i - 1] 的背包中,再装入 1 件第 i - 1 种物品所得的最大价值」两者中的最大值
dp[w] = max(dp[w], dp[w - weight_new[i - 1]] + value_new[i - 1])
return dp[W]
思路 1:复杂度分析
- 时间复杂度:
,其中 为背包的载重上限, 是第 种物品的数量。 - 空间复杂度:
。
6. 分组背包问题
分组背包问题:有
组物品和一个最多能装重量为 的背包,第 组物品的件数为 ,第 组的第 个物品重量为 ,价值为 。每组物品中最多只能选择 件物品装入背包。请问在总重量不超过背包载重上限的情况下,能装入背包的最大价值是多少?
6.1 分组背包问题基本思路
思路 1:动态规划 + 二维基本思路
1. 划分阶段
按照物品种类的序号、当前背包的载重上限进行阶段划分。
2. 定义状态
定义状态
状态
3. 状态转移方程
由于我们可以不选择
- 不选择第
组中的任何物品:可以获得的最大价值为 。 - 选择第
组物品中第 件:可以获得的最大价值为 。 - 选择第
组物品中第 件:可以获得的最大价值为 。 - ……
- 选择第
组物品中最后 件:假设 ,则可以获得的最大价值为 。
则状态转移方程为:
4. 初始条件
- 如果背包载重上限为
,则无论选取什么物品,可以获得的最大价值一定是 ,即 。 - 无论背包载重上限是多少,前
组物品所能获得的最大价值一定为 ,即 。
5. 最终结果
根据我们之前定义的状态,
思路 1:代码
class Solution:
# 思路 1:动态规划 + 二维基本思路
def groupPackMethod1(self, group_count: [int], weight: [[int]], value: [[int]], W: int):
size = len(group_count)
dp = [[0 for _ in range(W + 1)] for _ in range(size + 1)]
# 枚举前 i 组物品
for i in range(1, size + 1):
# 枚举背包装载重量
for w in range(W + 1):
# 枚举第 i - 1 组物品能取个数
dp[i][w] = dp[i - 1][w]
for k in range(group_count[i - 1]):
if w >= weight[i - 1][k]:
# dp[i][w] 取所有 dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k] 中最大值
dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1][k]] + value[i - 1][k])
思路 1:复杂度分析
- 时间复杂度:
,其中 为物品分组数量, 为背包的载重上限, 是每组物品的数量。因为 ,所以时间复杂度也可以写成 。 - 空间复杂度:
。
6.2 分组背包问题滚动数组优化
思路 2:动态规划 + 滚动数组优化
1. 划分阶段
按照当前背包的载重上限进行阶段划分。
2. 定义状态
定义状态
3. 状态转移方程
4. 初始条件
- 无论背包载重上限为多少,只要不选择物品,可以获得的最大价值一定是
,即 。
5. 最终结果
根据我们之前定义的状态,
思路 2:代码
class Solution:
# 思路 2:动态规划 + 滚动数组优化
def groupPackMethod2(self, group_count: [int], weight: [[int]], value: [[int]], W: int):
size = len(group_count)
dp = [0 for _ in range(W + 1)]
# 枚举前 i 组物品
for i in range(1, size + 1):
# 逆序枚举背包装载重量
for w in range(W, -1, -1):
# 枚举第 i - 1 组物品能取个数
for k in range(group_count[i - 1]):
if w >= weight[i - 1][k]:
# dp[w] 取所有 dp[w - weight[i - 1][k]] + value[i - 1][k] 中最大值
dp[w] = max(dp[w], dp[w - weight[i - 1][k]] + value[i - 1][k])
return dp[W]
思路 2:复杂度分析
- 时间复杂度:
,其中 为物品分组数量, 为背包的载重上限, 是每组物品的数量。因为 ,所以时间复杂度也可以写成 。 - 空间复杂度:
。
7. 二维费用背包问题
二维费用背包问题:有
件物品和有一个最多能装重量为 、容量为 的背包。第 件物品的重量为 ,体积为 ,价值为 ,每件物品有且只有 件。请问在总重量不超过背包载重上限、容量上限的情况下,能装入背包的最大价值是多少?
7.1 二维费用背包问题基本思路
我们可以参考「0-1 背包问题」的状态定义和基本思路,在「0-1 背包问题」基本思路的基础上,增加一个维度用于表示物品的容量。
思路 1:动态规划 + 三维基本思路
1. 划分阶段
按照物品种类的序号、当前背包的载重上限、容量上限进行阶段划分
2. 定义状态
定义状态
3. 状态转移方程
注意:采用这种「状态定义」和「状态转移方程」,往往会导致内存超出要求限制,所以一般我们会采用「滚动数组」对算法的空间复杂度进行优化。
4. 初始条件
如果背包载重上限为
或者容量上限为 ,则无论选取什么物品,可以获得的最大价值一定是 ,即:无论背包载重上限是多少,前
种物品所能获得的最大价值一定为 ,即:
5. 最终结果
根据我们之前定义的状态,
思路 1:代码
class Solution:
# 思路 1:动态规划 + 三维基本思路
def twoDCostPackMethod1(self, weight: [int], volume: [int], value: [int], W: int, V: int):
size = len(weight)
dp = [[[0 for _ in range(V + 1)] for _ in range(W + 1)] for _ in range(size + 1)]
# 枚举前 i 组物品
for i in range(1, N + 1):
# 枚举背包装载重量
for w in range(W + 1):
# 枚举背包装载容量
for v in range(V + 1):
# 第 i - 1 件物品装不下
if w < weight[i - 1] or v < volume[i - 1]:
# dp[i][w][v] 取「前 i - 1 件物品装入装载重量为 w、装载容量为 v 的背包中的最大价值」
dp[i][w][v] = dp[i - 1][w][v]
else:
# dp[i][w][v] 取所有 dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1] 中最大值
dp[i][w][v] = max(dp[i - 1][w][v], dp[i - 1][w - weight[i - 1]][v - volume[i - 1]] + value[i - 1])
return dp[size][W][V]
思路 1:复杂度分析
- 时间复杂度:
,其中 为物品分组数量, 为背包的载重上限, 为背包的容量上限。 - 空间复杂度:
。
7.2 二维费用背包问题滚动数组优化
思路 2:动态规划 + 滚动数组优化
1. 划分阶段
按照当前背包的载重上限、容量上限进行阶段划分。
2. 定义状态
定义状态
3. 状态转移方程
4. 初始条件
- 如果背包载重上限为
或者容量上限为 ,则无论选取什么物品,可以获得的最大价值一定是 ,即:
5. 最终结果
根据我们之前定义的状态,
思路 2:代码
class Solution:
# 思路 2:动态规划 + 滚动数组优化
def twoDCostPackMethod2(self, weight: [int], volume: [int], value: [int], W: int, V: int):
size = len(weight)
dp = [[0 for _ in range(V + 1)] for _ in range(W + 1)]
# 枚举前 i 组物品
for i in range(1, N + 1):
# 逆序枚举背包装载重量
for w in range(W, weight[i - 1] - 1, -1):
# 逆序枚举背包装载容量
for v in range(V, volume[i - 1] - 1, -1):
# dp[w][v] 取所有 dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1] 中最大值
dp[w][v] = max(dp[w][v], dp[w - weight[i - 1]][v - volume[i - 1]] + value[i - 1])
return dp[W][V]
思路 2:复杂度分析
- 时间复杂度:
,其中 为物品分组数量, 为背包的载重上限, 为背包的容量上限。 - 空间复杂度:
。
参考资料
来源:https://github.com/itcharge/LeetCode-Py