when greedy fails
Greedy is seductive: it is short to write, fast to run, and often gives an answer that looks reasonable. The danger is precisely that — a greedy program almost always returns SOMETHING, and that something can be silently, confidently wrong. The skill is learning to suspect greed before trusting it, and to test it before believing it.
Greedy fails whenever a locally best choice forecloses a globally better future — when a choice that looks best now sacrifices possibilities worth more later. Several classic warning signs help you spot this. First, indivisibility or hard capacity limits: 0/1 knapsack fails because you cannot shave an item to fit, so the densest-first choice can block a better whole-item combination. Second, the objective interacting across choices: coin change with arbitrary denominations fails because taking the biggest coin can strand you with an awkward remainder. Third, plausible-but-distinct greedy rules disagreeing: if 'shortest first' and 'earliest finish' and 'fewest conflicts' all sound reasonable but give different answers, at most one can be optimal, so none is trustworthy without proof. The practical defense is twofold: try to construct a small counterexample (often three or four items is enough — for 0/1 knapsack, capacity 50 with items (value 60, weight 10), (value 100, weight 20), (value 120, weight 30), where density-greedy takes the first two for value 160 but the optimum takes the last two for value 220), and try to construct a proof (exchange or staying-ahead, or a matroid). If neither succeeds, do not ship the greedy.
The deepest reason to respect this: greedy correctness is fragile under tiny problem changes. Fractional knapsack to 0/1 knapsack, single-room scheduling to coin change, MST to traveling-salesman — each pair has nearly identical surface form but opposite greedy verdicts, separated by one assumption (divisibility, structure, the matroid property). When greedy fails, the standard rescue is dynamic programming if the problem has optimal substructure with overlapping subproblems, or approximation algorithms if it is NP-hard. The point of this entry is not to memorize a list but to build the reflex: a greedy that 'looks right' has earned nothing until it has a counterexample search behind it and a proof in front of it.
0/1 knapsack, capacity 50. Items (value, weight): (60, 10) density 6, (100, 20) density 5, (120, 30) density 4. Density-greedy takes the first two for value 60 + 100 = 160 and wastes 20 capacity; the optimum is the last two, weight 20 + 30 = 50 exactly for value 100 + 120 = 220. Greedy loses.
A small counterexample is the fastest disproof; if you cannot build one, try to build a proof — never trust greed on looks alone.
A greedy that 'looks right' is unproven. Before trusting it, search for a small counterexample AND attempt an exchange/staying-ahead proof or a matroid; failing greedy usually means dynamic programming or approximation instead.