python背包问题递归
时间: 2023-06-19 16:05:36 浏览: 114
背包问题是一个经典的动态规划问题,可以用递归来解决。
假设我们有一个背包,它最多可以装 W 重量的物品。现在有 n 个物品,每个物品的重量为 w[i],价值为 v[i]。我们需要在不超过背包容量的情况下,选择一些物品装进背包中,使得背包中物品的总价值最大。
我们可以定义一个函数 f(i, j),表示考虑前 i 个物品,背包剩余容量为 j 的情况下,可以获得的最大价值。那么,我们可以得到以下递归式:
f(i, j) = 0, (i=0 or j=0)
f(i, j) = f(i-1, j), (j < w[i])
f(i, j) = max(f(i-1, j), f(i-1, j-w[i]) + v[i]), (j >= w[i])
其中,第一行是边界条件,表示当没有物品或者背包容量为 0 时,最大价值为 0。第二行表示当前物品的重量已经超过了背包的容量,所以只能考虑前 i-1 个物品。第三行表示当前物品可以选择或者不选择,如果选择当前物品,那么最大价值就是当前物品的价值加上考虑前 i-1 个物品,背包剩余容量为 j-w[i] 的最大价值。
最终的答案就是 f(n, W)。
下面是一个简单的 Python 代码实现:
```
def knapsack(i, j, w, v):
if i == 0 or j == 0:
return 0
if j < w[i]:
return knapsack(i-1, j, w, v)
else:
return max(knapsack(i-1, j, w, v), knapsack(i-1, j-w[i], w, v) + v[i])
w = [0, 2, 3, 4, 5]
v = [0, 3, 4, 5, 6]
W = 8
n = len(w) - 1
print(knapsack(n, W, w, v)) # 输出 12
```
这个代码中,我们定义了一个函数 knapsack(i, j, w, v),其中 i 表示考虑前 i 个物品,j 表示背包剩余容量,w 和 v 分别表示物品的重量和价值。最终的答案就是 knapsack(n, W, w, v),其中 n 表示物品个数,W 表示背包容量。
阅读全文