Занятие 4. Решение задач ДП: возврат сдачи с оптимальным набором монет

Решение задачи динамического программирования о сдаче с оптимальным набором монет

Задача ДП о сдаче с оптимальным количеством монет

Задача о сдаче, как мы с вами убедились, — это типичная задача, решаемая методом динамического программирования.

Повторение

На предыдущем занятии мы решили данную задачу для сдачи размером n.
Мы получили общую рекурсивную формулу для решения задачи с монетами достоинством 1, 3, 5, 10:

Формула для целевой функции задачи про сдачу

Рис. 4.1. Формула для целевой функции задачи про сдачу

Результаты для сдачи 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) с помощью трех монет?

1 шаг:

Так как минимум для F(12) является 1 копейка (по таблице), то можно начать с 1 копейки:

1

2 шаг:

После того, как мы вернули одну копейку, нам остается вернуть 11 копеек. Для этого смотрим в ячейку таблицы с номером 11.
Минимум для F(11) определен в 10 копеек:

10

Остается F(1)

3 шаг:

На этом шаге остается вернуть 1 копейку. Смотрим в ячейку для F(1). Минимум определен в 1 копейку:

1

4 шаг:

Осталось вернуть 0. Минимум для F(0)=0.

Итак, получаем результат:

Для того, чтобы вернуть сдачу размером F(12), необходимо минимальное количество монет — 3, эти монеты: 1 копейка, 10 копеек и 1 копейка.

Задание dp 4_1: определить, какие монеты необходимо вернуть для сдачи номиналом F(15)

Формализуем полученное правило в математическую формулу:
У процедуры выбора минимума есть название — argmin f(x), которая возвращает в некоторой точке минимальное значение x для функции f.

Аналогичная функция есть для вычисления максимума — argmax.

Резюме

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

Алгоритм решения задачи динамического программирования:

  1. определение целевой функции
  2. определение начального условия
  3. определение порядка решения
  4. вычисление и нахождение общей (рекурсивной) формулы
Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*

Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить