Worked examples — When greedy fails — 0 - 1 knapsack counter-example

This page is a drill room. The parent note proved once that density-greedy fails. Here we hit every kind of instance so you never meet a case you haven't already seen worked out.

Before we start, one reminder of the vocabulary — no symbol used before it is named.

---

The scenario matrix

Each row below is a case class — a distinct way the greedy-vs-optimal story can play out. The worked examples afterward each carry a tag like [Cell 3] so you can see we covered them all.

Cell	Case class	What it stresses	Example
1	Greedy = OPT (lucky)	greedy can still be right	Ex 1
2	Greedy < OPT (the classic gap)	wasted capacity blocks a combo	Ex 2
3	Sort-by-value greedy fails	wrong key hogs capacity	Ex 3
4	Degenerate: nothing fits	zero-item answer	Ex 4
5	Degenerate: everything fits	capacity $\ge$ total weight	Ex 5
6	Zero-value / zero-weight items	edge inputs $v_i=0$, $w_i=0$	Ex 6
7	Greedy arbitrarily bad	tiny high-density item ruins it	Ex 7
8	½-approximation rescue	the guaranteed cheap fix	Ex 8
9	Real-world word problem	translate → solve	Ex 9
10	Exam twist: build the DP table	fill $K(i,c)$ by hand	Ex 10

Read each example's Forecast and guess before scrolling. That guess is the point.

---

Figure 1. A single stacked bar up to the capacity line $W=50$: A (orange, 10) + B (violet, 20) + C (magenta, 20) fills the bag exactly to $50$ with no gap, total value $230$.

1. Densities. ${\rho }_A=60/10=6$, ${\rho }_B=100/20=5$, ${\rho }_C=70/20=3.5$. Why this step? Greedy's only input is the density ordering, so compute it first.
2. Greedy walk. Take A (room $50\to 40$, value $60$). Take B (room $40\to 20$, value $160$). Try C (needs $20$, room is exactly $20$ → fits), value $230$. Why this step? Greedy takes each item if it still fits; here nothing gets skipped.
3. Greedy total $=60+100+70=230$, room left $=0$. Why this step? Sum the taken values and confirm the bag is exactly full — zero waste is the warning sign that greedy might already be optimal.
4. Is anything better? Total weight of all three is $10+20+20=50=W$, so all items fit at once. You literally cannot beat "take everything". Why this step? When the whole set fits, OPT = sum of all values, no search needed.

Verify: Greedy $=230$, OPT $=230$. Equal ✓.

---

Figure 2. Two stacked bars up to the capacity line $W=50$. Left (orange/violet) is greedy A+B, topping out at $30$ with a hatched empty GAP of $20$ and total value $160$. Right (violet/magenta) is B+C, filling all $50$ with total value $220$. The empty slot on the left is exactly the room item C needed.

1. Densities. ${\rho }_A=6$, ${\rho }_B=5$, ${\rho }_C=4$. Order: A, B, C. Why this step? Establish greedy's marching order.
2. Greedy walk. Take A (room $\to 40$, val $60$). Take B (room $\to 20$, val $160$). Try C (needs $30>20$) → skip. Why this step? C can't be sliced (0/1 rule), so greedy stops with 20 units wasted.
3. Greedy total $=160$. Why this step? Sum the values of the taken items A+B to record greedy's final score before comparing to OPT.
4. Find OPT. Try B+C: weight $20+30=50=W$ ✓, value $100+120=220$. Why this step? The wasted 20 units in step 2 is a hint that a lower-density item (C) could fill the bag better. Swapping out A for C recovers that gap.

Verify: Greedy $=160$, OPT $=220$. Shortfall $=60$ coins, i.e. greedy is $160/220\approx 72.7\%$ of optimal (≈27% worse) ✓.

---

Figure 3. Two stacked bars to $W=50$. Left (magenta) is value-greedy: one giant item H filling all $50$ but worth only $130$. Right (violet/orange) is P+Q filling all $50$ and worth $220$. Same fill, far more value — the heavy item was a value hog.

1. Sort by value (not density). Order: H$(130)$, Q$(120)$, P$(100)$. Why this step? We're testing the tempting "maximize value → take valuable things first" heuristic.
2. Value-greedy walk. Take H (weight $50$, room $50\to 0$, value $130$). Room is $0$ → skip P, skip Q. Why this step? H is heavy and valuable; grabbing it monopolizes the whole bag.
3. Value-greedy total $=130$. Why this step? H is the only item taken, so its value alone is the heuristic's score — record it before finding the true optimum.
4. Find OPT. P+Q: weight $20+30=50=W$ ✓, value $100+120=220$. Why this step? Two lighter items together out-value the single heavy hog.

Verify: value-greedy $=130$, OPT $=220$. $130<220$ ✓.

---

Figure 4. A tiny capacity line at $W=5$ far below three item-weight bars (10, 20, 30). None reach — everything is over the line, so the loaded bar is empty (value 0).

1. Check each item against $W$. $w_A=10>5$, $w_B=20>5$, $w_C=30>5$. Every item is too heavy. Why this step? The "take if it fits" test fails for all — the greedy walk takes nothing.
2. Greedy total $=0$, room left $=5$. Why this step? Empty subset is the only legal solution.
3. OPT. No subset (other than $\varnothing$) has weight $\le 5$, so OPT $=0$ too. Why this step? A degenerate instance where greedy and OPT trivially agree at zero.

Verify: Greedy $=0$, OPT $=0$ ✓.

---

1. Total weight. $10+20+30=60\le 100=W$. Why this step? If the whole set fits, the capacity constraint is inactive.
2. Greedy walk. Take A, B, C — each fits in the ever-shrinking-but-still-ample room. Total $=60+100+120=280$. Why this step? Greedy never has to skip; it grabs all.
3. OPT $=280$ (take everything — adding an item never lowers a nonnegative-value total). Why this step? With slack capacity, OPT = sum of all values.

Verify: Greedy $=280$, OPT $=280$ ✓.

---

1. Densities — careful with the zeros. ${\rho }_A=6$. For Z: $w_Z=0$, so by the infinite-density convention above, Z gets the priority label $+\infty$ ("free value" ⇒ sorts first). For N: ${\rho }_N=0/15=0$ (sorts last). Why this step? $w=0$ has no finite ratio, so we use the convention we defined earlier — Z is tagged "always first"; a genuine ordering still exists: Z, A, N.
2. Greedy walk (rule as written). Take Z (label $+\infty$, weight $0$ → room stays $50$, value $5$). Take A (room $50\to 40$, value $65$). Try N (weight $15\le 40$ → fits, so greedy takes it), value $65+0=65$, room $\to 25$. Why this step? We obey "take if it fits" literally — N is taken even though it is useless, because the rule never inspects value.
3. Greedy total $=65$ (Z + A + N; N contributed $0$). Why this step? Sum the taken values $5+60+0$; the useless N leaves the total unchanged, which is exactly the point being demonstrated.
4. OPT. Z is free positive value ⇒ always in ($+5$). A is the only positive-value weighted item ($+60$). N contributes $0$ so including or excluding it cannot change the score. OPT $=5+60=65$. Why this step? Here greedy = OPT anyway — the zero-value item was harmless because enough room remained. In a tighter bag, blindly taking N could waste room a positive item needed, which is why real solvers add a guard "don't take $v_i=0$ items"; but that guard is an optimization on top of the base rule, not the base rule itself.

Verify: Greedy $=65$, OPT $=65$ ✓.

---

Figure 5. Capacity line at $W=1000$. Greedy bar (orange) shows a sliver of height 1 (item T, value 2) with a vast hatched gap of 999. Optimal bar (magenta) is one solid block filling all 1000 (item M, value 1500). The sliver blocked the giant.

1. Densities. ${\rho }_T=2/1=2$, ${\rho }_M=1500/1000=1.5$. Order: T, M. Why this step? T looks best per kilo.
2. Greedy walk. Take T (room $1000\to 999$, value $2$). Try M (needs $1000>999$) → skip. Why this step? The tiny item stole 1 unit of room, and that's enough to block the giant.
3. Greedy total $=2$. Why this step? Only T was taken, so its value alone is greedy's score — record it before comparing.
4. OPT. Just take M: weight $1000=W$ ✓, value $1500$. Why this step? Dropping the tiny lure lets the giant fit.

Verify: Greedy $=2$, OPT $=1500$, ratio $<0.5$ ✓.

---

1. Density-greedy value (from Ex 7) $=2$. Why this step? One of the two candidates.
2. Best single item that fits. Both T ($v=2$) and M ($v=1500$, and $1000\le 1000$ so it fits) are candidates; the best is M $=1500$. Why this step? This second candidate protects against exactly the Ex-7 disaster — a lone giant that greedy skipped.
3. Heuristic answer $=\max (2,1500)=1500$. Why this step? Take the better of the two candidates.

Verify: HEUR $=1500$, OPT $=1500$, and $1500\ge 0.5\times 1500$ ✓.

---

Figure 6. A drone payload bar capped at $50$ kg. Naive dispatch loads laptop+monitor (orange/violet) to $30$ kg with a $20$-kg empty gap, fees \160$.Optimalloadsmonitor+printer(violet/magenta)fillingall$50$kg,fees$$220$.

1. Translate to knapsack. $W=50$; items A=laptop$(10,60)$, B=monitor$(20,100)$, C=printer$(30,120)$. Why this step? Word problems are knapsack in disguise: capacity = payload, value = fee, integrality = "can't split a parcel".
2. Density-greedy (what a naive dispatcher does). A then B = \160$,printerskipped(needs$30$,only$20$ left). Why this step? Shows the tempting-but-wrong shortcut.
3. Optimal load. monitor + printer $=20+30=50$ kg $=W$, fees \100 + $120 = $220$. Why this step? Fills the payload exactly; the story's "can't split" is the 0/1 constraint that makes DP necessary.

Verify: naive $=160$, optimal $=220$ ✓.

---

Figure 7. The filled DP grid. Rows are $i=0,1,2,3$ (items unlocked, orange labels); columns are $c=\mathrm{0..5}$ (violet labels). Each cell holds $K(i,c)$. The bottom-right cell $K(3,5)=7$ is highlighted magenta; an arrow shows the "skip" link from the cell directly above.

1. Row 0 (no items). $K(0,c)=0$ for all $c\in \{0,1,2,3,4,5\}$. Why this step? Base case: no items → no value. Every DP grows from here.
2. Row 1 (item $w=2,v=3$). For $c<2$: $K=0$. For $c\ge 2$: $\max (0,3+K(0,c-2))=3$. Row1 $=[0,0,3,3,3,3]$. Why this step? One item worth 3 fits once we have room $\ge 2$; more room doesn't add value.
3. Row 2 (item $w=3,v=4$).
   • $c=0,1,2$: $w_2=3>c$ → too heavy → copy Row1 → $0,0,3$.
   • $c=3$: $\max (K_1(3)=3,4+K_1(0)=4)=4$.
   • $c=4$: $\max (K_1(4)=3,4+K_1(1)=4)=4$.
   • $c=5$: $\max (K_1(5)=3,4+K_1(2)=4+3=7)=7$. Row2 $=[0,0,3,4,4,7]$. Why this step? At $c=5$ we take both items 1 and 2 ($2+3=5$ kg, $3+4=7$).
4. Row 3 (item $w=4,v=5$).
   • $c=0,1,2,3$: $w_3=4>c$ → too heavy → copy Row2 → $0,0,3,4$.
   • $c=4$: $\max (K_2(4)=4,5+K_2(0)=5)=5$.
   • $c=5$: $\max (K_2(5)=7,5+K_2(1)=5)=7$. Row3 $=[0,0,3,4,5,7]$. Why this step? At $c=5$, keeping items 1+2 (value 7) beats taking item 3 alone (value 5).
5. Answer $K(3,5)=7$, achieved by items 1+2. Why this step? Bottom-right cell is the whole problem's answer — no early commitment, both take/skip tried at every cell.

Verify: $K(3,5)=7$, and brute force over all subsets of weight $\le 5$ agrees ✓.

---

Recall Quick self-quiz over the matrix

When is density-greedy guaranteed correct on 0/1 knapsack? ::: When all items fit ($W\ge \sum w_i$, Cell 5) or trivially none fit (Cell 4) — i.e. when capacity never forces a choice. Does the fixed greedy rule take a $v=0$ item that fits? ::: Yes — the rule is "take iff it fits" and never inspects value; Ex 6 shows it takes N and simply gains nothing. Ex 7 greedy score vs OPT? ::: $2$ vs $1500$ — greedy captured ~0.13%, proving no guarantee. What two candidates does the ½-approximation compare? ::: density-greedy's value, and the single most valuable item that fits. What does $K(i,c)$ mean? ::: The max value using only the first $i$ items with a sub-bag of capacity $c$; the answer is $K(n,W)$. Final answer of the DP table in Ex 10? ::: $K(3,5)=7$ (items 1 and 2). How do you handle a zero-weight positive-value item? ::: Give it priority $+\infty$ (always first, always take) — Cell 6.

---

Connections

• Parent: When greedy fails — the theory these examples drill
• Dynamic Programming — Ex 10 is DP by hand
• Fractional Knapsack — where greedy is optimal (contrast to Ex 2); the source of the upper-bound lemma in Ex 8
• Greedy Algorithms · Greedy-Choice Property · Exchange Argument — why the proof holds there, not here
• Approximation Algorithms — the ½-guarantee of Ex 8
• NP-hardness — why no fast exact greedy key exists
• Optimal Substructure — the property the DP recurrence exploits