Break the cashier's greedy habit and find the exact coin combination that minimizes transaction count.
- Test the greedy choice on 6 cents with coins {1, 3, 4} to see the three-coin trap
- Step the DPHeatmap to watch optimal debts propagate along denomination edges
- Take the boss round bet on what makes a currency canonical under Pearson's test
After thisYou will instantly spot when greedy resource allocation fails and how to frame discrete debt as a shortest path.
Short on timeExamine the 6-cent row in the DPHeatmap to see where greedy (4+1+1) loses to shortest-path (3+3).
Six Cents on the Counter
3 minthe hook
Six cents to make, with coins of 1, 3 and 4, and as many of each as you like. Run the rule a cashier runs — take the largest coin that still fits.
A 4 fits, so 2 cents remain. A 1 fits, then another 1. Three coins: 4 + 1 + 1.
Now set the rule aside and look at the tray. 3 + 3 is also six cents, in two coins. The largest-coin-first answer is a coin worse than the best answer, and nothing on the coins said so.
Take the largest coin that fits at each step and you spend 4, then 1, then 1 — three coins for six cents. What is the fewest coins of value 1, 3 and 4 that make six?
Two is the answer; three is the rule. That gap is the page: the fewest coins is a property of the set of coins, and the largest-first rule is an algorithm that happens to be right on some sets and wrong on others.
NextWhy does the greedy cashier spend three coins on six cents where two are optimal?
The Cashier’s Illusion
2 minthe trap
Operationally you are handed a set of denominations c₁ > c₂ > ⋯ > cₙ, unlimited supply of each, and an amount . You hand back the fewest coins that sum to .
“Spend the biggest coin first” is an algorithm, not the question, and it is the algorithm everyone reaches for because a cashier uses it. It is exact on the coins in your pocket and wrong on others, and it gives you no way to tell which case you are in. The real question is about the set of coins, not about the order an algorithm happens to pick them.
NextHow does the debt directed acyclic graph represent all possible coin combinations?
The Directed Graph of Debt
2 minthe invariant
Fix the coins and the amount . The vertices are the amounts . For every coin and every amount , draw an edge
of weight one. The coins are the edge set; an amount is a vertex; making change for is walking from down to . Call this the debt graph: its vertices are amounts, its downward edges are coins, and the fewest coins is the shortest path.
This is the whole page in one sentence. The DP is a shortest-path computation on the debt graph, whose edges are the coins, and the “fewest coins” you asked for is a distance.
Every edge drops the vertex label, so the graph is acyclic and sweeping the amounts from upward visits each cell only after the cells it depends on — Bellman’s relaxation in dependency order. The same table is one row of a min-plus closure, the subject of Floyd–Warshall and Dijkstra. Distances here are small integers, so a plain sweep beats a priority queue.
Reachability is connectivity. Amount is representable exactly when a path runs from down to , and a cell that reads is a vertex no such path reaches.
Let . Every edge changes an amount by a multiple of , so the amounts fall into the residue classes modulo and no edge leaves a class; only the class of can be representable at all.
When that is the only class, and every amount past a finite threshold is reachable. That threshold is the next object.
NextHow does Pearson's polynomial-time test certify whether a currency system is canonical?
Pearson’s Test and Sylvester’s Gap
2 minthe algebra
Give the recurrence first, then watch it disagree with the rule.
The recurrence. Write for the fewest coins summing to . Standing at costs nothing, and every other amount is one coin plus the best way to cover the rest:
with the minimum over the coins, and when no coin fits. Unbounded supply is why the same appears on both sides: after spending a coin you may spend a copy of it again, so no coin count enters the state. Only the amount does — that is what makes the state space the vertices of section 2 and nothing more.
The greedy walk, and where it leaves the path. Greedy commits: it takes the largest coin that fits and never reconsiders. On the coins 1, 3, 4 and amount that walk is , three coins. The shortest path is , two coins, and you can see it is shorter because reaching from never requires passing through , while greedy’s first move forces into the remainder.
Greedy is not “the DP, done fast”. It is a single path picked by a rule, and on the wrong coin system the rule picks a worse path. The failures do not come from rare amounts: for 1, 3, 4 the smallest is , and Chang and Gill 1970 recorded a second one on 1, 5, 20, 25, where 40 cents costs four greedy coins and two minimum ones.
Canonical systems — the rule’s exact domain. The literature has a name for the good case. A coin system is canonical when the greedy representation of every amount is a representation of minimum size (Pearson 2005, following Chang and Gill 1970). Read carefully, “greedy is optimal if and only if the system is canonical” is then not a theorem — canonicity means that greedy is optimal.
The theorem is that this infinite condition is decidable by a finite check, and quickly. Kozen and Zaks 1994 showed the smallest amount where greedy fails, if one exists, lies below , so there is a finite set of candidates to test; Pearson 2005 built a test from candidates that runs in arithmetic operations, polynomial in the input size and independent of how large the coins are.
Everyday systems — the 1-2-5 series, the US 1, 5, 10, 25 — are canonical, which is why the cashier’s rule has never failed you. The pre-decimal British set 1, 3, 6, 12, 24, 30, 60, 240 was not: 48 pence is 30 + 12 + 6 by greedy and 24 + 24 in the minimum, both facts from Pearson 2005’s account.
So “does greedy work here” is a question about the set 1, 3, 4 — not about greedy — and it has a polynomial-time answer. Which coin systems are canonical is a theorem about numbers; that greedy is correct on exactly those is a definition.
The Frobenius number: the largest unreachable amount. Representability is arithmetic: is reachable when with non-negative integers . The amounts that cannot be written this way are finite exactly when , and when they are finite the largest of them is the Frobenius number .
A coin of value 1 saves every amount, so for 1, 3, 4 the set of gaps is empty and there is no Frobenius number to name — the debt graph has a single residue class and the table in section 4 has no cell.
For two coprime coins there is a clean closed form,
and exactly amounts are missed (also Sylvester 1882). For 5, 7 that reads , and indeed 23 is the largest amount five- and seven-cent coins cannot make.
For three or more coins no closed form is known in general; the two-coin formula is the exception, not the rule. The chart below evaluates it exactly for twelve coprime pairs, in three families.
Largest amount two coprime coins cannot make — exactly a·b − a − b (Sylvester 1882)
1 minboss round
A coin system is 4, 6 and 10 — one even coin, and in fact all three are even. Does this system have a largest amount it cannot make?
NextHow does dynamic programming trace the shortest path on the denomination grid?
Tracing Paths Across the Denomination Grid
2 minthe simulation
Hover or click a cell: its predecessor cells light up and the exact recurrence that filled it appears here. Or press play to walk the fill order(28 cells in dependency order).
dp[i][j] = min( dp[i−1][j] (do not use coin i), dp[i][j−cᵢ] + 1 (use coin i again) ).
Fewest coins making 6 from [1, 3, 4].
Hover any cell to read its recurrence. The row is the coin types considered so far, the column is the amount, and the corner cell is C(6). Press play to fill in dependency order, then Trace solution to walk the winning representation back.
The rows are none, ≤ 1, ≤ 3, ≤ 4 and the columns are amounts . A cell is the fewest coins making using only the first coin types, so the bottom row is for the full system and the corner is .
Hover a filled cell and the two incoming edges light up. One is skip — climb a row, decline this coin type — and the other is use: step left by the coin’s value along the same row, spending a copy of it. The leftward step is exactly the debt-graph edge from section 2; the row climb is the bookkeeping that turns the one-dimensional recurrence into a table.
For your coins the corner reads 2, and the trace proves it: from ≤ 4 at amount 6 the winning chain drops to the ≤ 3 row at 6, then steps left by 3 twice, 6 → 3 → 0, for the two threes. The 4 is never spent, which is the whole lesson of 4 + 1 + 1 versus 3 + 3 made visible.
Watch the shape of the fill. Every cell depends on a cell above it and a cell to its left, so the row-major order fills each cell only after both of its parents — the table’s own topological order. And greedy has no cell of its own: it is one path, chosen without looking at the alternatives the table keeps.
NextWhat Frobenius coin gap determines whether an integer programming instance is solvable?
Currency Architecture and Integer Programs
2 minsystems
Four places this distance is the thing you compute.
- Dispensing machines. A vending or ATM machine holds a fixed set of denominations and wants the fewest coins or notes per payout. That is exactly the corner cell of section 4, and a currency designer who knows the system is canonical may ship the greedy rule instead of a table.
- Currency design. The “optimal denomination problem” asks which denominations minimize the average number of coins per transaction; the answer is a property of the set, computed by running the DP for every amount. Shallit 2003 argues for an 18-cent piece on these grounds.
- The simplest integer program. Minimum coins is subject to , integer: one equality, non-negativity, integrality. Every technique of integer programming is tested on this one-row instance first, and fixing the number of coin types makes it integer programming in a fixed dimension, which is polynomial time.
- Min-plus closure, elsewhere in this section. The same graph with weighted edges is least-cost routing; with instead of it is a longest path and Viterbi decoding. The coins are an adjacency matrix, and is a column of its closure.
Frobenius Numbers and Weak NP-Hardness
Skip this section if you only want the representation; it is about the problem’s place in complexity and about the largest gap, the Frobenius number.
Weakly NP-hard, not strongly. Make the coin values and the amount part of the input and decide whether is representable using at most coins. This is NP-complete (Lueker 1975 introduced the family of unbounded decisions that contains it). The hardness is weak: the table of section 4 runs in time, which is polynomial in the amount itself, so it is polynomial when is written in unary and exponential only in the number of bits of .
That is the signature of weak NP-hardness — a pseudo-polynomial algorithm exists, and strong NP-hardness would forbid one unless . Fix the number of denominations instead of freeing it, and the problem returns to polynomial time: Kannan 1992 computes the Frobenius number in polynomial time for every fixed , and the same fixed-dimension integer-programming route puts the minimum count back in polynomial time.
Compute the largest gap with a shortest path. The Frobenius number needs no DP over all amounts if you route correctly. Let be the smallest coin and build a graph on the residues , with an edge of weight for every coin . Then is the smallest representable amount congruent to , so the largest non-representable amount is
This is the coins-as-edges reading once more, now over residues rather than amounts, and it answers the system 4, 6, 9 from prompt 2’s explanation by hand: the farthest residue is , at distance , so . The table below is that same number, visible: the whole amount-11 column reads .
Hover or click a cell: its predecessor cells light up and the exact recurrence that filled it appears here. Or press play to walk the fill order(48 cells in dependency order).
dp[i][j] = min( dp[i−1][j] (do not use coin i), dp[i][j−cᵢ] + 1 (use coin i again) ).
Fewest coins making 11 from [4, 6, 9].
Coins 4, 6 and 9 — even coins with gcd 1. Every cell in the amount-11 column is infinite, and the panel names it: 11 is the Frobenius number of this system. Scroll the table sideways to reach the column.
No closed form returns that 11 from 4, 6, 9; the residue graph computed it, and even the smallest gap of a three-coin system is beyond a formula. In general the Frobenius problem is NP-hard (Ramírez-Alfonsín 1996) even though it is polynomial for fixed (Kannan 1992) — the same weak/strong split as the minimum-coin problem above.
Lineage & Attributions
- Sylvester 1882 — the Frobenius number of two coprime coins, , and the count of non-representable amounts.
- Lueker 1975 — Two NP-complete problems in nonnegative integer programming: the unbounded decision family that makes change-making NP-hard.
- Kannan 1992 — Lattice translates of a polytope and the Frobenius problem: a polynomial-time algorithm for the Frobenius number when the number of coins is fixed.
- Kozen–Zaks 1994 — the smallest counterexample to greedy lies below , giving the first test polynomial in the largest coin.
- Pearson 2005 — A polynomial-time algorithm for the change-making problem: canonicity decided in , and the pre-decimal British counterexample.
- Ramírez-Alfonsín 1996 — the Frobenius problem is NP-hard in general, even for a fixed amount of work per coin.
- Chang and Gill 1970 — the first finite certificate that greedy is optimal for all amounts, polynomial in the largest coin.
- Shallit 2003 — What this country needs is an 18c piece: the optimal denomination problem and the average-coins criterion.