Алгоритм ранца, странное поведение (python3)

Question

Я работал над рекурсией и пытался решить проблему с ранцем [https://en.wikipedia.org/wiki/Knapsack_problem].. Я придумал приведенный ниже алгоритм, который прекрасно работает:

cost_array = [2,3,4,5,9]
value_array = [3,4,8,8,10]

def KP(Weight, C, V):
    if Weight < 2:
        return 0
    q = 0
    for i in range(len(C)):
        q = max(q, (KP(Weight-C[i], [x for j,x in enumerate(C) if j!=i], \
                [x for j,x in enumerate(V) if j!=i]) + V[i]*(Weight-C[i] >= 0)))
    return q


print(KP(25,cost_array,value_array))

Однако, когда я меняю значениеот q до q < 0 и вызову print(KP(25,cost_array,value_array)) результат, который я получаю 33 - q.Поскольку 33 является максимальным значением, которое может иметь рюкзак.

Что странно, так это то, что я получаю такое поведение, только если вызываю исходную функцию с Weight > 23 и здесь 23=2+3+4+5+9.

Я не могу понять, в какой момент к моему результату добавляется отрицательный q, эта строка никогда не выполняет такую ​​операцию, вы, ребята, можете меня просветить?

q = max(q, (KP(W-C[i], [x for j,x in enumerate(C) if j!=i], [x for j,x in enumerate(V) if j!=i]) + V[i]*(W-C[i] >= 0)))

Спасибо,

д_даррик

Answer 1

Предположим, q=-2 (отрицательное значение). Таким образом, вы заполняете свои базовые случаи -2.То есть -2 возвращается для базовых случаев вашей функции, которая затем добавляется к ответу на каждом этапе рекурсии.Попробуйте подход снизу вверх с 2D-массивом.Вы можете посмотреть на это здесь https://www.youtube.com/watch?v=8LusJS5-AGo.В вашем случае вы заполняете базовые случаи матрицы -2.

def knapSack(W, wt, val, n): 
    K = [[0 for x in range(W+1)] for x in range(n+1)] 

    q=-2 #Make it zero for correct answer

    # Build table K[][] in bottom up manner 
    for i in range(n+1): 
        for w in range(W+1): 
            if i==0 or w==0: 
                K[i][w] = q #Here you are assigning negative value
            elif wt[i-1] <= w: 
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
            else: 
                K[i][w] = K[i-1][w] 

    return K[n][W] 

# Driver program to test above function 
value_array = [3,4,8,8,10]
cost_array =  [2,3,4,5,9]
Weight = 25
n = len(val) 
print(knapSack(Weight, cost_array, value_array, n))