Алгоритм формирования выдачи купюр из банкомата

Условие

Дан объект denominations, где ключи представляют номиналы банкнот, а значения – их доступное количество. Требуется реализовать функцию atmWithdraw(amount, denominations), принимающую целевую сумму для выдачи (amount) и объект с текущими остатками банкнот (denominations). Функция должна вернуть новый объект, содержащий набор банкнот, необходимых для выдачи указанной суммы, в том же формате, что и denominations. При этом исходный объект denominations должен быть изменён: количество использованных банкнот должно уменьшиться. Если собрать требуемую сумму из имеющихся банкнот невозможно, то:

• объект denominations остаётся без изменений;
• функция возвращает строковое сообщение о невозможности выполнения выдачи.

Ответ

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

function atmWithdraw(amount, denominations) {
  const notes = Object.keys(denominations).map(Number).sort((a, b) => b - a);
  if (!Number.isSafeInteger(amount) || amount < 0 || notes.some(note =>
    !Number.isSafeInteger(note) || note <= 0 || !Number.isSafeInteger(denominations[note]) || denominations[note] < 0)) {
    throw new RangeError('Некорректные данные');
  }
  const selected = Array(notes.length).fill(0), failed = new Set();
  function search(index, remaining) {
    if (remaining === 0) { selected.fill(0, index); return true; }
    if (index === notes.length) return false;
    const key = `${index}:${remaining}`;
    if (failed.has(key)) return false;
    const note = notes[index];
    const max = Math.min(denominations[note], Math.floor(remaining / note));
    for (let count = max; count >= 0; count--) {
      selected[index] = count;
      if (search(index + 1, remaining - count * note)) return true;
    }
    selected[index] = 0; failed.add(key); return false;
  }
  if (!search(0, amount)) return 'Невозможно выдать сумму';
  const result = {};
  for (let index = 0; index < notes.length; index++) {
    if (selected[index]) {
      result[notes[index]] = selected[index];
      denominations[notes[index]] -= selected[index];
    }
  }
  return result;
}

Номиналы предполагаются каноническими положительными числовыми ключами обычного изменяемого объекта. При неудаче остатки не трогаются, нулевая сумма даёт {}. Мемоизация сокращает перебор, но для крупных сумм нужны лимиты/динамическое программирование; минимальное число купюр этим контрактом не гарантируется.