Python 中背包问题(01背包,完全背包,多重背包)的解决方法
01 背包问题:
题目描述:有一个容量为 C 的背包和 n 个物品,每个物品有一个重量 w 和一个价值 v,要求选择一些物品装入背包,使得装入背包的物品总重量不超过背包容量,并且价值最大。
解决方法:采用动态规划,状态转移方程为:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]),其中dp[i][j]表示前i个物品放入容量为j的背包可以获得的最大价值。
代码演示:
def knapsack01(C, w, v):
n = len(w)
# 初始化背包价值矩阵
dp = [[0 for j in range(C+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, C+1):
if j < w[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])
return dp[n][C]
测试
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
C = 8
print(knapsack01(C, w, v)) # 输出 11
完全背包问题:
题目描述:有一个容量为 C 的背包和 n 个物品,每个物品有一个重量 w 和一个价值 v,要求选择一些物品装入背包,使得装入背包的物品总重量不超过背包容量,并且价值最大,可以无限制地装入每一种物品。
解决方法:仍然采用动态规划,状态转移方程为:dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]),其中dp[i][j]表示前i个物品放入容量为j的背包可以获得的最大价值。
代码演示:
def knapsack_complete(C, w, v):
n = len(w)
# 初始化背包价值矩阵
dp = [[0 for j in range(C+1)] for i in range(n+1)]
for i in range(1, n+1):
for j in range(1, C+1):
if j < w[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1])
return dp[n][C]
测试
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
C = 10
print(knapsack_complete(C, w, v)) # 输出 19
多重背包问题:
题目描述:有一个容量为 C 的背包和 n 个物品,每个物品有一个重量 w 和一个价值 v,每种物品最多可选 s[i] 个,要求选择一些物品装入背包,使得装入背包的物品总重量不超过背包容量,并且价值最大。
解决方法:采用动态规划,并引入二进制优化,将多重背包问题转化为01背包问题。将每种物品拆分成若干件物品,每件物品的重量和价值均为原来物品的重量和价值,然后就可以使用01背包的方法求解。
代码演示:
def knapsack_multi(C, w, v, s):
n = len(w)
# 二进制优化
new_w = []
new_v = []
for i in range(n):
k = 1
while s[i] >= k:
new_w.append(w[i] * k)
new_v.append(v[i] * k)
s[i] -= k
k *= 2
if s[i] > 0:
new_w.append(w[i] * s[i])
new_v.append(v[i] * s[i])
n = len(new_w)
# 初始化背包价值矩阵
dp = [0 for j in range(C+1)]
for i in range(1, n+1):
for j in range(C, new_w[i-1]-1, -1):
dp[j] = max(dp[j], dp[j-new_w[i-1]] + new_v[i-1])
return dp[C]
测试
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
s = [1, 2, 3, 4]
C = 10
print(knapsack_multi(C, w, v, s)) # 输出 38
以上是 Python 中背包问题(01背包,完全背包,多重背包)的解决方法,以及详细的代码演示。
相关文章