以下是一个使用动态规划解决背包问题的示例代码:
def knapsack(weight, value, count, max_weight):
n = len(weight)
dp = [[0] * (max_weight + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, max_weight + 1):
if weight[i-1] > j:
dp[i][j] = dp[i-1][j]
else:
# 当前物品有多个,需要考虑数量限制
for k in range(count[i-1] + 1):
if weight[i-1] * k <= j:
dp[i][j] = max(dp[i][j], dp[i-1][j-weight[i-1]*k] + value[i-1]*k)
else:
break
return dp[n][max_weight]
使用示例:
weight = [2, 3, 4] # 物品重量数组
value = [3, 4, 5] # 物品价值数组
count = [1, 2, 3] # 物品数量数组
max_weight = 5 # 背包的最大承重
result = knapsack(weight, value, count, max_weight)
print(result) # 输出最大价值
该代码通过一个二维数组 dp
来保存每个状态下的最优解,其中 dp[i][j]
表示在前 i
个物品中,背包承重为 j
的情况下的最大价值。通过动态规划的原理,不断更新 dp
数组中的值,最终得到最优解。在更新 dp[i][j]
的时候,需要考虑当前物品数量的限制,以保证不超过物品的实际数量。最后返回 dp[n][max_weight]
即为背包问题的最优解。
上一篇:背包问题深度学习