边缘添加算法是解决0/1背包问题的一种常用方法。下面是一个使用动态规划实现边缘添加算法的Python代码示例:
def knapsack(values, weights, capacity):
n = len(values)
# 创建一个二维数组来保存子问题的解
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
# 如果当前物品的重量大于背包容量,则无法放入背包
if weights[i - 1] > j:
dp[i][j] = dp[i - 1][j]
else:
# 边缘添加的核心步骤
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
# 返回最优解
return dp[n][capacity]
这段代码中,values
是物品的价值列表,weights
是物品的重量列表,capacity
是背包的容量。函数knapsack
返回背包中可以放入的物品的最大总价值。
这个算法的时间复杂度是O(n * C),其中n是物品的个数,C是背包的容量。