Для решения задачи выдачи минимального количества банкнот можно использовать жадный алгоритм: сортируем номиналы по убыванию и последовательно вычитаем максимальные возможные банкноты из суммы.
Реализуйте функцию выдачи наличных: по запрошенной сумме и конфигурации доступных купюр определите, можно ли выдать сумму, и верните набор купюр либо ошибку/признак невозможности выдачи. Используйте переданные лимиты купюр, учитывайте ограниченное количество банкнот и невозможность составить сумму.
Для решения задачи выдачи минимального количества банкнот можно использовать жадный алгоритм: сортируем номиналы по убыванию и последовательно вычитаем максимальные возможные банкноты из суммы.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Для решения задачи выдачи минимального количества банкнот можно использовать жадный алгоритм: сортируем номиналы по убыванию и последовательно вычитаем максимальные возможные банкноты из суммы.
function atm(notes, sum) {
notes.sort((a, b) => b - a); // сортируем по убыванию
const result = [];
for (const note of notes) {
while (sum >= note) {
sum -= note;
result.push(note);
}
}
if (sum !== 0) {
// если сумма не может быть выдана заданными номиналами
return [];
}
return result;
}
// Пример
console.log(atm([1, 5, 50, 100], 362));
// Вывод: [100, 100, 100, 50, 5, 5, 1, 1]
Этот алгоритм работает корректно, если номиналы банкнот позволяют выдать любую сумму (например, есть банкнота 1). Если нет, то возможны случаи, когда сумма не может быть выдана.