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

Сдача

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

• Входные данные: Целое число $money$.
• Выходные данные: Минимальное количество монет номиналами $1$, $3$, $4$, чтобы выдать сдачу с $money$.
• Ограничения: $1 \le money \le 10^3$.

Пример 1

• $34=3+3+4+4+4+4+4+4+4$.

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

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

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

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

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

Пусть $change(money)$ — это минимальное количество монет номиналами $1$, $3$ и $4$, которые нужны для сдачи с $money$, а $(c_1,\dotsc,c_k)$ — оптимальная сдача с $money$. В таком случае $$ c_1+\dotsb+c_k=money . $$ Тогда $$ c_1+\dotsb+c_{k-1}=money-c_k. $$ Следовательно, $change(money-c_k)=k-1$. Таким образом, для решения задачи при $money$ достаточно решить её при $money-c_k$ и добавить единицу.

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

Проблема в том, что мы не знаем значение $c_k$. Тем не менее мы знаем, что $c_k$ равняется или $1$, или $3$, или $4$. Так $change(money)$ равно одному из следующих вариантов: $change(money-1)+1$, $change(money-3)+1$ и $change(money-4)+1$.

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

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

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

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) снова и снова для одного и того же значения $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 <= money:
            table[m] = min(table[m],1+table[m-c])
    return table[money]

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

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