Greedy Choice
Greedy means taking the best-looking option right now and never going back. It is fast and simple, and it is only correct when a local choice can be proven safe: when any solution that skips the greedy pick can be exchanged for one that takes it. Coin change shows both sides, with coins where the exchange holds and coins where it does not.
Make 6 with coins 4, 3, 1 using as few coins as possible. Greedy rule: take the largest coin that fits, and never reconsider.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 2, with their answers.
6 left. Which coin does greedy take next?
Answer: 4. 4 is the largest coin that is not more than 6.
2 left. Which coin does greedy take next?
Answer: 1. 1 is the largest coin that is not more than 2.
How it runs, step by step
Make 6 with coins 4, 3, 1 using as few coins as possible. Greedy rule: take the largest coin that fits, and never reconsider.
Making 6 from the coins 4, 3, 1 by always taking the largest that fits.
6 left. 4 fits, so take it once: 6 - 4 = 2.
With 6 left, the largest coin that fits is 4. Take it once, leaving 2.
2 left. 4, 3 are too big. 1 fits, so take it 2 times: 2 - 2 = 0. Done.
With 2 left, the largest coin that fits is 1. Take it 2 times, leaving 0.
Greedy made 6 with 3 coins: 4 + 1 + 1. But 3 + 3 uses only 2. Greedy fails here because the exchange argument breaks: taking the biggest coin first left a remainder that needs many small coins.
Greedy used 3 coins: 4 + 1 + 1. The minimum is 2 coins: 3 + 3.
Write it yourself
Define greedyCoinCount(coins, amount) and return how many coins greedy uses - always take the largest coin that fits. It runs in your browser against this lesson's own 4 examples.
// Take the biggest coin that still fits, as many times as it fits, then move down. This is not always the fewest coins, and that is the point.function greedyCoinCount(coins, amount) { return 0;}
Remember
- Greedy takes the locally best choice and never revisits it.
- It is correct only when an exchange argument holds: any solution can be reshaped to include the greedy pick without getting worse.
- Coin change with 1, 5, 10, 25 is safe. With 1, 3, 4 and amount 6, greedy gives three coins where two suffice.
Where this is used
PaymentsDispensing cash
An ATM or a self-checkout pays out by handing over the largest denomination its cassettes can still fit, then repeating - this exact loop, with the cassettes standing in for the sorted coin list. When a cassette runs dry the usable set is no longer the full currency, and the greedy pick can strand a remainder the machine cannot complete, so dispensers fall back to searching over the denominations actually loaded.
TypographyBreaking a paragraph into lines
Browsers and most word processors fill each line with as many words as fit and move on, never revisiting a line already set. TeX refuses to: the Knuth-Plass algorithm scores the whole paragraph with dynamic programming and will loosen one line to avoid a badly stretched one three lines later. The visible difference is the loose lines greedy leaves behind, where the spaces have to stretch because the row above took one word too many.
CompilersLLVM's register allocator
Assigning variables to a fixed set of CPU registers optimally is NP-hard, so LLVM's default allocator is named greedy outright. It pulls live ranges off a priority queue in decreasing order of spill weight and gives each one the best register available. Real greedy code bends further than the textbook version does: when nothing is free it evicts a lower-weight range and requeues it, or splits the range into pieces, and only spills to memory when neither works. What it never does is search for a globally optimal assignment, because a compiler has to finish in milliseconds on functions with thousands of live ranges.
OperationsPlacing a pod on a node
The Kubernetes scheduler handles one pod at a time: it filters out nodes that cannot run it, scores the survivors, and places the pod on the highest scorer. It does not revisit a placement to rebalance the cluster, so a run of individually sensible decisions can leave it badly packed. The one thing it will undo is preemption, evicting lower-priority pods when a higher-priority one has nowhere to go. Everything else is left to a separate descheduler that evicts pods so the scheduler places them again - repairing greedy choices after the fact instead of avoiding them.
Why it works this way
The coins have to arrive sorted descending
The loop takes each coin in the order it is given and drains it before moving on, so the ordering is where the rule "largest coin that still fits" actually lives. Hand the same function 1, 5, 10, 25 in ascending order and it pays 41 as forty-one pennies: still valid change, but the worst answer available. The comment on the signature is load-bearing, not decoration.
Greedy can miss the answer entirely, not just the short one
With coins 3 and 4 and an amount of 6, greedy takes the 4, is left with 2 that no coin fits, and returns a single coin worth 4. That is not change at all, and the loop has no way to put the 4 back. Real coin systems always include a 1 so any leftover can be paid off; without one you have to check that the returned coins really sum to the amount.
How would you know a coin set is safe?
You cannot tell by looking, but you do not have to test every amount either. Kozen and Zaks showed that if a system is not canonical, its smallest counterexample is below the sum of the two largest coins, so a finite check settles the question: for 1, 3, 4 that means trying amounts under 7, and 6 is where it breaks. Pearson later gave a polynomial-time test for the same property. Currency systems in circulation are canonical, which is why counting out change by hand works.
What the fix costs
The general answer is dynamic programming: best[x] = 1 + the smallest best[x - c] over the coins, filled from 0 up to the amount. That is O(coins x amount) time and O(amount) memory against greedy's single pass and O(1). You are paying for the right to reconsider - greedy commits to a coin and never looks at it again, while the table keeps the best answer for every smaller amount and can change its mind.
Read more
- Greedy algorithmWikipedia
- Change-making problemWikipedia
- Activity selection problemWikipedia
- Matroids: when greedy is provably optimalWikipedia
- Line wrap and word wrap: greedy versus optimalWikipedia