Модуль выдачи наличных

Условие

Дано устройство, которое хранит банкноты разных номиналов. На вход приходит Map<Integer, Integer> — ключом является номинал купюры, а значением — количество таких купюр. Необходимо реализовать метод, который может вызываться неоднократно. Метод принимает требуемую сумму и возвращает карту, показывающую, какие купюры и в каком количестве следует выдать. Если собрать указанную сумму невозможно, метод возвращает сообщение об ошибке.

Map<Integer, Integer> input = Map.of(
    50, 6,
    100, 6,
    500, 6,
    1000, 6
);

public Map<Integer, Integer> withdraw(int amount) {
    // ...
}

Ответ

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

Один корректный учебный вариант — перебор по номиналам с возвратом. Поля класса: изменяемая копия stock и отсортированный список номиналов denominations.

public synchronized Map<Integer, Integer> withdraw(int amount) {
    if (amount <= 0) throw new IllegalArgumentException();
    Map<Integer, Integer> selected = new HashMap<>();
    if (!choose(0, amount, selected))
        throw new IllegalStateException("Cannot dispense exact amount");
    selected.forEach((value, count) -> stock.put(value, stock.get(value) - count));
    return selected;
}

private boolean choose(int index, int remaining, Map<Integer, Integer> selected) {
    if (remaining == 0) return true;
    if (index == denominations.size()) return false;
    int value = denominations.get(index);
    int max = Math.min(stock.get(value), remaining / value);
    for (int count = max; count >= 0; count--) {
        if (count == 0) selected.remove(value); else selected.put(value, count);
        if (choose(index + 1, remaining - count * value, selected)) return true;
    }
    selected.remove(value);
    return false;
}

Конструктор должен копировать Map.of в HashMap и проверять положительность номиналов и неотрицательность запасов. Перебор может быть дорогим; для больших сумм используют bounded-knapsack/DP с ограничениями. Ошибка поиска остатки не меняет.