6.1 Задача о монетах¶

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

В качестве первого примера рассмотрим задачу, в которой дан набор монет, и нужно составить сумму n, используя эти монеты. Номиналы монет равны

coins = {c1, c2, ..., ck},

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

Например, пусть доступны монеты с номиналами

{1, 2, 5, 10, 20, 50, 100, 200},

а нужно набрать n = 760. Тогда достаточно 5 монет. Один из оптимальных вариантов:

200 + 200 + 200 + 100 + 50 + 10 — нет, это уже 6 монет.

Лучше так:

200 + 200 + 200 + 100 + 50 + 10 показывает, что жадный выбор не всегда удобно проверять «на глаз».

Возьмём более аккуратный пример: для n = 570 оптимально выбрать

200 + 200 + 100 + 50 + 20,

то есть требуется 5 монет.

Жадный алгоритм¶

Простой жадный алгоритм действует так: на каждом шаге он берёт самую крупную монету, которая ещё не превышает оставшуюся сумму. Алгоритм повторяет этот выбор, пока вся сумма не будет набрана.

Для приведённого примера это работает так:

%%{init: {
  "themeVariables": {
    "fontSize": "22px"
  },
  "flowchart": {
    "nodeSpacing": 50,
    "rankSpacing": 50,
    "useMaxWidth": false
  }
}}%%
flowchart LR
    A[Осталось 570] --> B[Берём 200]
    B --> C[Осталось 370]
    C --> D[Берём 200]
    D --> E[Осталось 170]
    E --> F[Берём 100]
    F --> G[Осталось 70]
    G --> H[Берём 50]
    H --> I[Осталось 20]
    I --> J[Берём 20]
    J --> K[Осталось 0]

Получается решение из 5 монет. Но всегда ли этот подход даёт оптимальный ответ?

Оказывается, для стандартного набора монет ответ да: жадный алгоритм действительно всегда находит решение с минимальным количеством монет.

Почему это работает для стандартных номиналов¶

Идея доказательства такая.

Во-первых, в оптимальном решении монеты 1, 5, 10, 50 и 100 не могут встречаться более одного раза. Иначе две одинаковые монеты можно было бы заменить одной более крупной и уменьшить число монет. Например, если в решении есть 5 + 5, их выгоднее заменить на 10.

Аналогично, монеты 2 и 20 могут встречаться не более двух раз. Действительно:

• 2 + 2 + 2 можно заменить на 5 + 1,
• 20 + 20 + 20 можно заменить на 50 + 10.

Кроме того, в оптимальном решении не может быть комбинаций 2 + 2 + 1 и 20 + 20 + 10, потому что их можно заменить соответственно на 5 и 50.

Из этих наблюдений следует важный вывод: для каждого номинала x нельзя оптимально собрать сумму x или любую большую сумму, используя только более мелкие монеты.

Например, если x = 100, то наибольшая сумма, которую ещё можно оптимально составить только из меньших монет, равна

50 + 20 + 20 + 5 + 2 + 2 = 99.

Значит, когда остаток становится не меньше 100, монету 100 действительно нужно брать сразу. По той же логике работает и выбор остальных крупных монет. Следовательно, жадный алгоритм, который всегда выбирает максимально возможный номинал, строит оптимальное решение.

Этот пример хорошо показывает, что доказать корректность жадного алгоритма бывает значительно труднее, чем придумать сам алгоритм.

Общий случай¶

В общем случае набор номиналов может быть произвольным, и тогда жадный алгоритм не обязан давать оптимальный ответ.

Чтобы опровергнуть корректность жадного подхода, достаточно привести контрпример. Здесь он находится очень легко: пусть доступны монеты

{1, 3, 4},

а целевая сумма равна 6.

Жадный алгоритм выберет сначала 4, а затем доберёт остаток двумя монетами 1, получив решение

4 + 1 + 1.

Это 3 монеты.

Но оптимальный ответ —

3 + 3,

то есть 2 монеты.

Следовательно, для произвольного набора монет жадная стратегия может ошибаться.

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