Проблема здесь - классическая ситуация c DP, когда жадность может иногда давать оптимальные решения, а иногда нет.
Ситуация в этой задаче аналогична классической c проблеме DP размену монет где мы wi sh, чтобы найти наименьшее количество монет разного достоинства для внесения сдачи с заданной целью. стоимость. Номиналы, доступные в некоторых странах, таких как США (в которых используются монеты достоинством 1, 5, 10, 25, 50, 100), таковы, что оптимально жадно выбирать самую большую монету, пока ее стоимость не упадет ниже ее, а затем перейти к следующая монета. Но с другими наборами номиналов, такими как 1, 3, 4, жадный выбор самого большого значения многократно может привести к неоптимальным результатам.
Точно так же ваше решение отлично работает для одного веса яиц, но не работает для других. Если мы выберем для наших яиц веса 1, 6, 9 и дадим целевой вес 14, алгоритм сразу же выберет 9, а затем не сможет добиться прогресса на 6. В этот момент он проглотит кучу единиц и в конечном итоге думает 6 - минимальное решение. Но это явно неверно: если мы разумно проигнорируем 9 и выберем сначала две шестерки, то сможем достичь желаемого веса всего с 4 яйцами.
Это показывает, что мы должны учитывать тот факт, что в любой момент принятия решения, принятие любого из наших наименований может в конечном итоге привести нас к глобально оптимальному решению. Но в данный момент у нас нет возможности узнать. Итак, мы пробуем каждую деноминацию на каждом этапе. Это очень удобно для рекурсии и может быть записано так:
def dp_make_weight(egg_weights, target_weight):
least_taken = float("inf")
if target_weight == 0:
return 0
elif target_weight > 0:
for weight in egg_weights:
sub_result = dp_make_weight(egg_weights, target_weight - weight)
least_taken = min(least_taken, sub_result)
return least_taken + 1
if __name__ == "__main__":
print(dp_make_weight((1, 6, 9), 14))
Для каждого вызова у нас есть 3 возможности:
- Базовый случай
target_weight < 0: вернуть что-то, чтобы указать решение невозможно (для удобства я использовал бесконечность). - Базовый случай
target_weight == 0: мы нашли возможное решение. Верните 0, чтобы указать, что здесь не было предпринято никаких шагов, и дайте вызывающей стороне базовое значение для увеличения. - Рекурсивный случай
target_weight > 0: попробуйте взять каждый доступный egg_weight, вычтя его из общего числа и рекурсивно исследуя корневой путь в новом состоянии. Изучив все возможные исходы текущего состояния, выберите тот, который сделал наименьшее количество шагов для достижения цели. Добавьте 1, чтобы подсчитать пройденное яйцо на текущем шаге и вернуться.
До сих пор мы видели, что жадное решение неверно и как его исправить, но не мотивировало динамическое c программирование или мемоизация. DP и мемоизация - это чисто оптимизационные концепции, поэтому вы можете добавить их после того, как найдете правильное решение и вам потребуется его ускорить. Сложность приведенного выше решения по времени экспоненциальна: для каждого вызова мы должны вызывать len(egg_weights) рекурсивные вызовы.
Есть много ресурсов, объясняющих DP и мемоизацию , и я уверен, что ваш курс покрывает это, но вкратце, наше рекурсивное решение, показанное выше, повторно вычисляет одни и те же результаты снова и снова, выбирая разные рекурсивные пути, которые в конечном итоге приводят к тем же значениям, которые даются для target_weight. Если мы храним памятку (словарь), в которой результаты каждого вызова хранятся в памяти, то всякий раз, когда мы снова сталкиваемся с вызовом, мы можем искать его результат вместо того, чтобы заново вычислять его с нуля.
def dp_make_weight(egg_weights, target_weight, memo={}):
least_taken = float("inf")
if target_weight == 0:
return 0
elif target_weight in memo:
return memo[target_weight]
elif target_weight > 0:
for weight in egg_weights:
sub_result = dp_make_weight(egg_weights, target_weight - weight)
least_taken = min(least_taken, sub_result)
memo[target_weight] = least_taken + 1
return least_taken + 1
if __name__ == "__main__":
print(dp_make_weight((1, 6, 9, 12, 13, 15), 724)) # => 49
Поскольку мы используем Python, способ "Pythoni c" сделать это, вероятно, заключается в украшении функции. Фактически, есть встроенный мемоизатор под названием lru_cache, поэтому, возвращаясь к нашей исходной функции без какой-либо мемоизации, мы можем добавить мемоизацию (кеширование) с помощью двух строк кода:
from functools import lru_cache
@lru_cache
def dp_make_weight(egg_weights, target_weight):
# ... same code as the top example ...
Запоминание с помощью декоратора имеет обратную сторону увеличения размера стека вызовов пропорционально размеру обертки, поэтому это может увеличить вероятность разрушения стека. Это одна из мотиваций для написания алгоритмов DP итеративно, снизу вверх (то есть начинать с базовых вариантов решения и создавать таблицу этих небольших решений, пока вы не сможете построить глобальное решение), что может быть хорошим упражнением для эта проблема, если вы ищете ее под другим углом.