我试图编写一个简单的 0-1 背包问题,但遇到了一些错误。帮助将不胜感激。
T = int(input().strip())
def knapsack(n,k,ar):
if n==0 or k==0:
return 0
elif ar[n-1]>k:
return knapsack(n-1,k,ar)
else:
return max(knapsack(n-1,k,ar),ar[n-1] + knapsack(n-1,k-ar[n-1],ar))
for t in range(T):
a = input().strip()
n,k = int(a[0]),int(a[2])
ar = [int(i) for i in input().strip().split(' ')]
print(knapsack(n,k,ar))
我再次运行这个输入
2
3 12
1 6 9
5 9
3 4 4 4 8
我收到错误的输出?我找不到任何错误。提前致谢
输出
1
8
最佳答案
您的算法没问题,但您对函数的输入是错误的。
在第一个输入中,n,k = int(a[0]),int(a[2])
行采用 3
和 1
作为输入而不是 3
和 12
。
我猜你应该使用 list(map(int, input().split()))
来代替,并得到 a[0]
和 a[1]
。
关于python - 我的背包代码输出错误?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39808872/