下面是使用动态规划解决完全背包问题的Python代码示例:
〓〓python代码如下:〓〓
def knapsack_unbounded(weights, values, capacity):
n = len(weights) # 物品数量
dp = [0] * (capacity + 1) # 动态规划表
# 逐步计算填充动态规划表
for i in range(1, capacity + 1):
for j in range(n):
if weights[j] <= i:
dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
return dp[capacity]
# 示例用法
weights = [2, 3, 4, 5] # 物品重量列表
values = [3, 4, 5, 6] # 物品价值列表
capacity = 7 # 背包容量
max_value = knapsack_unbounded(weights, values, capacity)
print("背包能够装下的最大价值为:", max_value)
在这段代码中, knapsack_unbounded 函数使用动态规划解决完全背包问题。它接受三个参数: weights 是物品的重量列表, values 是物品的价值列表, capacity 是背包的容量。
函数使用一维动态规划表 dp 来记录每个背包容量对应的最大价值。通过两层循环,逐步填充动态规划表。外层循环遍历背包容量,内层循环遍历物品列表。对于每个背包容量和物品,可以选择将该物品放入背包的数目为 i // weights[j] (即不限次数地放入物品),然后计算放入该物品和不放入该物品两种情况下的最大价值,并取较大的一个。
最终,返回动态规划表中最后一个位置的值,即表示在给定背包容量下的最大总价值。
在示例中,输入的物品重量列表为 [2, 3, 4, 5] ,价值列表为 [3, 4, 5, 6] ,背包容量为 7。经过计算,得到背包能够装下的最大总价值为 9。