Сдача
Как нам уже известно, естественный «жадный» подход к этой задаче работает неправильно при любом наборе номиналов. Например, при номиналах , и «жадный» алгоритм разменяет центов тремя монетами (), хотя это возможно сделать всего лишь двумя (). Ваша цель — использовать динамическое программирование для решения задачи «Сдача» с номиналами , и .
- Входные данные: Целое число .
- Выходные данные: Минимальное количество монет номиналами , , , чтобы выдать сдачу с .
- Ограничения: .
Пример 1
|
Ввод |
Вывод |
|
34 |
9 |
- .
Для оптимального варианта сдачи с необходимо семь монет. Рассмотрим произвольный поднабор оптимального решения — например, если сложить четыре монеты из приведённого ниже прямоугольника, то получится .
💡 Остановитесь и подумайте:
Сможете разменять центов тремя монетами?
Ответ на этот вопрос: «Нет». Если бы размен был возможен тремя монетами, то можно было бы заменить выделенные четыре монеты и получить сдачу с шестью монетами, а не семью.
Такая ситуация показывает нам важную особенность динамического программирования — решение задачи содержит решения всех её мелких подзадач.
Эта особенность позволяет найти решение задачи, сначала выполняя мелкие подзадачи.
Пусть — это минимальное количество монет номиналами , и , которые нужны для сдачи с , а — оптимальная сдача с . В таком случае
Тогда
Следовательно, . Таким образом, для решения задачи при достаточно решить её при и добавить единицу.
💡 Остановитесь и подумайте:
Мы закончили?
Проблема в том, что мы не знаем значение . Тем не менее мы знаем, что равняется или , или , или . Так равно одному из следующих вариантов: , и .
Так как мы ищем оптимальный способ выдать сдачу, равно минимальному из этих трёх выражений. В итоге мы получаем следующее рекуррентное соотношение:
При небольших аргументах это соотношение выражает значение рекурсивным образом через собственные значения. Для такой нисходящей рекурсии нам необходимо указать базовый случай. У нас это будет : .
Уравнение выше — самая важная часть алгоритма динамического программирования, так как из него легко сделать рекурсивный алгоритм.
1Change(money):
2 if money=0:
3 return 0
4 else:
5 result = +infinity
6 for c=1,3,4:
7 if c <= money:
8 result = min(result,1+Change(money-c))
9 return result
У этого алгоритма есть серьёзная проблема: он становится крайне медленным, потому что вызывает Change(money) снова и снова для одного и того же значения .
Мемоизация — стандартный способ избежать этого: при вычислении Change(money) мы можем использовать сохранение в таблице и тогда нам не придётся делать перевычисление.
1table=associative array
2
3Change(money):
4 if table[money] is not yet computed:
5 if money=0:
6 table[money]←0
7 else:
8 result = +infinity
9 for c=1,3,4:
10 if c <= money:
11 result = min(result,1+Change(money-c))
12 table[money] = result
13 return table[money]
На практике такой алгоритм уже достаточно хорош, хотя у него есть проблемы с эффективностью: рекурсивные вызовы и уточняющие запросы для ассоциативного массива приводят к замедлению. Заметив, что все вычисляемые значения — это последовательные целые числа, мы можем реализовать улучшенный подход, в котором используется массив для хранения решений всех задач.
1Change(money):
2 table[0..money] = [+infinity,…,+infinity]
3 table[0] = 0
4
5 for m from 1 to money:
6 for c=1,3,4:
7 if c <= m:
8 table[m] = min(table[m],1+table[m-c])
9 return table[money]
Время выполнения этого алгоритма составляет , так как каждая итерация внешнего цикла for проходит за постоянное время.
💡 Остановитесь и подумайте:
Обратите внимание, что описанный выше алгоритм неявно находит кратчайший путь в ориентированном ациклическом графе, приведённом ниже (при ). Рассчитайте время выполнения алгоритма для самого короткого пути в аналогичном графе при произвольном значении .