Блог

В книге «Введение в алгоритмы» я пытаюсь реализовать задачу динамического программирования, которая известна как «программа для вырезания стержней». Здесь у меня есть массив, определяющий цену стержней переменной длины. Итак, array {1, 4} определяет, что цена стержня длиной 1 дюйм составляет 1 доллар, а цена стержня длиной 4 также равна 4 долларам. Мне дают входные данные, которые представляют собой длину заданного стержня. Моя цель — разрезать стержень на несколько частей, чтобы длина каждой части оставалась целой, а общая стоимость частей была максимальной.

Вот моя программа

 print("Input Length Prices: ")
p = [int(x) for x in input().split()]

def cut_rod(n):
    if n == 0:
        return 0
    q = -1
    for i in range(1, n 1):
        q = max(q, p[i-1]   cut_rod(n-1))

    return q

print("Input Length to Cut: ")
print(cut_rod(int(input())))

  

Вот мои входные и выходные данные.

Ввод

 1 4
2
  

Вывод

 5 (This is the sum of 1 and 4)
  

Ожидаемый результат

 4
  

Таким образом, вместо максимальной общей цены она дает сумму всех цен длин. Я также попробовал несколько других входных данных. Во всех случаях это дает сумму. Это очень странно.

Редактировать: стержень тоже можно сохранить неразрезанным.

В вашей программе есть две проблемы:

# 1) Вам нужно cut_rod(n-i) , а не cut_rod(n-1) в вашем рекурсивном вызове. Как только вы удалите часть длины i , у вас p-i останется.

# 2) Вы неоднократно вызываете cut_rod рекурсивно, и для больших значений n вы выполняете O(n*n) рекурсивные вызовы. Суть динамического программирования в том, что вы вычисляете значение для меньших результатов, а затем кэшируете их, а не пересчитываете каждый раз, когда они вам нужны.

К счастью, Python упрощает это. Просто аннотируйте свой код с помощью @functools.lru_cache(None)

=== Исправление ===

Я писал выше, что этот код без кэширования был O(n*n) . На самом деле это экспоненциально или хуже. Наивная рекурсивная реализация чисел Фибоначчи экспоненциальна, и это делает только два рекурсивных вызова для каждого аргумента n больше 2; эта программа делает n - 1 .