0-1背包问题
题目描述
给定n种物品和一个背包,物品i的重量是Wi,其价值为Vi,背包的容量为C。如何选择装入背包的物品,可以使得装入背包中物品的总价值最大?
输入
每组输入包括三行,
第一行包括物品个数n,以及背包容量C。
第二、三行包括两个一维数组,分别为每一种物品的价值和重量。
输出
输出包括两行,第一行为背包的最大总价值,第二行为所选取的物品。
例如:最大总价值=15,物品选取策略为11001。数据保证答案唯一。
样例输入 Copy
5 10
6 3 5 4 6
2 2 6 5 4
样例输出 Copy
15
11001
def knapsack_max_value_and_strategy(v, w, n, c):
m = [[0] * (c + 1) for _ in range(n + 1)]
selected_items = [[0] * (c + 1) for _ in range(n + 1)]
for i in range(n - 1, -1, -1):
for j in range(c + 1):
if j < w[i]:
m[i][j] = m[i + 1][j]
selected_items[i][j] = 0
else:
if m[i + 1][j] > m[i + 1][j - w[i]] + v[i]:
m[i][j] = m[i + 1][j]
selected_items[i][j] = 0
else:
m[i][j] = m[i + 1][j - w[i]] + v[i]
selected_items[i][j] = 1
max_value = m[0][c]
strategy = ""
j = c
for i in range(n):
strategy += str(selected_items[i][j])
j -= w[i] * selected_items[i][j]
return max_value, strategy
while True:
try:
n, c = map(int, input().split())
v = list(map(int, input().split()))
w = list(map(int, input().split()))
max_value, strategy = knapsack_max_value_and_strategy(v, w, n, c)
print(max_value)
print(strategy)
except EOFError:
break
为什么我在oj上运行只有百分之67正确?应该如何修改?