部分背包问题是经典的01背包问题的扩展,与01背包问题不同的是,在部分背包问题中每个物品的数量并不是固定的1个,而是可以是任意正整数。
- 问题描述:
有一个容量为C的背包,有n个物品,第i个物品的重量为w[i],价值为v[i],数量为s[i]。问该背包最多能装下多少价值的物品。
- 算法思路:
部分背包问题可以转化为多重背包问题求解,将每个物品i拆分为s[i]件相同的物品,便形成了一个有s[i]个物品i的多重背包问题。对每个拆分后的物品i,重量为w[i],价值为v[i]。接下来,我们就可以用多重背包问题的思路去求解。
具体的实现方式有两种:一种是直接基于多重背包问题的常规DP算法进行求解;另一种是“优化建图”的方式,将多重背包问题转化成01背包问题求解,这种方式可以大幅减少DP的时间复杂度,性能更加优异。
- 代码实现:
先介绍基于多重背包问题的常规DP算法实现:
def multi_knapsack(c, w, v, s):
"""
c: 背包容量
w: 物品重量列表
v: 物品价值列表
s: 物品数量列表
"""
# 初始化dp数组
dp = [0] * (c + 1)
# 遍历每个物品
for i in range(len(w)):
# 如果当前物品数量为0,则跳过
if s[i] == 0:
continue
# 多重背包问题的DP过程
for j in range(c, 0, -1):
for k in range(1, s[i] + 1):
if j >= k * w[i]:
dp[j] = max(dp[j], dp[j - k * w[i]] + k * v[i])
else:
break
# 返回dp数组的最后一个元素
return dp[-1]
再介绍一种“优化建图”的方式实现:
def optimized_multi_knapsack(c, w, v, s):
"""
c: 背包容量
w: 物品重量列表
v: 物品价值列表
s: 物品数量列表
"""
# 初始化dp数组
dp = [0] * (c + 1)
# 遍历每个物品
for i in range(len(w)):
# 如果当前物品数量为0,则跳过
if s[i] == 0:
continue
# 将多重背包问题转化为01背包问题
t = 1
while t < s[i]:
for j in range(c, t * w[i] - 1, -1):
dp[j] = max(dp[j], dp[j - t * w[i]] + t * v[i])
s[i] -= t
t *= 2
if s[i] > 0:
for j in range(c, s[i] * w[i] - 1, -1):
dp[j] = max(dp[j], dp[j - s[i] * w[i]] + s[i] * v[i])
# 返回dp数组的最后一个元素
return dp[-1]
- 示例说明:
假设有如下背包问题:
容量为10,物品有5个,分别为:
序号 | 重量 | 数量 | 价值 |
---|---|---|---|
1 | 6 | 3 | 20 |
2 | 4 | 2 | 15 |
3 | 3 | 5 | 10 |
4 | 5 | 1 | 8 |
5 | 2 | 10 | 4 |
使用上面所介绍的两个函数,计算该背包问题的最大价值:
c = 10
w = [6, 4, 3, 5, 2]
v = [20, 15, 10, 8, 4]
s = [3, 2, 5, 1, 10]
print("基于多重背包问题的常规DP算法实现,最大价值为:", multi_knapsack(c, w, v, s))
print("基于\"优化建图\"的方式实现,最大价值为:", optimized_multi_knapsack(c, w, v, s))
输出结果为:
基于多重背包问题的常规DP算法实现,最大价值为: 135
基于"优化建图"的方式实现,最大价值为: 135
通过测试结果可以看出,在本例中两种实现方式的结果都是一样的,因此二者的正确性是等价的。