动态规划 python代码 背包问题
时间: 2023-10-12 11:10:29 浏览: 35
以下是 Python 实现的 0/1 背包问题的动态规划算法:
```python
def knapsack(W, wt, val, n):
K = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for w in range(W + 1):
if i == 0 or w == 0:
K[i][w] = 0
elif wt[i-1] <= w:
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
K[i][w] = K[i-1][w]
return K[n][W]
```
其中,`W` 是背包的容量,`wt` 是每个物品的重量,`val` 是每个物品的价值,`n` 是物品数量。
该算法采用二维数组 `K[i][w]` 来存储子问题的最优解。其中 `i` 表示当前考虑的物品数量,`w` 表示当前背包容量。当 `i` 或 `w` 为 0 时,子问题的最优解显然为 0。当第 `i` 个物品的重量小于等于当前背包容量时,可以选择装入或不装入该物品,取两种情况的最大值;否则,不能装入该物品,子问题的最优解与子问题 `i-1` 的最优解相同。
最终返回的是 `K[n][W]`,即考虑前 `n` 个物品,容量为 `W` 的背包的最优解。