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}{cccc}& v_i& w_i& v_i/w_i\\ 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 (dp[i-1][w],dp[i-1][w-w_i]+v_i)$$

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.)