完全背包问题是经典的动态规划问题之一,它与01背包问题类似,但不同之处在于每个物品可以选择无限次放入背包。下面是使用动态规划解决完全背包问题的Python代码示例:
〓〓python代码如下:〓〓
def knapsack_unbounded(weights, values, capacity):
n = len(weights) # 物品数量
dp = [0] * (capacity + 1) # 动态规划表
# 逐步计算填充动态规划表
for i in range(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 = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
max_value = knapsack_unbounded(weights, values, capacity)
print("背包能够装下的最大价值为:", max_value)
在这段代码中, knapsack_unbounded 函数使用动态规划解决完全背包问题。它接受三个参数: weights 是物品的重量列表, values 是物品的价值列表, capacity 是背包的容量。函数使用一个动态规划表 dp 来记录每个背包容量对应的最大价值。
通过两层循环,逐步填充动态规划表。外层循环遍历背包容量从0到目标容量,内层循环遍历物品列表。对于每个物品,如果其重量不超过当前背包容量,就可以选择将该物品放入背包,并更新当前背包容量下的最大价值。最终,返回动态规划表中背包容量为目标容量时的最大价值。
在示例中,输入的物品重量列表为 [1, 3, 4, 5] ,价值列表为 [1, 4, 5, 7] ,背包容量为 7。经过计算,得到背包能够装下的最大总价值为 9。