When greedy works vs when it fails: knapsack

The same problem, two versions

A thief finds $n$ items; item $i$ has value $v_i$ and weight $w_i$, and the knapsack holds weight $W$. The two versions diverge on a single rule:

- Fractional knapsack — you may take *any fraction* of an item (think gold dust). Greedy works. - 0/1 knapsack — each item is taken whole or left behind (think gold bars). Greedy fails; you need DP.

Fractional knapsack: greedy by value density

Compute each item's value density $v_i / w_i$, sort descending, and greedily fill the knapsack with the highest-density items, taking a fraction of the last one if it does not fit. This is $O(n \lg n)$ (the sort dominates).

Why it is safe (exchange argument): if an optimal solution skipped some of a higher-density item to include a lower-density one, you could swap a sliver of the low-density portion for the high-density portion, raising the value without changing the weight — contradicting optimality. Because fractions are allowed, the greedy choice never wastes capacity.

0/1 knapsack: the greedy counterexample

Take $W = 50$ and three items (CLRS Fig. 15.2):

$$\begin{array}{c|ccc} & v_i & w_i & v_i/w_i\\\hline 1 & \$60 & 10 & 6\\ 2 & \$100 & 20 & 5\\ 3 & \$120 & 30 & 4 \end{array}$$

Greedy (by density) takes item 1 ($\$60$, density 6), then item 2 ($\$100$, density 5) for weight $30$ and value $\$160$; item 3 no longer fits. Optimal skips the densest item: items 2 + 3 weigh exactly 50 and are worth $\$220$. Greedy left 20 pounds of capacity "wasted" on the lower-value item 1.

The fractional version of the *same* instance reaches $\$240$: take all of items 1 and 2 ($30$ lb, $\$160$) plus $\tfrac{20}{30}$ of item 3 ($\$80$). Allowing fractions removes the wasted-capacity trap.

Why 0/1 needs DP

In the 0/1 problem, choosing one item reduces the capacity available to all others — the subproblems share the weight constraint, so the greedy choice can foreclose a better combination. That shared constraint is exactly the overlapping-subproblem structure DP exploits. The DP is

$$dp[i][w] = \max\bigl(dp[i-1][w],\; dp[i-1][w - w_i] + v_i\bigr)$$

in $O(nW)$ time. (That $O(nW)$ is pseudo-polynomial — polynomial in the numeric value of $W$, but exponential in the number of bits used to write $W$. 0/1 knapsack is NP-complete.)