Greedy Algorithms and Matroids proved a rule correct by exchange wherever the structure allowed it. Change the coins to 1, 3 and 4 and the largest-first rule returns three coins for an amount of six where two suffice. What replaces the rule is not a better rule: it is a recurrence that tries every first coin and keeps the best, and everything on this course is the cost of evaluating one.
Core ideas
One hard idea: optimal substructure, which is the property that licenses the recurrence and is a proof obligation rather than a hope. The other two are about what a failing instance does and does not establish.
Largest-first takes the 4, and is then solving for 2 with nothing better than a 1 available: 4 + 1 + 1, three coins, and it never reconsiders. The recurrence asks f(6) = 1 + min(f(5), f(3), f(2)), which is every legal first coin at once, and f(3) = 1 gives f(6) = 2. The difference is not cleverness. It is that one of them discards the alternatives before it knows what they cost.
If some fewest-coin way of making a begins with coin c, then what remains is a fewest-coin way of making a − c — because a cheaper way of making a − c could be substituted in and would give a cheaper way of making a, contradicting the first. That substitution argument is the whole justification for reading f(a) off smaller values of f, and a problem without it cannot be written as a recurrence over subproblems at all.
Six units from 1, 3 and 4 settles the question of whether largest-first is correct for every coin system: it is not, and one counterexample is enough. Now switch the lab to 1, 2 and 5 and the same rule is optimal at every amount you will type. That is a fact about that coin system, established by trial for the amounts you tried, and it is not a proof about the system, let alone about the rule.
The material
The problem, the instance where greed fails, the substitution argument, and the three routes the lab runs.
Given a set of coin denominations and an amount a, find the smallest number of coins, each denomination usable any number of times, that add to exactly a. If no multiset of the coins adds to a the answer is that the amount cannot be made, which is a result and not a failure.
Two things are being separated here, and conflating them is the reason this lesson comes first. A rule says what to do next: take the largest coin that fits. A recurrence says what the answer is in terms of smaller answers, and commits to nothing. Greedy Algorithms and Matroids is about the conditions under which a rule can be proved correct; this course is about what to do when it cannot.
Largest-first takes 4, leaving 2, then 1, leaving 1, then 1: 4 + 1 + 1, three coins. The lab reports the answer as 2 and the coins it uses as 3 + 3, re-added on the panel to 6. Both are legal ways to pay. Only one of them is fewest, and the rule does not find it on this input.
Notice how little it took. The coin system is three denominations and the amount is six; nothing here is adversarially large. A reader who has just spent a course proving greedy rules correct by exchange should read this as the boundary being drawn rather than as a trick, because the exchange argument that works for the fractional problem really does fail here, and the lesson after next is where that failure is made explicit on a second problem.
A problem has optimal substructure when an optimal solution to it contains, as a part, an optimal solution to a smaller instance of the same problem. The phrase names a proof obligation: you show that a better solution to the part could be cut in, which is what makes the recurrence a statement about optima rather than about some solutions.
Let f(a) be the fewest coins that add to a, with f(0) = 0 and f(a) undefined when no multiset adds to a. Then for every a > 0 that can be made, f(a) = 1 + min of f(a − c) over all coins c ≤ a for which a − c can be made.
Both directions. Any multiset of coins adding to a has a first coin c, and removing it leaves a multiset adding to a − c with one fewer coin; so f(a) ≥ 1 + f(a − c) for that c, and therefore f(a) ≥ 1 + min of f(a − c).
For the other direction, take the c attaining the minimum and a cheapest multiset for a − c; adding one c to it gives a multiset adding to a of size 1 + f(a − c), so f(a) ≤ 1 + min of f(a − c). The two inequalities give equality, and the substitution in the second half is the optimal-substructure argument doing its work.
□
The exchange argument behind a greedy rule needs more than optimal substructure: it needs the greedy choice property, that some optimal solution agrees with the rule on the first step. With coins 1, 3 and 4 at an amount of six there is no optimal solution containing a 4, so that property is simply false, and the exchange has nothing to exchange into. Optimal substructure survives untouched — which is precisely why the recurrence still works when the rule does not.
This is the split the Subject's ordering is built on. Greedy needs both properties and pays O(n log n); dynamic programming needs only the first and pays for it in table cells. Neither is stronger than the other; they assume different things, and the assumption is the thing to check.
The lab runs the same definition three ways: as a recursion with no memory, as the same recursion writing each answer down the first time, and as a table filled bottom-up. On this instance the three answers are all 2, and the costs are 24 calls, 14 calls, and 28 cells. The panel prints the ratio as an exact fraction — 12/7, about 1.7 times fewer calls — and says explicitly that the comparison is worth nothing unless the answers match, which is why they are checked before they are counted.
Read those three numbers carefully, because they do not say what a reader expects. The table fills 28 cells; the memo-free recursion makes 24 calls. On this input the exponential method does less work than the polynomial one. The proved bounds are unchanged — the table is Θ(nk) cells for n denominations and amount k, and the plain recursion is exponential in k — and the next lesson moves the amount to eighteen, where the same two routes cost 22 089 calls and 76 cells. A count at one size cannot order two growth rates, and this page is the smallest instance on the course where it visibly gets the order wrong.
Interactive
The same definition run without a memo, with one, and as a table
Method
The recurrence is cheap to write and expensive to evaluate, so it is worth one honest attempt to avoid it.
Write what the answer is in terms of smaller answers, with every legal first choice in the minimum. That expression is correct or it is not, independently of how you intend to evaluate it, and it is the thing the rest of the work has to agree with.
Assume an optimal solution whose part is not optimal, cut the better part in, and derive a contradiction. If the substitution does not go through — because the part interacts with the rest — the recurrence is not licensed and no amount of filling a table will repair it.
Spend the effort on a counterexample. Small denominations that are not multiples of one another are where they live: 1, 3, 4 breaks largest-first at six, and 1, 3, 4 is the smallest system this library knows of that does. Confirmations cost the same and buy nothing.
Run the recursion, the memo and the table on the instance you actually have. The ordering between them changes with size, and the only way to know which is cheaper at your size is the counter, not the complexity class.
Three costs are interesting only when the three answers are one answer. The lab prints a verdict for that first and says so in the banner; a cost comparison between a right method and a wrong one is not a comparison.
One row per coin type added to the system, one column per amount from zero up. Each row answers the same question the row above it answered, with one more denomination available. A dot is an amount that cannot be made with the coins so far.
The row for 1, 3 already contains the answer: f(3) = 1, so f(6) = 2 by taking two threes, and adding the 4 to the system changes nothing at the amount asked about. That is worth noticing, because the greedy rule's whole mistake was to use the 4 — the denomination that turns out to be irrelevant at six is the one it reaches for first.
Move the highlighted cell along the range control and the lab repaints the cells that cell read, in amber. That list is not a description of the recurrence written out beside it; it is recorded by the reads the recurrence itself performed, so it cannot disagree with what the code did. Two cells for every cell in the bottom row, here.
For a faded rehearsal, keep the coins and set the amount to 11 before running it. The supplied first move: largest-first pays 4 + 4 + 3, which is three coins. Decide whether the recurrence can do better, then check — and notice that being right about this one tells you nothing about twelve.
You should be able to write the recurrence for a problem, discharge optimal substructure by substitution, name the extra property a greedy rule would need, and read a cost comparison without turning it into a statement about growth.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.