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

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

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

Постановка задачи

Теперь поставим задачу о сдаче по-другому:

Задача:
Определить минимальное количество монет (достоинством 1, 3, 5, 10), необходимое для возврата сдачи размером n. Это и есть целевая функция

Пока не нужно отвечать на вопрос: «Какие именно монеты нужно вернуть?»
Нам просто следует ответить на вопрос: «Сколько монет нужно вернуть? (минимум)»

Рассмотрим сколько нужно монет, чтобы вернуть сдачу определенного размера:

Сдача F
0 0
1 1
2 2
3 минимум = 1 (3 копейки)
4 минимум = 2 (1+3 копейки)
5 минимум = 1 (5 копеек)
6 минимум = 2 (2 решения: 3+3 копейки,5+1 копейки)
...

Итак:
Чтобы вернуть сдачу размера 0, нужно взять: 0 монет по 1 копейки, 0 монет по 3 копейки, 0 монет по 5 копеек, 0 монет по 10 копеек.

Чтобы вернуть сдачу размера 3, нужно взять:

  1. 1 1 1
  2. 3

Минимум равен 1 — т.е. нужно вернуть монету достоинством 3 копейки

Чтобы вернуть сдачу размера 4, нужно взять:

  1. 1 1 1 1
  2. 1 3

Как можно было бы решить эту задачу?

Наивное решение

Наивное решение — это полный перебор.

Алгоритм такой:

Рассмотрим всевозможные способы вернуть сдачу размера n и выбрать тот из них, который использует минимальное количество монет (т.е. то, что уже сделано в таблице, тот же алгоритм)

Проблема: Если нам надо вернуть сдачу размером n, то в общем случае количество способов вернуть сдачу n будет пропорционально 2 в степени n/2 (на сколько делить — зависит от монет, но это уже неважно):

для n:   𝜭(2n/2)

Т.е., если надо вернуть 1000 копеек, то общее количество способов — это 2500

𝜭(2500)

Такое решение не реализуемо даже для достаточно малых n.

Таким образом, такое решение не оптимально и не эффективно. Соответственно, оно нам не подходит.

Жадный алгоритм (матройды)

Жадное решение тоже наивное.

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

Алгоритм решения следующий:

Есть сдача размера n. Мы начнем от нее отнимать число 10 столько раз, пока n не станет меньше 10. Как только n стало меньше 10, будем возвращать уже по 5 копеек, и так продолжать до 1 копейки.

Вроде бы решение эффективное, но проблема в том, что оно неверное. Вернее, оно не всегда верное. И еще точнее: Существуют наборы монет, для которых жадное решение будет давать неверное решение, но существуют и наборы монет, для которых жадное решение дает правильное решение.

Так, для набора монет достоинством 1, 10, 100 копеек жадный алгоритм даст верное решение.

Рассмотрим пример набора монет, когда жадный алгоритм не работает:

Пример: Монеты достоинством 10, 9 и 1 копейка. Нужно вернуть сдачу размером 18:
n = 18

Решение:

  1. 18 - 10 = 8
  2. 8 - 1 - 1 - 1 - 1 - 1 - 1 - 1 - 1 = 0

Т.е. придется отнимать по 1 копейки 8 раз. Но понятно, что оптимальное решение для этой задачи — это 2 монеты по 9 копеек.

Таким образом, мы пока имеем два варианта решения с наивными алгоритмами: один из них не эффективен, а второй — относительно эффективный, но не всегда работает верно.

Задание: Реализовать жадный алгоритм средствами pascal

Решение задачи с помощью динамического программирования

Еще раз вспомним этапы решения задачи ДП:

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

Целевая функция F(n) у нас уже определена из предыдущих решений.
Введем обозначения:

Обозначим через F(n) минимальное количество монет достоинством 1, 3, 5, 10, необходимое для возврата сдачи размера n

F(0) = 0
F(1) = 1
F(3) = 1
F(5) = 3
F(6) = 2 (5+1 или 3+3)
F(n) = ?

 

Решение:

2.

Начнем с самого простого, мы знаем, что

F(0) = 0

Это и будет начальным условием.

В принципе, мы уже знаем и чему равняется F(1), но в общем виде, без частного случая.

3.

Будем получать F(1), исходя из решения F(0), F(2) — исходя из решения F(1) и т.д.

Получаем порядок решения — линейный.

F(0) <- F(1) <- F(2) <- F(3) <- ... <- F(n-1) <- F(n)

Таким образом, решив данную последовательность, в результате получим минимальное количество монет, которое можно вернуть в качестве сдачи номиналом n:

Решение задачи с помощью динамического программирования

Рис. 3.1. Последовательность решения задачи с помощью динамического программирования

4.

Осталось сказать, как осуществляется переход. Как знание F(i) позволяют вычислить F(i+1). Т.е. нам нужно определеить общую формулу (рекурсивную) или правило перехода от решения текущей подзадачи к решению последующей подзадачи.

Посчитаем F(i) для i>=10
Итак, нам нужно вернуть сдачу размера i. F — минимальное количество монет, которое нужно, чтобы вернуть сдачу i.

Если мы для начала вернем сдачу в 1 копейку, то нам останется вернуть F(i-1) копейку.

Т.о., существует 4 способа, чтобы вернуть сдачу i:

  1. можно взять монету достоинством 1, и нам останется вернуть сдачу наминалом F(i-1) минимальным количеством монет;
  2. можно вернуть монету достоинством 3, и нам останется вернуть сдачу наминалом F(i-3) минимальным количеством монет;
  3. можно вернуть монету достоинством 5, и нам останется вернуть сдачу наминалом F(i-5) минимальным количеством монет;
  4. можно вернуть монету достоинством 10, и нам останется вернуть сдачу наминалом F(i-10) минимальным количеством монет.

Получаем:

F(i) = 1 + F(i-1); 1 + F(i-3); 1 + F(i-5); 1 + F(i-10)

Нужно решить все 4 способа и выбрать решение с минимальным результатом.

Нахождение общей формулы для задачи о сдаче

Рис. 3.2. Нахождение общей формулы для задачи о сдаче

Таким образом, получаем общую формулу:
F(i) = min из 1+F[i-j], по всем j1, 3, 5, 10, формула верна для всех i>=10

А F[i-j] на каждом конкретном этапе решения у нас уже есть, т.е. если мы на шаге i, то мы к этому моменту уже просчитали F[i-j].

Или рекурсивная формула для Fn:

F(n) = 1 + min [F(n-1), F(n-3), F(n-5), F(n-10)]

Здесь мы ввели индикатор, который указывает для какого n будет работать формула. Например, формула F(n-10) будет работать только при n>=10:

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

Рис. 3. 3. Формула для целевой функции с индикатором

Как изменится F(i), если i>5 и i<10, то j1, 3, 5
если i>3 и i<5, то j1, 3
если i<3, то j1

Пример: Выполнить задачу о сдаче с минимальном количеством монет для F(15)

Решение:
Подставляем значения в общую формулу:

F(15) = min[1+F(14), 1+F(12), 1+F(10), 1+F(5)]

F(5) у нас уже просчитано (можно сделать это в уме) = 1,
F(10) — тоже в уме = 1
F(12) = ?
F(14) = ?

Рассчитываем F(12) и F(14):
Находим начальное условие (расчитываем в уме количество монет). Получаем, что F(0) = 0; F(1) = 1.

F(2)

F(2) рассчитываем по формуле и получаем:
F(2) = 1 + min[F(1)] = 1 + 1 = 2

F(3)

Посчитаем F(3) по формуле:
Формула для целевой функции

Для F(3) по формуле срабатывает индикатор для двух решений — n>=1 и n>=3, значит получаем:
F(3) = 1 + min[F(3-1), F(3-3)] = 1 + min[F(2), F(0)] = 2 или 0, min = 0
F(3) = 1 + 0 = 1

F(4)

Для F(4) по формуле срабатывает индикатор для двух решений — n>=1 и n>=3, значит получаем:
F(4) = 1 + min[F(4-1), F(4-3)] = 1 + min[F(3), F(1)] = 1 или 1, min = 1
F(4) = 1 + 1 = 2
Или просто в уме просчитали, что сдачу в 4 копейки можно получить, как 3 + 1 копейка, соответственно F(3) + F(1) = 2

F(5)

Для F(5) по формуле срабатывает индикатор для n>=5, значит получаем:
F(5) = 1 + min[F(5-1), F(5-3), F(5-5)] = 1 + min[F(4),F(2),F(0)] = 2 или 2 или 0, min = 0
F(5) = 1 + 0 = 1

F(12)

Аналогично рассчитываем все варианты, например, для F(12) получаем:
F(12) = 1 + min[F(11), F(9), F(7), F(2)] = 2 или 3 или 3 или 2, min = 2
F(12) = 3

F(13)

Для F(13) получаем:
F(13) = 1 + min[F(12), F(10), F(8), F(3)] = 3 или 1 или 2 или 1, min = 1
F(13) = 2

F(14)

Для F(14) получаем:
F(14) = 1 + min[F(13), F(11), F(9), F(4)] = 2 или 2 или 3 или 2, min = 2
F(14) = 3

F(15)

Для F(15) получаем:
F(15) = 1 + min[F(14), F(12), F(10), F(5)] = 3 или 3 или 1 или 1, min = 1
F(15) = 2

В итоге получаем таблицу:

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Fn 0 1 2 1 2 1 2 3 2 3 1 2 3 2 3 2

Таким образом, мы получили ответ на нашу задачу: минимальное количество монет, которое потребуется для того, чтобы отдать сдачу размером 15 копеек, равно 2 монетам, для 14 копеек — 3 монетам.

Ответ: F(15) = 2
Пример задачи динамического программирования

Рис. 3.4. Пример задачи для F(15)

Поделитесь уроком с коллегами и друзьями:

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

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

*
*

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