Блог

Я пытался написать простую задачу с рюкзаком 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] .