动态规划 背包问题 Python
时间: 2023-08-15 16:11:51 浏览: 49
背包问题是动态规划中的经典问题之一,它有多种变体,其中最常见的是 0-1 背包问题。下面是一个用 Python 实现的 0-1 背包问题的代码示例:
```python
def knapsack(weights, values, capacity):
n = len(weights)
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]
```
这个函数接受三个参数:weights 是物品的重量列表,values 是物品的价值列表,capacity 是背包的容量。
在函数内部,我们创建了一个二维数组 dp,其中 dp[i][j] 表示在前 i 个物品中,容量为 j 的背包可以获得的最大价值。
然后,我们使用两个嵌套循环遍历物品和背包容量。对于每个物品 i 和每个容量 j,我们有两种选择:
- 如果第 i 个物品的重量 weights[i-1] 大于当前容量 j,则无法将该物品放入背包中,因此 dp[i][j] 等于 dp[i-1][j],即在前 i-1 个物品中的最优解。
- 如果第 i 个物品的重量 weights[i-1] 小于等于当前容量 j,则可以选择将该物品放入背包中,此时的最优解为 dp[i-1][j-weights[i-1]] + values[i-1],即在前 i-1 个物品中容量为 j-weights[i-1] 的背包的最优解加上当前物品的价值。
最后,返回 dp[n][capacity],即在所有物品中容量为 capacity 的背包的最优解,即背包能够获得的最大价值。
这段代码实现了 0-1 背包问题的动态规划解法,可以在给定物品重量、价值和背包容量的情况下,计算出背包能够获得的最大价值。