Exercises — When greedy fails — 0 - 1 knapsack counter-example

The bag is a fixed-width box of capacity $W$. Greedy fills from the left with the densest items first (tall amber bars = high value-per-width). When the next dense item is wider than the leftover slot, greedy skips it and the slot stays empty — that empty slot (the amber-outlined gap) is exactly the value greedy throws away.

1. Greedy-choice property — some globally optimal solution contains the locally best (greedy) choice, so committing to it never rules out reaching an optimum. (See Greedy-Choice Property.)
2. Optimal substructure — the optimal solution of the whole problem is built from optimal solutions of subproblems (see Optimal Substructure). Both are typically proven by an Exchange Argument. 0/1 knapsack has optimal substructure but lacks the greedy-choice property, which is why greedy fails.

${\rho }_A=\frac{60}{10}=6.0,{\rho }_B=\frac{100}{20}=5.0,{\rho }_C=\frac{120}{30}=4.0$ Descending order: $A\succ B\succ C$. This is the order greedy walks the list in.

Walk $A\succ B\succ C$ with remaining capacity $r$, start $r=50$:

• Take A (needs 10 ≤ 50): value $60$, $r=40$.
• Take B (needs 20 ≤ 40): value $60+100=160$, $r=20$.
• Try C (needs 30 > 20): doesn't fit, skip. Chosen $\{A,B\}$, total value $160$, wasted capacity $r=20$.

All subsets, weight then value (feasible = weight ≤ 50):

Optimum $=\{B,C\}=220$. Greedy got $160<220$, so greedy is not optimal here. (This is the Fractional Knapsack–vs–0/1 contrast: only 0/1 can strand capacity.)

Recurrence: $K(i,c)=\max (K(i-1,c),v_i+K(i-1,c-w_i))$ if $w_i\le c$, else $K(i-1,c)$. Base row $K(0,c)=0$.

Why these two cases exhaust everything: for item $i$ there are only two possible fates — it is either in the chosen set or out. That is a complete, non-overlapping split of all solutions.

• Out (skip): if $i$ is not chosen, the best we can do is the best over the remaining items $\mathrm{1..}i-1$ with the same capacity $c$ — that is exactly $K(i-1,c)$.
• In (take): if $i$ is chosen, it consumes $w_i$ of capacity and contributes $v_i$; whatever is packed alongside it must be an optimal pack of items $\mathrm{1..}i-1$ in the reduced capacity $c-w_i$ — that is $v_i+K(i-1,c-w_i)$, and it is only legal when $w_i\le c$. Because "in" and "out" cover all possibilities, taking the $\max$ of the two is guaranteed to be the true best — and the fact that each branch re-uses an optimal smaller answer is precisely Optimal Substructure. This is why DP never commits early: it evaluates both fates instead of guessing one.

Order items A$(10,60)$, B$(20,100)$, C$(30,120)$.

Sample step, $K(3,50)$: skip C → $K(2,50)=160$; take C → $120+K(2,50-30)=120+K(2,20)=120+100=220$. Max is $220$. ✓ matches B+C.

The cell $K(3,50)=220$ (and its parent $K(2,20)=100$, meaning "use B in a size-20 slot"). DP considered the branch "skip A entirely" — that is what leaves room for both B (20) and C (30) to sum to exactly 50. Greedy committed to A first (highest density) and could never un-commit, so it never explored the "skip A" universe. This is the Optimal Substructure paying off: DP keeps the best answer for every capacity, including capacities that only make sense if you skip a dense item.

Capacity $W=100$. Items (listed X, Y, Z — this order also fixes tie-breaks):

• X: $w=1$, $v=2$, $\rho =2.0$ (densest, but tiny).
• Y: $w=100$, $v=100$, $\rho =1.0$.
• Z: $w=100$, $v=100$, $\rho =1.0$.

Greedy: takes X first (density 2.0) → $r=100-1=99$. Now Y and Z each need weight 100, but only 99 units remain, so neither fits. Greedy value $=2$. Optimum: take Y alone (or Z alone), weight $100\le 100$, value $=100$. So greedy $=2$, optimum $=100$. Ratio $2/100=0.02<0.5$ — density-greedy is here 50× worse. The mechanism is exactly the parent's warning: X's single unit of weight drops the remaining capacity from 100 to 99, which is just enough to lock out the heavy 100-value items. Pushing X's value toward $ϵ$ keeps the same blocking effect and drives the ratio → 0, showing density-greedy can be arbitrarily bad.

Heuristic: return $\max (\text{density-greedy value},\text{best single item that fits})$.

• Density-greedy value $=2$ (from 4.1).
• Best single item that fits in $W=100$: Y or Z, value $100$.
• $\max (2,100)=100$. Optimum is $100$, so the heuristic returns $100\ge \frac{1}{2}\cdot 100=50$. ✓ It meets the ½-approximation guarantee (see Approximation Algorithms). The "best single item" clause is what rescues the case where one heavy item is the whole answer.

$O(nW)$ is pseudo-polynomial: it is polynomial in the numeric value $W$, not in the number of bits needed to write $W$. Writing $W$ takes ${\log }_{2}W$ bits, so $W=2^{(\text{input size})}$ — the runtime is exponential in the input length. If we let $W$ (and weights) grow like $2^{40}$, the table has $\sim n\cdot 2^{40}$ cells and DP is intractable. 0/1 knapsack is in fact NP-hard; no known algorithm is polynomial in the bit-length of the input. So $O(nW)$ is a genuine, useful bound only when $W$ is small.

Definition of the sliver. Let $\delta$ be an arbitrarily small positive weight increment, i.e. we consider the limit $\delta \to 0^{+}$, and we always remove exactly the same amount $\delta$ that we add, so the swap is weight-preserving by construction. Fractional exchange: given an optimal solution missing some of the densest available item $d$, take a sliver of mass $\delta$ of $d$ and remove an equal mass $\delta$ of a lower-density item. Total weight is unchanged (we added $\delta$ and removed $\delta$), and value strictly rises (higher density in, lower density out) — a contradiction unless the optimum already used all of $d$ it could. The illegal line in 0/1: "take a sliver of mass $\delta$." In 0/1 the only allowed swap is a whole item, so $\delta$ can no longer shrink toward 0 — it jumps to a full weight $w_d$. That whole swap changes total weight and may violate $\sum w_i\le W$ — the exchange is not guaranteed feasible. Consequence: with no feasible weight-preserving exchange, there is no proof that a greedy choice is safe, so greedy-optimality collapses and we fall back to Dynamic Programming.

$W=50$. Items listed P, Q, R, S (listing order also fixes ties, per the page-wide rule):

• P: $w=10$, $v=60$ ($\rho =6.0$)
• Q: $w=20$, $v=100$ ($\rho =5.0$)
• R: $w=30$, $v=120$ ($\rho =4.0$)
• S: $w=50$, $v=200$ ($\rho =4.0$)

Note R and S tie at $\rho =4.0$; the tie-breaking rule considers R before S (R is listed first). (a) Density-greedy order $P\succ Q\succ R\succ S$: take P ($r=40$), take Q ($r=20$), R needs 30 skip, S needs 50 skip → set $\{P,Q\}$, value $160$. (b) Value-greedy (sort by value: S$200\succ$ R$120\succ$ Q$100\succ$ P$60$): take S ($w=50$, $r=0$) → nothing else fits → set $\{S\}$, value $200$. True optimum: enumerate feasible sets ≤ 50. Candidates: $\{S\}=200$, $\{Q,R\}=220$ (wt 50), $\{P,Q\}=160$, $\{P,R\}=180$ (wt 40). Best is $\{Q,R\}=220$. So density-greedy → $160$ (set $\{P,Q\}$), value-greedy → $200$ (set $\{S\}$) — different wrong sets — and the optimum $220$ is set $\{Q,R\}$, chosen by neither heuristic. This is the sharpest form of the parent's lesson: no single sort key finds the optimum.

Greedy (by any key) can strand capacity or hog it; the fix is DP with $K(i,c)=\max (K(i-1,c),v_i+K(i-1,c-w_i))$, giving the true optimum $220$ on the parent instance and correctly handling every instance you built here.