Жадный алгоритм (обменный аргумент)

O(n log n)

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

Сигналы

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

Шаблон

function minCoinsGreedy(coins, amount) {
    const sorted = [...coins].sort((a, b) => b - a);
    const used = [];
    for (const coin of sorted) {
        while (amount >= coin) {
            amount -= coin;
            used.push(coin);
        }
    }
    return amount === 0 ? used : null;
}

Похоже, но не то

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

номиналов до ~20 штук, сортируем один раз, затем один проход выдачи -> O(n log n): сортировка монет доминирует, сам проход выдачи стоит O(amount).

Изучить этот паттерн