Содержание:
Задача ДП о сдаче с оптимальным количеством монет
Задача о сдаче, как мы с вами убедились, — это типичная задача, решаемая методом динамического программирования.
Повторение
На предыдущем занятии мы решили данную задачу для сдачи размером n.
Мы получили общую рекурсивную формулу для решения задачи с монетами достоинством 1, 3, 5, 10:
Результаты для сдачи F(15) мы разместили в таблице:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Fn | 0 | 1 | 2 | 1 | 2 | 1 | 3 | 2 | 2 | 2 | 1 | 2 | 3 | 2 | 3 | 2 |
Ответ: для сдачи номиналом 15 копеек потребуется минимум 2 монеты.
Определение монет в сдаче
Проблема:
Обычно необходимо знать не только, сколько монет минимум необходимо вернуть, но и какие монеты это будут.
Вычисляя каждую подзадачу, мы получали минимум: либо для 1 копейки, либо для 3, либо для 5, либо для 10 копеек.
Например, вычисляя F(3), мы воспользовались указанной выше формулой. По формуле подошел индикатор для двух решений — n>=1 и n>=3, минимальным из которых оказался равным трем (n>=3):
F(3) = 1 + min[F(3-1), F(3-3)] = 1 + min[F(2), F(0)] = 2 или 0, min = 0
Запишем все минимумы, соответствующие каждому шагу, в таблицу (укажем их в скобках).
В тех случаях, когда минимальными являются несколько решений, возьмем любое из них:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Fn | 0 | 1 | 2 (1) | 1 (3) | 2 (1) | 1 (5) | 3 (1) | 3 (3) | 2 (3) | 3 (3) | 1 (10) | 2 (10) | 3 (1) | 2 (3) | 3 (1) | 2 (5) |
F(12) (для которой минимум возвращаемых монет равняется 3).Для решения этой задачи и пригодится минимум (то есть то число — достоинство монеты (1, 3, 5 или 10), в котором достигался минимум на каждом очередном шаге)
Вопрос задачи: Какие монеты нужны, чтобы вернуть F(12) с помощью трех монет?
Так как минимум для F(12) является 1 копейка (по таблице), то можно начать с 1 копейки:
1
После того, как мы вернули одну копейку, нам остается вернуть 11 копеек. Для этого смотрим в ячейку таблицы с номером 11.
Минимум для F(11) определен в 10 копеек:
10
Остается F(1)
На этом шаге остается вернуть 1 копейку. Смотрим в ячейку для F(1). Минимум определен в 1 копейку:
1
Осталось вернуть 0. Минимум для F(0)=0.
Для того, чтобы вернуть сдачу размером F(12), необходимо минимальное количество монет — 3, эти монеты: 1 копейка, 10 копеек и 1 копейка.
F(15)Формализуем полученное правило в математическую формулу:
У процедуры выбора минимума есть название — argmin f(x), которая возвращает в некоторой точке минимальное значение x для функции f.
Аналогичная функция есть для вычисления максимума — argmax.
Резюме
Динамическое программирование — это техника или метод, позволяющий решать комбинаторные и задачи оптимизации, наделенные определенным свойством.
Алгоритм решения задачи динамического программирования:
- определение целевой функции
- определение начального условия
- определение порядка решения
- вычисление и нахождение общей (рекурсивной) формулы