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

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

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

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

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

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

Сдача	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:   𝜭(2^n/2)

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

𝜭(2⁵⁰⁰)

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

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

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

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

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

Целевая функция 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) = ?

Решение:

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

F(0) = 0

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

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

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

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

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

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

Осталось сказать, как осуществляется переход. Как знание 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 способа и выбрать решение с минимальным результатом.

Таким образом, получаем общую формулу:
F(i) = min из 1+F[i-j], по всем j ∈ 1, 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:

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

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

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) = 1 + min[F(1)] = 1 + 1 = 2

Посчитаем 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) по формуле срабатывает индикатор для двух решений — 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) по формуле срабатывает индикатор для 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) = 1 + min[F(11), F(9), F(7), F(2)] = 2 или 3 или 3 или 2, min = 2
F(12) = 3

Для 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) = 1 + min[F(13), F(11), F(9), F(4)] = 2 или 2 или 3 или 2, min = 2
F(14) = 3

Для 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 монетам.