- given a knapsack with capacity $W$, $n$ items with weights $w_1, ..., w_n$ and values $v_1,...,v_n$ - return the most valuable combination of items that can fit in the knapsack - you can only use each unique item once - the 2D DP algorithm that solves this: - define $f(i, u)$ as the max value achievable with knapsack capacity $u$ and items $1,...,i$ - $f(i, u) = max(f(i - 1, u), f(i - 1, u - w_i) + v_i)$ - only 2 possible choices: - you use the item in this combination, or you don't - runtime is $O(nW)$ - in DP memo, there is a 2D matrix - $n + 1$ rows (0-n items left) - $W + 1$ columns ($0-W$ items left) https://people.eecs.berkeley.edu/~vazirani/algorithms/chap6.pdf