When greedy fails — 0 - 1 knapsack counter-example: Visual walkthrough

Step 1 — The bag, drawn as a ruler

WHAT. A knapsack is just a container with one limit: how much total weight it can hold. Call that limit the capacity, written $W$ . In our story $W = 50$ . That's all — no shape, no volume, just a single number-line of room.

WHY draw it as a ruler. Because "does it fit?" is only ever a comparison of numbers: the weight I've packed so far versus $W$ . A horizontal bar from $0$ to $50$ turns every packing decision into "how far along the bar am I?"

PICTURE. The bar below runs from $0$ (empty) to $W = 50$ (full). Every item we pack will be a colored block laid along this bar. When the colored part reaches the far edge, the bag is exactly full; any bare bar at the end is wasted capacity — room we paid for but never used.

Step 2 — The three items, and what "weight" and "value" mean

WHAT. We have $n$ items in total, where $n$ is just how many items there are — here $n = 3$ , which we label A, B, C. A single item $i$ carries two numbers:

its weight $w_{i}$ — how much bar it eats up, and
its value $v_{i}$ — how many "points" you score for taking it.

Our three items:

WHY two numbers, not one. If items had only weight, packing would be trivial. The tension — the entire difficulty — is that the thing you want (value) and the thing that limits you (weight) are different numbers. A block can be long but cheap, or short but rich.

PICTURE. Each item is drawn to scale: its width = weight, its height/label = value. Notice A is short (10 wide) but proud (60), C is long (30 wide) but only 120. Your eye should already feel the conflict.

Step 3 — Density: the number greedy trusts

WHAT. Greedy needs a single "how good is this item?" score to sort by. It uses value-density: $ρ_{i} = \frac{v _{i}}{w _{i}} ρ_{i} = "points per kilo" v_{i} = prize \div w_{i} = bar eaten$

Read the symbol out loud: $ρ_{i}$ ("rho-sub- $i$ ") is value divided by weight — how many points each unit of weight buys you.

WHY divide? Because "which item is best per unit of the scarce resource?" is the natural greedy question. Weight is scarce (only 50 of it). Dividing value by weight tells you the exchange rate: points earned for each unit of the limited bar you spend.

PICTURE. Draw each item as a slope: rise = value, run = weight. A steep line = high density = "greedy loves it." The slopes rank A steepest, then B, then C. Greedy will pack in this order.

Step 4 — Greedy packs: A, then B, then… stuck

WHAT. The greedy rule: sort by $ρ_{i}$ descending (A, B, C), walk the list, take an item if it still fits.

Take A ( $w_{A} = 10$ ): bar filled $0 \to 10$ , value $= 60$ , room left $= 50 - 10 = 40$ . Why? Highest density.
Take B ( $w_{B} = 20$ ): bar filled $10 \to 30$ , value $= 60 + 100 = 160$ , room left $= 50 - 30 = 20$ . Why? Next-highest, still fits ( $20 \leq 40$ ).
Try C ( $w_{C} = 30$ ): needs 30, but only 20 left. $30 > 20$ → doesn't fit. Skip.

WHY it stops. Greedy never unpacks. Once A sits in the bag, its 10 units are gone forever. That leaves a 20-unit gap that C (which needs 30) can never squeeze into.

PICTURE. Watch the bar fill left-to-right: blue A, then orange B, then a red bare gap of 20 at the right end. C floats above, too long to drop in. Greedy's score freezes at $160$ .

Step 5 — The optimum: drop A, take B + C

WHAT. Now try the combination greedy refused to consider: leave A on the table, take B and C.

$20 + 30 w_{B} + w_{C} = 50 = W 100 + 120 v_{B} + v_{C} = 220$

WHY this wins. By sacrificing the densest item A, we free the 10 units that were blocking C. Now B (20) and C (30) tile the bar exactly — $20 + 30 = 50$ , zero waste. The bag is packed perfectly, and $220 > 160$ .

PICTURE. Same ruler, new packing: orange B then green C, meeting flush at 50. No red gap. The number 220 sits above a completely full bar. Compare it directly against Step 4's leaky 160.

Step 6 — Why the fractional version would have been fine

WHAT. In fractional knapsack you may slice items ( $x_{i} \in [0, 1]$ ). Redo greedy allowing slivers:

Take all of A (10) and all of B (20) → room left 20.
Take $\frac{20}{30} = \frac{2}{3}$ of C → weight $20$ , value $\frac{2}{3} \times 120 = 80$ .
Total value $= 60 + 100 + 80 = 240$ .

WHY greedy suddenly wins here. With slivers there is never a gap — you always top the bag to exactly $W$ . The leftover 20 gets filled by a fraction of the next item, so density-order really does squeeze out the most value. The exchange argument works precisely because you can swap arbitrarily small pieces.

PICTURE. The bar fills A, B, then a striped 2/3-slice of C exactly reaching 50. No red. This 240 is the fractional optimum — and it beats even the 0/1 optimum of 220, because slicing is a superpower 0/1 forbids.

Step 7 — The fix in one glance: try BOTH choices (DP)

WHAT. Dynamic programming never commits early. For every item it asks both questions — skip it or take it. To bookkeep this, introduce a remaining-room number, written with a lowercase $c$ (a plain integer that runs $0, 1, 2, \dots, W$ — do not confuse this counting variable $c$ with the item C from our table). Then $K (i, c)$ means "best value achievable using only items $1 \dots i$ when the bag still has $c$ units of room":

$K (i, c) = max (skip item i K (i - 1, c), take item i, if w_{i} \leq c v_{i} + K (i - 1, c - w_{i}))$

Read it: $i$ = how many items we're allowed to consider so far; $c$ = an integer amount of leftover room, any value from $0$ up to $W$ . The $max$ compares "leave $i$ out" (room stays $c$ ) against "put $i$ in and solve the smaller bag $c - w_{i}$ ."

WHY it can't be fooled. Greedy died because it decided A before knowing about B+C. DP decides nothing early — it explores skip and take for every item, so no future combination is ever foreclosed. The work it does is one comparison for each (item, room) pair: $n$ items times $W + 1$ possible room values, i.e. runtime $O (nW)$ — here $n = 3$ items and $W = 50$ .

PICTURE. A branching tree: at each item the path forks take / skip. Greedy walked a single straight line (A→B→stuck, value 160). DP explores every branch; the winning path skip-A → take-B → take-C lights up green at 220.

The one-picture summary

Everything on one canvas: three packings of the same 50-unit ruler.

Greedy (A + B): a leaky bar, red gap of 20, value 160.
0/1 optimum (B + C): a full bar, no gap, value 220.
Fractional (A + B + ⅔C): full bar via a slice, value 240.

The story reads top-to-bottom: the more freedom you have (whole-only → fractions), the fuller the bag and the higher the score — and the one thing greedy's density rule can't handle is the gap forced by the whole-item rule.

Recall Feynman retelling — the whole walkthrough in plain words

Picture the bag as a 50-cm strip of tape you must cover with colored blocks; each block is as wide as its weight and worth the number printed on it. Greedy grabs blocks in order of "worth-per-centimetre": first the little rich blue block A, then the orange block B. Now only 20 cm of tape is bare, but green block C is 30 cm wide — too fat to fit. Greedy shrugs and stops at 160, leaving a 20-cm bald patch. The clever move is to refuse the shiny A block on purpose: put down B (20 cm) and C (30 cm) and they cover the tape perfectly, scoring 220. If you were allowed to cut blocks (the fractional world), greedy would win — you'd just snip C to plug any gap and reach 240. But whole-block rules leave gaps, and gaps are lost points. So instead of grabbing greedily, you try both "keep it" and "skip it" for every block and remember the best plan for each possible amount of leftover tape — that patient try-both bookkeeping is dynamic programming, and it always finds the 220.

Connections

Parent: When greedy fails
Greedy Algorithms · Fractional Knapsack · Dynamic Programming
Optimal Substructure · Greedy-Choice Property · Exchange Argument
Approximation Algorithms · NP-hardness