Реализовать функцию, которая выдает минимальное количество купюр по заданной сумме

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

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

Как отвечать

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

function greedy(sum, bills) {
  const sorted = [...bills].sort((a, b) => b - a);
  const out = new Map();
  for (const bill of sorted) {
    const count = Math.floor(sum / bill);
    if (count > 0) {
      out.set(bill, count);
      sum -= count * bill;
    }
  }
  return sum === 0 ? out : null;
}

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

function minBills(sum, bills) {
  const dp = new Array(sum + 1).fill(Infinity);
  dp[0] = 0;
  for (let s = 1; s <= sum; s++)
    for (const b of bills) if (b <= s) dp[s] = Math.min(dp[s], dp[s - b] + 1);
  return dp[sum];
}

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

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

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

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

Третье: возвращают количество, когда просили состав, или наоборот. Формулировку стоит уточнить в начале: минимальное число купюр это одно значение, а раскладка по номиналам это другая структура и другие тесты к ней.