В этом параграфе вы узнаете, почему жадная стратегия не всегда подходит для задачи сдачи и как динамическое программирование помогает найти оптимальное решение. Вы разберётесь с рекуррентной формулой, научитесь строить эффективный алгоритм с мемоизацией и поймёте, как ускорить его с помощью табличного подхода.
Ключевые вопросы параграфа
- Почему жадный алгоритм не справляется с задачей оптимальной сдачи?
- Как составить рекуррентное соотношение для минимального числа монет?
- В чём отличие мемоизации от табличного (bottom-up) подхода?
- Как реализовать решение задачи с помощью динамического программирования?
Сдача
Как нам уже известно, естественный «жадный» подход к этой задаче работает неправильно при любом наборе номиналов. Например, при номиналах , и «жадный» алгоритм разменяет центов тремя монетами (), хотя это возможно сделать всего лишь двумя (). Ваша цель — использовать динамическое программирование для решения задачи «Сдача» с номиналами , и .
- Входные данные: Целое число .
- Выходные данные: Минимальное количество монет номиналами , , , чтобы выдать сдачу с .
- Ограничения: .
Пример 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 проходит за постоянное время.
Обратите внимание, что описанный выше алгоритм неявно находит кратчайший путь в ориентированном ациклическом графе, приведённом ниже (при ). Рассчитайте время выполнения алгоритма для самого короткого пути в аналогичном графе при произвольном значении .
Что дальше
Теперь вы умеете использовать динамическое программирование для нахождения оптимального числа монет при сдаче. Вы поняли, почему жадный подход может давать неверный результат, научились строить рекурсивные решения с мемоизацией и ускорять их с помощью таблицы. А ещё увидели, что даже простая задача может быть связана с кратчайшими путями в графах.
Далее — задача на построение выражения с минимальной стоимостью вычислений. Вы научитесь определять порядок операций, который экономит ресурсы, и познакомитесь с динамическим программированием на интервалах.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Жадный подход может давать неоптимальные решения в задаче размена.
- Динамическое программирование позволяет учитывать все варианты и выбирать наилучший.
- Рекурсия с мемоизацией помогает избежать повторных вычислений, но может быть медленной.
- Табличный (bottom-up) подход эффективнее и позволяет решать задачу за линейное время.
- Такие задачи часто можно представить как поиск кратчайшего пути в графе.