Перейти к содержанию

7.1 Задача о монетах

В этой главе мы начинаем с задачи, которую уже встречали в разделе про жадные алгоритмы: дан набор номиналов монет \(\mathrm{coins}={c_1,c_2,\dots,c_k}\) и целевая сумма \(n\). Нужно набрать сумму \(n\), используя как можно меньше монет.

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

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

Рекурсивная постановка

Ключевая идея динамики — выразить решение большой задачи через решения более маленьких.

Обозначим через \(solve(x)\) минимальное число монет, необходимое для набора суммы \(x\).

Рассмотрим пример с номиналами

\[ \mathrm{coins}={1,4,6}. \]

Тогда первые значения функции таковы:

\[ \begin{aligned} solve(0) &= 0, \\\\ solve(1) &= 1, \\\\ solve(2) &= 2, \\\\ solve(3) &= 3, \\\\ solve(4) &= 1, \\\\ solve(5) &= 2, \\\\ solve(6) &= 1, \\\\ solve(7) &= 2, \\\\ solve(8) &= 2, \\\\ solve(9) &= 3, \\\\ solve(10) &= 2. \end{aligned} \]

Например, \(solve(10)=2\), потому что сумму \(10\) можно набрать как \(4+6\).

Почему это работает рекурсивно? Посмотрим на первую выбранную монету. Если первой взять монету \(1\), то остаётся задача набрать сумму \(9\). Если первой взять \(4\), остаётся набрать \(6\). Если первой взять \(6\), остаётся набрать \(4\).

Значит,

\[ solve(10)=\min\bigl(solve(9)+1,\ solve(6)+1,\ solve(4)+1\bigr). \]

В общем виде получаем:

\[ solve(x)= \begin{cases} \infty, & x<0,\\\\ 0, & x=0,\\\\ \min\limits_{c\in \mathrm{coins}} \bigl(solve(x-c)+1\bigr), & x>0. \end{cases} \]

Смысл такой:

  • если \(x<0\), набрать отрицательную сумму невозможно;
  • если \(x=0\), монеты не нужны вовсе;
  • если \(x>0\), перебираем все варианты первой монеты.

Например,

\[ solve(10)=solve(4)+1=solve(0)+2=2. \]

Простая рекурсия

Такую идею можно сразу записать в коде:

int solve(int x) {
    if (x < 0) return INF;
    if (x == 0) return 0;

    int best = INF;
    for (auto c : coins) {
        best = min(best, solve(x - c) + 1);
    }
    return best;
}

Но в таком виде решение неэффективно. Одна и та же подзадача вычисляется много раз, поэтому число вызовов быстро растёт.

Мемоизация

Чтобы избежать повторных вычислений, применяют мемоизацию: как только значение \(solve(x)\) найдено, мы сохраняем его и больше не пересчитываем.

Пусть есть массивы

bool ready[N];
int value[N];

Здесь:

  • ready[x] показывает, вычислено ли уже значение \(solve(x)\);
  • value[x] хранит само значение.

Тогда рекурсивная функция станет такой:

int solve(int x) {
    if (x < 0) return INF;
    if (x == 0) return 0;
    if (ready[x]) return value[x];

    int best = INF;
    for (auto c : coins) {
        best = min(best, solve(x - c) + 1);
    }

    value[x] = best;
    ready[x] = true;
    return best;
}

Теперь каждое значение считается только один раз, и итоговая сложность становится

\[ O(nk), \]

где \(n\) — целевая сумма, а \(k\) — число номиналов.

Итеративная реализация

На практике соревновательные программисты чаще используют итеративную версию. Она короче и обычно работает чуть быстрее за счёт меньших констант.

value[0] = 0;
for (int x = 1; x <= n; x++) {
    value[x] = INF;
    for (auto c : coins) {
        if (x - c >= 0) {
            value[x] = min(value[x], value[x - c] + 1);
        }
    }
}

Эта программа последовательно вычисляет ответы для всех сумм от \(0\) до \(n\).

Можно представить зависимость состояний так:


flowchart TD
    A["solve 10"] --> B["solve 9"]
    A --> C["solve 6"]
    A --> D["solve 4"]
    B --> E["solve 8"]
    B --> F["solve 5"]
    B --> G["solve 3"]
    C --> F
    C --> H["solve 2"]
    C --> I["solve 0"]
    D --> G
    D --> I
Hold "Ctrl" to enable pan & zoom

Здесь видно, что многие подзадачи повторяются. Именно поэтому мемоизация и табличная динамика так полезны.

Восстановление одного оптимального решения

Часто требуется не только узнать минимальное число монет, но и показать, какими именно монетами набирается сумма.

Для этого заведём массив

int first[N];

где first[x] — первая монета в одном из оптимальных способов набрать сумму \(x\).

Тогда алгоритм слегка меняется:

value[0] = 0;
for (int x = 1; x <= n; x++) {
    value[x] = INF;
    for (auto c : coins) {
        if (x - c >= 0 && value[x - c] + 1 < value[x]) {
            value[x] = value[x - c] + 1;
            first[x] = c;
        }
    }
}

После этого можно восстановить ответ:

while (n > 0) {
    cout << first[n] << "\n";
    n -= first[n];
}

Например, если \(\mathrm{coins}={1,4,6}\) и \(n=10\), то возможное восстановление даст:

\[ 10 \to 4 \to 0, \]

то есть ответ состоит из монет \(6\) и \(4\).

Подсчёт числа способов

Есть и другая версия задачи: не минимизировать число монет, а подсчитать количество способов набрать сумму \(x\).

Пусть снова

\[ \mathrm{coins}={1,4,6}, \qquad x=8. \]

Тогда способы таковы:

  • \(1+1+1+1+1+1+1+1\);
  • \(4+4\);
  • \(1+1+6\);
  • \(1+6+1\);
  • \(6+1+1\);
  • \(4+1+1+1+1\) и другие перестановки.

Если порядок монет считается различным, то динамика записывается так же естественно.

Обозначим через \(solve(x)\) число способов набрать сумму \(x\). Тогда:

\[ solve(x)= \begin{cases} 0, & x<0,\\\\ 1, & x=0,\\\\ \sum\limits_{c\in \mathrm{coins}} solve(x-c), & x>0. \end{cases} \]

Почему база при \(x=0\) равна \(1\)? Потому что существует ровно один способ набрать нулевую сумму: ничего не взять.

Итеративная реализация:

count[0] = 1;
for (int x = 1; x <= n; x++) {
    for (auto c : coins) {
        if (x - c >= 0) {
            count[x] += count[x - c];
        }
    }
}

Здесь count[x] хранит количество способов получить сумму \(x\).

Вычисления по модулю

Количество способов может быть очень большим. Поэтому в задачах часто просят вывести ответ по модулю \(m\), например по модулю \(10^9+7\).

Тогда после каждого прибавления достаточно делать

count[x] %= m;

то есть полная версия внутреннего перехода выглядит так:

if (x - c >= 0) {
    count[x] += count[x - c];
    count[x] %= m;
}

Что важно запомнить

Задача о монетах — один из самых классических примеров динамического программирования. На ней хорошо видны все базовые идеи:

  1. нужно выбрать, что будет состоянием — здесь это сумма \(x\);
  2. нужно понять, как выразить ответ через меньшие состояния;
  3. нужно избежать повторных вычислений — мемоизацией или табличной динамикой;
  4. при необходимости можно отдельно хранить информацию для восстановления ответа;
  5. ту же схему можно использовать не только для оптимизации, но и для подсчёта количества решений.