已知有n件物品,物品i的重量为wi、价值为pi,此物品可以有多个。现从中选取一部分物品装入一个背包内,背包最多可容纳的总重量是m,如何选择才能使得物品的总价值最大。为了追求价值最大化,同一物品可以装多件。python实现
时间: 2024-12-08 18:13:27 浏览: 18
这是一个经典的动态规划问题,通常被称为0-1背包问题或者是完全背包问题(每个物品只能取一次),如果允许物品无限次取用,则称为多重背包问题。我们可以使用Python的动态规划算法来解决它。
首先,我们需要创建一个二维数组dp,其中dp[i][j]表示前i个物品能够达到的最大价值,且背包容量为j。对于第i个物品,我们有两种选择:
1. 不选:dp[i][j] = dp[i-1][j]
2. 选:如果wi小于等于j,那么dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + pi)
这里的关键在于判断是否选择当前物品,即是否能放下。最后,dp[n][m]就是所求的最大价值。
以下是简单的Python代码实现:
```python
def knapsack(n, m, w, p):
# 初始化二维数组
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
# 动态规划填充过程
for i in range(1, n+1):
for j in range(1, m+1):
if w[i-1] <= j:
dp[i][j] = max(p[i-1] + dp[i-1][j-w[i-1]], dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
return dp[n][m]
# 示例:
n = 4
w = [10, 20, 30, 40]
p = [60, 100, 120, 200]
m = 50
print(knapsack(n, m, w, p)) # 输出:220 (可以选择物品1,3和4)
```
阅读全文