Four guides in, the honest question
By now you have seen greedy succeed four times. In interval scheduling the "earliest finish time" rule was provably optimal by greedy stays ahead; in Huffman coding merging the two rarest symbols was justified by an exchange argument. Both proofs leaned on the same two pillars from the very first guide: the greedy-choice property (some optimal solution agrees with the first greedy pick) and optimal substructure (what is left after that pick is a smaller problem of the same kind). When both hold, greedy works; when we could prove them, we were done.
But four wins are not a theorem, and "it looks locally best" was never a proof — that warning has run through every guide in this rung. So two honest questions remain. First: is there a single structure that explains why greedy is correct, instead of a fresh ad-hoc argument every time? And second: when greedy is wrong, how do we know, and what do we do instead? This guide answers both. The structure has a name — the matroid — and the canonical failure has a name too: the 0/1 knapsack.
The matroid: one abstraction behind many greedy proofs
A matroid is a deliberately spare piece of bookkeeping. You start with a finite ground set of elements, and you declare some of its subsets to be independent — "allowed" or "conflict-free". The catch is that this family of independent sets is not arbitrary; it must obey just two rules. The hereditary rule: every subset of an independent set is independent (drop an element and you stay allowed). The exchange property: if A and B are both independent and A has fewer elements than B, then some element of B can be added to A while keeping A independent. That second rule is the whole engine, so hold onto it.
Where have you seen exactly this? In the spanning-tree story. Take a graph; call a set of edges "independent" if it contains no cycle (a forest). Drop an edge from a forest and it is still a forest — hereditary. And if forest A has fewer edges than forest B, then A has more connected components, so some edge of B must cross between two of A's pieces without closing a cycle — that is the exchange property, alive in the wild. This particular matroid is called the graphic matroid, and it is exactly why Kruskal's algorithm is correct.
Where greedy walks off a cliff: 0/1 knapsack
Now the cautionary tale. You have a knapsack of capacity W and a pile of items, each with a weight and a value, and you want the most valuable load that fits. In the fractional version — where you may take any fraction of an item — greedy is perfect: sort by value-per-weight ("density"), pour in the densest first, and at the end you slice off exactly enough of the next item to fill the bag. The fractional knapsack is, in fact, a matroid-flavored success: the greedy-choice property holds because the densest unit of value is always worth grabbing first.
The 0/1 knapsack changes one word — each item must be taken whole or not at all — and the same greedy rule collapses. Here is a tiny trace. Capacity W = 10. Item A: weight 6, value 7 (density about 1.17). Item B: weight 5, value 5 (density 1.0). Item C: weight 5, value 5 (density 1.0). Densest-first greedy grabs A, then has 4 capacity left and neither B nor C fits, for total value 7. But B + C together weigh exactly 10 and are worth 10. Greedy walked off a cliff: it scored 7 when 10 was available, and no amount of "but A looked best" rescues it.
What broke? Optimal substructure survives, but the greedy-choice property dies: there is no optimal solution that contains the first greedy pick (A). Taking A forecloses the B+C pairing forever, and the bag's capacity is a global constraint that couples the items — a choice that looks best in isolation poisons the choices that follow. That coupling is exactly what the matroid exchange property forbids and what 0/1 knapsack flaunts. The lesson is the one this rung keeps repeating: greedy is not a universal method, it is a gamble that pays off only when the problem has the right structure, and "locally best" is a hypothesis to be proved, never a proof.
What to reach for when greedy is wrong
Greedy failing is not the end of the road — it is a signpost. The most common next stop is dynamic programming, which keeps the surviving pillar (optimal substructure) but stops trusting a single greedy choice; instead it tries every choice and remembers the best. The 0/1 knapsack by DP builds a table over (items considered, capacity used) and at each item asks "better to take it or leave it?", carrying both possibilities forward. On our tiny example it would discover B+C = 10 because it never commits to A before checking the alternatives. The price is honest: that table is O(n * W) time and space, which is efficient when W is modest but is not truly polynomial in the input's bit-length — 0/1 knapsack is NP-hard, and no method is known that is fast for all inputs.
Sometimes even DP is too slow because the problem is NP-hard at its core, and then greedy makes a comeback in a humbler role — not as an exact method but as a fast approximation. The greedy set-cover algorithm repeatedly grabs the set covering the most still-uncovered elements; it does not find the optimum, but it provably comes within a factor of about ln(n) of it. Be precise about what such a guarantee means: an approximation ratio is a worst-case bound, a promise the answer is never worse than that factor times optimal — not a claim about the typical case, where it often does much better.
The whole rung, in one breath
Step back and the five guides form one arc. Guide one named the two pillars; guides two and three gave you the two master proof techniques (greedy stays ahead, and the exchange argument); guide four showed both at work in a real codec. This guide supplies the missing theory underneath them — the matroid — and the honest boundary line: greedy is correct exactly when the problem's allowed solutions have enough structure (a matroid, or a proof by exchange), and it is wrong, sometimes spectacularly, when a global constraint couples the choices, as in 0/1 knapsack.
Carry forward the habit, not the slogan. "Take the locally best option" is a tempting reflex, but the value of everything in this rung is the discipline of doubting it — demanding a proof, or a counterexample, before you trust a greedy algorithm with a problem that matters. That discipline is exactly the mindset the next rung on dynamic programming will reward, where remembering and reconsidering replaces the single irreversible greedy commitment.