给定N件物品和一个容量为V的背包,每件物品有固定的重量Ci和价值Wi。目标是选择若干件物品放入背包中,刚好装满背包,且使得背包中的物品总价值最大。请给出具体的代码
时间: 2024-10-13 10:05:38 浏览: 57
这个问题属于0-1背包问题,它是动态规划的一个经典应用。动态规划通常用于解决最优化问题,其中一个问题的状态可以通过其子状态来构建。以下是使用Python描述的一个简单解决方案:
```python
def knapsack(W, wt, val, n):
# 创建一个二维数组,初始化为负无穷大
K = [[0 for w in range(W+1)] for i in range(n+1)]
# 构建动态规划表
for i in range(1, n+1):
for w in range(1, W+1):
if wt[i-1] <= w:
# 如果物品i可以放入背包且不超出容量
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w])
else:
# 如果物品i无法放入当前背包
K[i][w] = K[i-1][w]
return K[n][W]
# 示例
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
max_value = knapsack(W, wt, val, n)
print("最大价值为:", max_value)
```
在这个代码中,`knapsack`函数接收背包的容量、物品的重量列表、价值列表和物品数量作为输入,然后通过计算每个状态(背包容量w和已考虑的物品数i)的最大价值来填充动态规划表。
阅读全文