Когда локальный выбор безопасен

Жадный алгоритм не означает «бери самое большое, потому что так кажется разумным». Его шаг безопасен, только если можно объяснить, почему в каком-то оптимальном ответе этот шаг тоже может стоять первым.

Как кассиру собрать заданную сумму

Пусть касса должна выдать сумму обычными рублёвыми номиналами 1, 5, 10, 50. Нужно использовать как можно меньше монет. Для 67 естественный первый выбор — 50, затем 10, 5, 1, 1.

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

Что проверит полный перебор разменов

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

Почему ветви размена растут слишком быстро

Перебор заново отвечает на вопрос «как выдать остаток r». Динамическое программирование исправит это повторение для произвольных монет, но здесь можно сделать ещё сильнее: не рассматривать альтернативы вовсе, если доказан безопасный первый выбор.

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

Для номиналов 1, 5, 10, 50 любая сумма хотя бы 50 в оптимальном наборе может содержать монету 50: заменить пять монет 10 или десять монет 5 на одну 50 не хуже по числу монет. Аналогично после удаления всех пятидесяток остаток меньше 50, и тот же обменный аргумент работает для 10, затем для 5.

Значит, существует оптимальное решение, которое начинает с максимально возможной монеты. Мы выбираем её, уменьшаем остаток и повторяем рассуждение. Контрпример: для 1, 3, 4 и суммы 6 жадный выбор даст 4+1+1 (три монеты), а оптимум — 3+3 (две).

Какое свойство сохраняет остаток суммы

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

Как построить размен шаг за шагом

1. Отклонить отрицательную сумму: задача размена определена только для amount >= 0.
2. Отсортировать допустимые номиналы по убыванию.
3. Для каждого d взять remaining / d монет и вычесть их стоимость.
4. В конце проверить, что remaining == 0; иначе такая система не умеет выдать сумму.
5. Использовать алгоритм только для системы, для которой жадность уже доказана в условиях задачи или известна отдельно.

Как выразить выбор монеты в коде

Функция возвращает выбранные номиналы, чтобы ответ можно было проверить, а не только посчитать их число. Она сама отклоняет отрицательный amount, поэтому C++ и Python одинаково соблюдают контракт amount >= 0. Пример ограничен системой 1, 5, 10, 50; код не утверждает оптимальность для произвольного массива.

C++17

#include <cassert>
#include <iostream>
#include <stdexcept>
#include <vector>

using namespace std;

vector<int> greedyRubles(int amount) {
    if (amount < 0) {
        throw invalid_argument("amount");
    }

    const vector<int> denominations = {50, 10, 5, 1};
    vector<int> chosen;

    for (int coin : denominations) {
        int count = amount / coin;
        for (int used = 0; used < count; ++used) {
            chosen.push_back(coin);
        }
        amount %= coin;
    }
    return chosen;
}

int main() {
    vector<int> answer = greedyRubles(67);
    int sum = 0;
    for (int coin : answer) {
        sum += coin;
    }
    assert(sum == 67);
    assert(answer == vector<int>({50, 10, 5, 1, 1}));
    bool rejectedNegative = false;
    try {
        greedyRubles(-1);
    } catch (const invalid_argument&) {
        rejectedNegative = true;
    }
    assert(rejectedNegative);
    cout << answer.size() << '\n';
}

Python 3

def greedy_rubles(amount: int) -> list[int]:
    if amount < 0:
        raise ValueError("amount")

    denominations = [50, 10, 5, 1]
    chosen: list[int] = []

    for coin in denominations:
        count, amount = divmod(amount, coin)
        chosen.extend([coin] * count)
    return chosen


answer = greedy_rubles(67)
assert sum(answer) == 67
assert answer == [50, 10, 5, 1, 1]
try:
    greedy_rubles(-1)
except ValueError:
    pass
else:
    raise AssertionError("negative amount must be rejected")
print(len(answer))

Во что обходится жадный размен

При фиксированных четырёх номиналах поиск количества каждого номинала занимает O(1), а создание списка ответа — O(k), где k равно числу выданных монет. Если номиналов m, после сортировки это O(m log m + k); если они уже упорядочены, O(m + k). Доказательство относится к указанной десятичной системе, а не ко всем системам монет.

Какие номиналы требуют контрпримера

amount = 0 возвращает пустой список. Отрицательная сумма нарушает контракт задачи, поэтому обе реализации явно отклоняют её внутри функции. Если убрать монету 1, некоторые остатки становятся недостижимыми, поэтому необходима явная проверка остатка. Самый важный смысловой тест — 1,3,4 и 6: он показывает, почему нельзя переносить код без доказательства.

Чем проверить выдачу монет

• 0 -> [];
• -1 -> ошибка в обеих реализациях;
• 5 -> [5] и 49 -> 10,10,10,10,5,1,1,1,1;
• 67 -> [50,10,5,1,1];
• сравнить жадный ответ и DP для малых сумм в системе 1,5,10,50;
• отдельно убедиться, что для 1,3,4 и 6 жадный результат хуже DP.

Какие условия намекают на жадный выбор

Ищите задачу, где решение строится последовательностью необратимых локальных шагов, а цель — минимум или максимум. Прежде чем кодировать, спросите: «могу ли я заменить первый шаг оптимального решения моим шагом и не ухудшить ответ?» Если да, это кандидат на жадный алгоритм.

Когда крупная монета ведёт в тупик

Не применяйте жадность только по красивой интуиции. Разные номиналы, ограничения на число монет, штрафы за сочетания или требование точной суммы часто требуют DP. В частности, набор 1,3,4 ломает правило «взять максимальную монету».

Самопроверка выбора первой монеты

Вопрос: почему для 1,5,10,50 можно взять 50, если остаток не меньше 50?
Ответ: в оптимальном наборе сумму не меньше 50 нельзя покрывать пятью десятками лучше, чем одной пятидесяткой; замена не увеличивает число монет и оставляет тот же остаток.

Самопроверка доказательства обмена

Вопрос: почему результат 4+1+1 для суммы 6 не доказывает корректность жадности для монет 1,3,4?
Ответ: существует лучшее разложение 3+3. Локально большая 4 не допускает нужного обменного доказательства.

Потренируйте размен с опорой на инвариант

Для суммы 93 вручную выпишите состояние remaining после каждого номинала 50,10,5,1. Затем измените набор монет на 1,3,4 и найдите первую сумму до 10, на которой правило максимальной монеты расходится с DP. Подсказка: сравнивайте число монет, а не только возможность собрать сумму.

Самостоятельная проверка жадной гипотезы

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

Задача 1

Даны произвольные положительные номиналы и сумма. Верните минимальное число монет или -1, если сумму собрать нельзя. Сформулируйте контрпример, который отличает это условие от канонического размена.

Что запомнить о доказанном локальном выборе

Жадный шаг — это теорема о структуре оптимального решения. Если обменный аргумент не находится, сначала ищите DP или другой способ сохранить варианты.