- 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