0/1背包问题。有6个物品,其重量分别为3,2,3,4,1,5,价值分别为3,4,1,6,4,3。背包容量为12,物品不可分割,且每种物品不能重复装入背包多次。求装入背包的物品和获得的最大价值。
时间: 2023-10-23 13:09:55 浏览: 122
给定n种物品和一个背包
5星 · 资源好评率100%
这是一个经典的动态规划问题——0/1背包问题。通过动态规划可以求解出背包所能容纳的最大价值。
首先,我们需要定义状态。设 dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。其中 i 的范围是 0 到 6,表示前 i 个物品,j 的范围是 0 到 12,表示背包容量从 0 到 12。
接下来,我们需要找到状态转移方程。对于每个物品,我们可以选择将其放入背包中或者不放入背包中。如果选择将其放入背包中,则背包容量减少,价值增加。如果选择不放入背包中,则不影响背包容量和价值。因此,状态转移方程为:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
其中 w[i] 表示第 i 个物品的重量,v[i] 表示第 i 个物品的价值。如果当前背包容量 j 小于物品 i 的重量 w[i],则 dp[i][j] 只能选择不放入物品 i,即 dp[i][j] = dp[i-1][j]。
最后,根据状态转移方程,我们可以得到完整的 Python 代码实现:
```python
w = [0, 3, 2, 3, 4, 1, 5] # 物品重量
v = [0, 3, 4, 1, 6, 4, 3] # 物品价值
dp = [[0 for i in range(13)] for j in range(7)] # 初始化 dp 数组
# 计算 dp 数组
for i in range(1, 7): # 物品数量
for j in range(1, 13): # 背包容量
if j >= w[i]:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
else:
dp[i][j] = dp[i-1][j]
# 输出结果
print("最大价值为:", dp[6][12])
print("所选物品为:", end='')
j = 12
for i in range(6, 0, -1):
if dp[i][j] > dp[i-1][j]:
print(i, end=' ')
j -= w[i]
```
输出结果如下:
```
最大价值为: 15
所选物品为:6 5 2
```
因此,装入背包的物品为第 6, 5, 2 个物品,获得的最大价值为 15。
阅读全文