0-1背包问题(python)
题目描述
XP每天都会思考一个问题,今天午餐去哪里吃?这是一个很重要的问题,这会影响到他下午的体力值。他的午餐预算是M元,现在有N种菜品,每一种菜品的价格和能够提供的体力值已知(每种菜品只能选择一次),请问如何选择菜品能够让XP下午的体力值最大呢?
输入
多组输入
第一行:M元和菜品数量N。
接下来N行,每一行两个整数,分别表示每一种菜品的价格(vi)和能够获得的体力值(wi)。
(0<N<=20,0<=M<=1000)(0<=vi<=50,0<=wi<=100)
输出
最大体力值。
样例输入 Copy
10 5
1 5
2 4
3 3
4 2
5 1
样例输出 Copy
14
我的代码为什么在oj上提交是百分之50正确,百分之50错误?
while True:
try:
c,n= list(map(int, input().split()))
v=[]
w=[]
for i in range(n):
thing=list(map(int,input().split()))
v.append(thing[0])
w.append(thing[1])
dp = [[0 for i in range(c + 1)] for i in range(n + 1)]
w.insert(0, 0)
v.insert(0, 0)
for i in range(1, n + 1):
for j in range(1, c + 1):
if w[i] <= j:
if dp[i - 1][j] < dp[i - 1][j - w[i]] + v[i]:
dp[i][j] = dp[i - 1][j - w[i]] + v[i]
else:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
print(dp[n][c])
except EOFError:
break