MiddleCodeCommonNot answered yet
Dispense an ATM amount with the fewest bills; when does greedy fail?
An ATM has bill denominations 50, 100, 500, 1000, 5000 rubles with limited stock per denomination. Dispense a requested amount using larger bills first. If it cannot be assembled, leave the stock unchanged.
Requirements:
- On failure, the available counts must stay exactly as before (atomic).
- Explain when a greedy largest-first strategy can fail.
// returns true and decrements stock on success; false and no change on failure
bool dispense(std::map<int,int>& stock, int amount) {
// your code here
}Write the implementation.
Walk denominations from largest to smallest, taking min(amount / denom, stock[denom]) of each. Greedy is optimal only because the denominations are mutually divisible. Compute the plan into a temporary and apply it only if the remainder is zero — so a failure leaves stock untouched.
- ✗Mutating the real stock before knowing the amount is fully assembled
- ✗Assuming greedy is optimal for arbitrary denominations, not just divisible ones
- ✗Leaving zero-count denominations in the dispensed result
- →Give a denomination set where greedy fails but a solution exists.
- →How would you switch to a DP solution for arbitrary denominations?
Contents
Task
Dispense an amount with larger bills first; on failure leave the stock untouched.
Solution
#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) { // largest first
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; // cannot assemble → no change
for (auto& [denom, cnt] : plan) stock[denom] -= cnt; // apply the plan
return true;
}Key points
- The plan is built in a temporary; the real stock changes only when
rem == 0. - Greedy is optimal because the denominations are mutually divisible.
- For arbitrary denominations greedy fails — dynamic programming is needed.
Contents
