有N个物品,每个物品的重量是wi ,每个物品的价值是vi 。 求解当背包容量为W时,能获得的最大价值,并输出获得最大价值时每种物品是否在背包内 数据范围 0 < n <= 30 重量、价值、背包容量均为正整数第二行N个数,依次表示各个物品的是否放在背包里(0表示不放,1表示放),如果有多种方案,取字典序最小的。生成代码
时间: 2024-02-05 07:14:17 浏览: 26
以下是使用动态规划算法求解01背包问题的Python代码:
```python
n, W = map(int, input().split())
w = [0] * (n+1)
v = [0] * (n+1)
for i in range(1, n+1):
wi, vi = map(int, input().split())
w[i] = wi
v[i] = vi
dp = [[0] * (W+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(W+1):
if w[i] > j:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
ans = dp[n][W]
x = [0] * (n+1)
for i in range(n, 0, -1):
if ans == 0:
break
if ans == dp[i-1][W]:
continue
else:
x[i] = 1
ans -= v[i]
W -= w[i]
for i in range(1, n+1):
print(x[i], end=' ')
```
其中,`w[i]`和`v[i]`分别表示第i个物品的重量和价值。`dp[i][j]`表示在前i个物品中选择不超过j重量的物品能获得的最大价值。最后,根据`dp`数组反向推出哪些物品被选中,即可得到方案。