Answers · Making it fast enough
When is picking the locally best option actually guaranteed to give the best overall answer?
In shortOnly when a proof shows that some best overall answer can contain the locally best first choice, and the same holds for every later step; otherwise one counterexample can break it.
The locally best step is guaranteed to be part of a best overall answer only when an exchange argument proves it. You must show that every optimal solution can be modified to include the step your rule would take first, without becoming worse, and then the same argument must apply to the remaining problem after that step is fixed. If that proof goes through, one pass is enough. If it does not, there is no guarantee, and one counterexample is enough to settle the matter.
- any best possible answer
- the choice the rule would make first
- a best answer modified to include that choice
The proof obligation
Take a room that holds one talk at a time and talks (0,6), (1,4), (5,7), (3,8), (8,9). Sorting by finish gives (1,4), (0,6), (5,7), (3,8), (8,9). The rule takes (1,4), then (5,7) because 5 is at least 4, then (8,9) because 8 is at least 7, so it fits three talks. The exchange argument says any best schedule that does not start with (1,4) can swap its first talk for (1,4). That replacement finishes at 4, no later than the talk it replaced, so every later talk still fits and the count is unchanged. The modified schedule is still best and now starts with the earliest finish, so taking it first is safe. The same reasoning then applies to the talks that remain after 4.
This is why the count of three is not an accident of the example. The proof does not compare all schedules; it compares any best schedule with one modified best schedule that agrees with the local choice. That is enough, because once the first choice is fixed, the rest of the problem is the same kind of problem with a smaller list. The method needs no table and no stored answers, only a sort and a single pass. What it does need is the paragraph above, because without the exchange the pass is just a plausible habit.
The counterexample
The natural guess fails because best at this moment is a claim about one step, while optimal is a claim about the whole answer. Make 6 from coins of 1, 3 and 4. Taking the largest coin first gives 4, then 1, then 1: three coins. The best answer is 3 and 3: two coins. The exchange gets stuck in exactly the place that matters. To put 4 into the best answer you must break 3 and 3, and 4 plus 1 plus 1 is worse than 3 plus 3. A locally best choice has blocked a combination that is globally better.
That failure is hard to see by testing. It needs an early choice that is good enough to be taken and that consumes enough of the budget to rule out two or more later choices which together beat it. Small examples often lack that shape, so the method passes hand-written cases and can pass a sample of ordinary data. Nothing crashes and no warning appears. The answer is simply a little worse on the one input where the blocking matters. Agreement on random inputs is evidence, not proof. A disagreement is a counterexample and settles the question permanently.
Where the guarantee stops
The guarantee is a property of the specific rule and the specific problem, not of the fact that the rule looks sensible. Whole-item packing by value per kilo fails because swapping in the denser item may add weight, so something else must come out, and what comes out may be worth more than the gain. Divisible packing by value per kilo succeeds because you can swap in as much of the denser item as fits and remove an equal weight of something less dense. Two problems one word apart sit on opposite sides of the line. If the exchange argument only proves the first choice, it must still prove the second and the rest. If it gets stuck, build the input where it gets stuck. If neither proof nor counterexample appears, write the table version as a check and compare the two on a few thousand random inputs. If they always agree but the proof still will not come, ship the table, because an unproven single pass that is probably right is not worth being quietly wrong.
Worth keeping
- An exchange argument guarantees a local choice only if any optimal solution can be modified to include that choice without becoming worse.
- A single counterexample disproves a local-choice method, while agreement on random tests is evidence rather than proof.
- The same wording can describe two problems on opposite sides of the line: whole-item packing fails where divisible packing succeeds.
Where this goes next
This question is one step of Answers Built From Smaller Answers, a course that works through its subject from the beginning. The page that teaches this part of it is When You Do Not Need the Table, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- What's the difference between memoized recursion and filling a DP table bottom-up?Memoised recursion keeps the calls and only solves states it reaches; a bottom-up table removes the calls, fills every entry in a dependency-safe order, and is usually faster when most entries are needed.
- Why is merge sort O(n log n) when it keeps splitting the array in half?Splitting in half gives about twenty levels for a million items, and merging at every level still touches all million items, so the total is twenty million rather than a million times a million.
- How does binary search find something in a sorted list so fast?Binary search is fast because each comparison halves the remaining sorted range, so a thousand items need about ten probes and a million need about twenty, rather than one probe per item.
- What is memoization and why does caching recursive results make it so much faster?Memoisation stores each answer once and reuses it, so a recursion that repeats the same subproblems stops redoing work and becomes a table lookup instead.
- Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
- Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.