Dynamic programming: the knapsack family

Maximize value in a limited bag. One rule — fractions allowed? — decides greedy vs DP.

Fractional vs 0/1

• Fractional (take slices): greedy is OPTIMAL — densest first, top off the bag
• 0/1 (all-or-nothing): greedy BREAKS — densest item can waste capacity
• Classic: (10,60),(20,100),(30,120), bag 50 → greedy 160, optimum 220
• No greedy rule works for 0/1 → dynamic programming

The 0/1 DP: take or skip

• dp[i][w] = best value from first i items within capacity w
• Each item: max(skip = dp[i-1][w], take = value + dp[i-1][w-weight])
• Fill from no-items up; answer = dp[n][capacity]
• O(n · capacity)

Watch the table fill

Green = item taken here · grey = skipped. dp[4][7] = 9 (items 3+4). Density-greedy grabs the 5-weight item first → only 8.

Greedy has no guarantee

Greedy ~95% average but WORST case → 0 (item A=(1,2), B=(W,W), bag W: greedy 2, optimum W). Fractional 136% = a loose upper bound (relaxation gap).

Pseudo-polynomial

• O(n · capacity) is polynomial in capacity's VALUE, exponential in its BITS
• Fast for modest capacity; infeasible for huge ones → branch-and-bound / FPTAS
• 0/1 knapsack is NP-hard — the DP doesn't put it in P
• "Fast for my inputs" ≠ "polynomial-time"

Takeaway

Fractions allowed → greedy. All-or-nothing → DP. That's the whole difference. DP makes the state space explicit — but a huge state space still bites. Next: edit distance & LCS — DP on sequences (diff, spell-check, DNA).