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

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

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

Как отвечать

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

Дальше каркас решения:

• жадный проход: сортируете номиналы по убыванию, для каждого берёте Math.min(Math.floor(rest / nominal), stock[nominal]) и уменьшаете остаток. Для рублёвого ряда без лимитов это даёт минимум купюр;
• проверка остатка: если после прохода rest > 0, выдача невозможна, и функция должна вернуть null или ошибку, а не частичный набор;
• лимиты ломают жадность: при запасе 500×1 и 200×3 сумму 600 жадный алгоритм не выдаст (взял 500, остаток 100), а правильный ответ 200×3. Поэтому при ограниченном запасе нужен перебор с возвратом или динамика в духе ограниченного рюкзака: для каждой суммы минимум купюр, где номинал берётся не больше, чем лежит в кассете;
• списание запаса: уменьшайте stock только после того, как набор найден целиком. Считайте на копии и фиксируйте результат одним присваиванием, иначе неудачная попытка испортит состояние банкомата.

Про сложность: жадный проход линеен по числу номиналов, а таблица динамики растёт вместе с суммой. Поэтому сумму считают в единицах наименьшего номинала: 37 800 рублей при шаге 100 это всего 378 ячеек.

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

Утверждают, что жадный алгоритм оптимален всегда. Он оптимален только для «канонических» наборов номиналов и без ограничений на запас, а в банкомате ограничения есть всегда.

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

Мутируют запас по ходу подбора. Когда выясняется, что сумму собрать нельзя, часть купюр уже «выдана» в состоянии, и следующий клиент видит неверные остатки.