Изменения: динамическое программирование

Question

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

Пример этого был приведен ниже:

Мы хотим достичь n = 14и у нас есть три монеты разных ценностей: d1 = 1,d2 = 7,d3 = 10,

Используя жадный подход, это заставило бы нас сделать 10 + 1 + 1 + 1 + 1 (5 монет).

Было сказано, что динамический подход к проблеме решит это точно. Я пытался решить это, но он вернулся к 5.

Предположим, F содержит количество монет, необходимое для получения суммы

F[14] = min {F[14 – 1] , F[14 – 7],  F[14 – 10]} + 1

      = F[14 – 10] + 1 = 4 + 1 = 5

Это еще раз показывает, что нам нужно 5 монет, когда это явно можно сделать, используя 2 монеты (7 + 7).

Что дает? Благодарю.

Answer 1

Вы предполагали, что min {F[14 – 1] , F[14 – 7], F[14 – 10]}=F[14-10] когда это не так. Минимум на самом деле F[14-7]=1 и, следовательно, оптимальный 2