why greedy fails on 0/1 knapsack

Recall the divisible (fractional) knapsack, where sorting by value-per-weight and filling greedily is provably optimal. The 0/1 knapsack looks almost identical — same items, same value, same weight, same capacity — with one tiny change: each item must be taken whole or left behind, no fractions. That single change destroys greedy's optimality, and seeing exactly why is the clearest lesson in this whole field about how brittle greed can be.

Here is the failure in full. Capacity 50. Items (value, weight): item 1 = (60, 10) with density 6, item 2 = (100, 20) with density 5, item 3 = (120, 30) with density 4. Density-greedy takes item 1 (10 used), then item 2 (30 used), then tries item 3 but only 20 capacity remains and item 3 weighs 30 — in the 0/1 world it cannot be sliced, so it is left out entirely, giving value 60 + 100 = 160 with 20 units of capacity wasted. The true optimum takes items 2 and 3: weight 20 + 30 = 50 fills the sack exactly for value 100 + 120 = 220 — much better. Greedy's mistake was committing to the high-density item 1, whose weight was awkward, instead of the combination that packs the capacity perfectly. The fractional exchange argument fails precisely because you can no longer swap a partial kilogram to repair a suboptimal packing; indivisibility removes the move the proof depended on.

Structurally, the feasible sets of 0/1 knapsack do not form a matroid — they violate the exchange property — so no weight-based greedy rule can be universally optimal, by the converse of the matroid-greedy theorem. The correct method is dynamic programming: build a table over items and capacities, achieving O(n * W) time where W is the capacity (this is pseudo-polynomial, since W can be exponential in the input's bit-length, and 0/1 knapsack is NP-hard in general; an FPTAS gives near-optimal answers fast when you can tolerate a small error). The enduring takeaway: 0/1 knapsack is the canonical 'greedy looks right but is wrong' problem, and its lesson is that surface similarity to a greedy-solvable problem guarantees nothing — you must check divisibility, the exchange property, or build a counterexample.