8.2. Задача «Размен 2»

Сдача

Как нам уже известно, естественный «жадный» подход к этой задаче работает неправильно при любом наборе номиналов. Например, при номиналах , и «жадный» алгоритм разменяет центов тремя монетами (), хотя это возможно сделать всего лишь двумя (). Ваша цель — использовать динамическое программирование для решения задачи «Сдача» с номиналами , и .

• Входные данные: Целое число .
• Выходные данные: Минимальное количество монет номиналами , , , чтобы выдать сдачу с .
• Ограничения: .

Пример 1

Ввод	Вывод
34	9

• .

Для оптимального варианта сдачи с необходимо семь монет. Рассмотрим произвольный поднабор оптимального решения — например, если сложить четыре монеты из приведённого ниже прямоугольника, то получится .

💡 Остановитесь и подумайте:
Сможете разменять центов тремя монетами?

Ответ на этот вопрос: «Нет». Если бы размен был возможен тремя монетами, то можно было бы заменить выделенные четыре монеты и получить сдачу с шестью монетами, а не семью.

Такая ситуация показывает нам важную особенность динамического программирования — решение задачи содержит решения всех её мелких подзадач.

Эта особенность позволяет найти решение задачи, сначала выполняя мелкие подзадачи.

Пусть — это минимальное количество монет номиналами , и , которые нужны для сдачи с , а — оптимальная сдача с . В таком случае

Тогда

Следовательно, . Таким образом, для решения задачи при достаточно решить её при и добавить единицу.

💡 Остановитесь и подумайте:
Мы закончили?

Проблема в том, что мы не знаем значение . Тем не менее мы знаем, что равняется или , или , или . Так равно одному из следующих вариантов: , и .

Так как мы ищем оптимальный способ выдать сдачу, равно минимальному из этих трёх выражений. В итоге мы получаем следующее рекуррентное соотношение:

При небольших аргументах это соотношение выражает значение рекурсивным образом через собственные значения. Для такой нисходящей рекурсии нам необходимо указать базовый случай. У нас это будет : .

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

Change(money):
    if money=0:
        return 0
    else:
        result = +infinity
        for c=1,3,4:
        if c <= money:
            result = min(result,1+Change(money-c))
        return result

У этого алгоритма есть серьёзная проблема: он становится крайне медленным, потому что вызывает Change(money) снова и снова для одного и того же значения .

Мемоизация — стандартный способ избежать этого: при вычислении Change(money) мы можем использовать сохранение в таблице и тогда нам не придётся делать перевычисление.

table=associative array
    
Change(money):
    if table[money] is not yet computed:
    if money=0:
        table[money]←0
    else:
        result = +infinity
        for c=1,3,4:
        if c <= money:
            result = min(result,1+Change(money-c))
        table[money] = result
    return table[money]

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

Change(money):
    table[0..money] = [+infinity,…,+infinity]
    table[0] = 0
    
    for m from 1 to money:
        for c=1,3,4:
        if c <= m:
            table[m] = min(table[m],1+table[m-c])
    return table[money]

Время выполнения этого алгоритма составляет , так как каждая итерация внешнего цикла for проходит за постоянное время.

💡 Остановитесь и подумайте:
Обратите внимание, что описанный выше алгоритм неявно находит кратчайший путь в ориентированном ациклическом графе, приведённом ниже (при ). Рассчитайте время выполнения алгоритма для самого короткого пути в аналогичном графе при произвольном значении .