Размен монет

Дана сумма $x$ и номиналы монет, каждого достаточно. Набрать сумму минимальным числом монет.

Естественная жадность: брать самые крупные, пока влезают.

int coins = 0;
for (int value : denominations)   // по убыванию
    { coins += x / value; x %= value; }

Для номиналов $1, 5, 10, 25$ это верно. Проверено перебором: на всех суммах от 1 до 300 жадный ответ совпадает с оптимальным.

Для номиналов $1, 3, 4$ — неверно. На тех же условиях жадность ошибается на 14 суммах из 60. Наименьшая — шесть: жадно получается $4 + 1 + 1$ (три монеты), оптимально $3 + 3$ (две).

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

Доказательство для $1, 5, 10, 25$ — обменное. Возьмём оптимальный ответ и покажем, что он не может сильно отличаться от жадного.

В оптимальном ответе не может быть:

• пяти монет по 1 — заменяются одной пятёркой, монет стало на четыре меньше;
• двух монет по 5 — заменяются одной десяткой;
• трёх монет по 10 — заменяются на $25 + 5$, три монеты вместо трёх… стоп, это не улучшение. Правильно так: $10 + 10 + 10 = 30 = 25 + 5$, две монеты вместо трёх. Улучшение есть.

После этих ограничений остаётся конечное число вариантов для остатка, и все проверяются вручную. Отсюда: единиц не больше 4, пятёрок не больше 1, десяток не больше 2 — а это ровно то, что даёт жадный алгоритм.

Ключ в структуре номиналов: каждый следующий кратен предыдущему или почти кратен. Для $1, 3, 4$ этого нет — четвёрка не кратна тройке, и обмен $3 + 3 \to 4 + 1 + 1$ ухудшает ответ вместо того, чтобы улучшать.

Как проверить свою систему

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

Известен результат: для системы с наибольшим номиналом $c$ достаточно проверить все суммы до $2c$ — если на них жадность оптимальна, она оптимальна всегда. На практике проверяют перебором до нескольких тысяч:

vector<int> exact(limit + 1, INT_MAX);
exact[0] = 0;
for (int sum = 1; sum <= limit; sum++)
    for (int value : denominations)
        if (value <= sum && exact[sum - value] != INT_MAX)
            exact[sum] = min(exact[sum], exact[sum - value] + 1);

Двадцать строк динамики против часа размышлений над доказательством. Это общий приём: стресс против перебора отвечает на вопрос «работает ли жадность» надёжнее, чем интуиция.

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

В общем случае задача решается динамикой, кодом выше. Сложность — $O(x \cdot k)$, где $k$ — число номиналов.

Если сумма огромная ($10^{18}$), а номиналов мало, динамика не годится, и задача становится по-настоящему трудной: в общей постановке это NP-полная задача. В олимпиадных условиях это означает, что вас ждут либо с фиксированными номиналами, либо с суммой, влезающей в таблицу.

Родственная задача: набрать любым способом

Если минимизировать число монет не нужно, а надо просто узнать, набирается ли сумма, задача становится проще. Для двух взаимно простых номиналов $a$ и $b$ есть точный ответ: все суммы, начиная с $(a-1)(b-1)$, набираются, а наибольшая ненабираемая равна $ab - a - b$. Это число Фробениуса.

Для трёх и более номиналов формулы нет — снова динамика или расширенный Евклид для проверки разрешимости.

Мораль

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

Условие «монеты номиналом 1, 2, 5, 10, 50, 100» и условие «номиналы даны во входных данных» — это две разные задачи, и первая мысль во втором случае должна быть о динамике.