Как перебрать варианты выдачи суммы с минимальным количеством купюр при неизвестных номиналах

Что проверяют

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

Как отвечать

«Неизвестные номиналы» означает, что они приходят на вход и заранее про них ничего не известно. Для рублей жадный подход «бери самую крупную» даёт оптимум, но это свойство конкретной системы номиналов. Контрпример: номиналы [1, 3, 4], сумма 6. Жадный возьмёт 4 + 1 + 1, три купюры, а оптимум 3 + 3.

Решение через ДП:

• состояние: dp[s], минимальное число купюр для суммы s, причём dp[0] = 0, остальные Infinity;
• переход: для каждой суммы от 1 до amount и каждого номинала c <= s берём dp[s] = Math.min(dp[s], dp[s - c] + 1);
• ответ: dp[amount], а если там Infinity, сумму не собрать, возвращаем -1;
• сложность: время O(amount · n), память O(amount).

Чтобы вернуть не только количество, но и сами купюры, храните рядом массив last[s] с номиналом, на котором достигнут минимум, и идите от amount назад, вычитая его.

Во фронтенде стоит сказать ещё две вещи. Деньги считают в целых единицах, копейках, иначе 0.1 + 0.2 сломает индексы массива. И восходящий цикл надёжнее рекурсии с мемоизацией: при сумме в десятки тысяч и номинале 1 глубина рекурсии упрётся в размер стека, и браузер бросит RangeError.

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

Где спотыкаются

Сразу пишут жадный алгоритм и не проверяют его на контрпримере. Для произвольного набора номиналов такое решение неверно.

Путают минимальное число купюр с числом способов разменять сумму. Во второй задаче важен порядок циклов (номиналы во внешнем), иначе один и тот же набор посчитается несколько раз.

Забывают про недостижимые суммы. Без проверки на Infinity функция вернёт Infinity вместо понятного -1, и интерфейс покажет пользователю «Infinity купюр».