DP Table — 0/1 Knapsack
Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi) if wi≤w, else dp[i-1][w].
Time: O(nW), Space: O(nW) — pseudo-polynomial. Backtrack via choosing item i if dp[i][w] ≠ dp[i-1][w].
Scaling Comparison: Brute Force vs DP
Brute force: O(2^n) — exponential. DP: O(nW) — polynomial in n and W (pseudo-polynomial since W can be exponential in bits).
Value Density Analysis
Greedy by value/weight ratio is optimal for fractional knapsack but NOT 0/1 knapsack. DP finds true optimum. Bars show v/w ratio for each item; selected items highlighted.