MiddleКодЧастоЕщё не отвечали
Выдать сумму банкомата минимумом купюр; когда жадность ломается?
В банкомате есть номиналы 50, 100, 500, 1000, 5000 рублей с ограниченным запасом по номиналу. Выдайте запрошенную сумму, начиная с крупных купюр. Если собрать нельзя, оставьте запас без изменений.
Требования:
- При неудаче доступные количества должны остаться ровно как были (атомарно).
- Объясните, когда жадная стратегия «крупные первыми» может не сработать.
// возвращает true и уменьшает запас при успехе; false и без изменений при неудаче
bool dispense(std::map<int,int>& stock, int amount) {
// ваш код здесь
}Допишите реализацию.
Идём по номиналам от крупных к мелким, беря min(amount / denom, stock[denom]) каждого. Жадность оптимальна лишь потому, что номиналы взаимно делятся. Считаем план во временный буфер и применяем, только если остаток нулевой — так неудача оставляет запас нетронутым.
- ✗Менять реальный запас до того, как сумма полностью собрана
- ✗Считать жадность оптимальной для произвольных номиналов, а не только делящихся
- ✗Оставлять номиналы с нулевым количеством в результате выдачи
- →Приведите набор номиналов, где жадность ломается, но решение есть.
- →Как перейти к решению через динамику для произвольных номиналов?
Оглавление
Задача
Выдайте сумму крупными купюрами; при неудаче оставьте запас нетронутым.
Решение
#include <map>
bool dispense(std::map<int,int>& stock, int amount) {
std::map<int,int> plan;
int rem = amount;
for (auto it = stock.rbegin(); it != stock.rend(); ++it) { // крупные первыми
int denom = it->first, take = std::min(rem / denom, it->second);
if (take > 0) { plan[denom] = take; rem -= take * denom; }
}
if (rem != 0) return false; // собрать нельзя → без изменений
for (auto& [denom, cnt] : plan) stock[denom] -= cnt; // применяем план
return true;
}Ключевые моменты
- План считается во временный буфер; реальный запас меняем лишь при
rem == 0. - Жадность оптимальна, потому что номиналы взаимно делятся.
- Для произвольных номиналов жадность ломается — нужна динамика.
Оглавление
