有一个背包的最大能承受的重量是 M ,有 n 个物品,每个物品有各自的重量和价值,计算在不超出背包最大承重限制下,背包中物品最大价值可以是多少?
时间: 2024-05-10 11:18:18 浏览: 25
这是一个经典的动态规划问题,通常被称为 01 背包问题。
我们可以使用一个二维数组 dp[i][j] 表示前 i 个物品放入一个容量为 j 的背包可以获得的最大价值。状态转移方程为:
- 当第 i 个物品的重量大于当前背包的容量 j 时,不放入第 i 个物品,此时最大价值为 dp[i-1][j]。
- 当第 i 个物品的重量小于等于当前背包的容量 j 时,可以选择放入或者不放入第 i 个物品,取两者中的最大值,即:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
其中 w[i] 表示第 i 个物品的重量,v[i] 表示第 i 个物品的价值。
最终的结果即为 dp[n][M]。
以下是 Python 代码示例:
```python
def knapsack(weights, values, M):
n = len(weights)
dp = [[0] * (M+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, M+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][M]
```
其中 weights 和 values 分别为物品的重量和价值列表,M 为背包最大承重。