Рекурсия не входит в базовый случай - PullRequest
Новая
       8

Рекурсия не входит в базовый случай

0 голосов
/ 08 февраля 2020

когда я запускаю эту программу, я получаю индекс из-за ошибки диапазона. что я сделал не так, почему не работает 

def knapsack(p, w, capacity, idx):
    if capacity <= 0 or 0 > idx >= len(p):
        return 0
    profit_1 = 0
    if w[idx] <= capacity:
        profit_1 = p[idx] + knapsack(p, w, capacity - w[idx], idx + 1)
    profit_2 = knapsack(p, w, capacity, idx + 1)
    return max(profit_1, profit_2)


p = [31, 26, 72, 17]
w = [3, 1 , 5, 2]

print(knapsack(p, w, 7, 0))

В базовый регистр не входит

Ошибка 

Traceback (most recent call last):
  File "C:/Users/komat/PycharmProjects/DSA/divide&conquer/knapsack.py", line 14, in <module>
    print(knapsack(p, w, 7, 0))
  File "C:/Users/komat/PycharmProjects/DSA/divide&conquer/knapsack.py", line 6, in knapsack
    profit_1 = p[idx] + knapsack(p, w, capacity - w[idx], idx + 1)
  File "C:/Users/komat/PycharmProjects/DSA/divide&conquer/knapsack.py", line 6, in knapsack
    profit_1 = p[idx] + knapsack(p, w, capacity - w[idx], idx + 1)
  File "C:/Users/komat/PycharmProjects/DSA/divide&conquer/knapsack.py", line 7, in knapsack
    profit_2 = knapsack(p, w, capacity, idx + 1)
  File "C:/Users/komat/PycharmProjects/DSA/divide&conquer/knapsack.py", line 6, in knapsack
    profit_1 = p[idx] + knapsack(p, w, capacity - w[idx], idx + 1)
  File "C:/Users/komat/PycharmProjects/DSA/divide&conquer/knapsack.py", line 5, in knapsack
    if w[idx] <= capacity:
IndexError: list index out of range

1 Ответ

0 голосов
/ 08 февраля 2020

Вы делаете idx + 1 в строке profit_1 = p[idx] + knapsack(p, w, capacity - w[idx], idx + 1). В некоторой итерации idx становится 3, а idx + 1 становится 4. Однако длина массивов равна 4, а индекс 4 не будет работать, так как индексирование начинается с 0 и заканчивается на 3. Следовательно, оно разрывается с IndexError.

Попробуйте добавить print (p, w, capacity, idx) в качестве первой строки вашей функции def, и вы будете знать, где она ломается.

...