- 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 are allowed to use each item multiple times - the 1D DP algorithm that solves this: - $f(w) = \max_{\,i\,:\,w_i \leq w} f(w - w_i) + v_i$ - decision at each stage is which item to choose, for those that could possibly fit in the remaining space - runtime is $(nW)$ - there is 1D table of length $W + 1$ - but each entry can take up to $O(n)$ time to compute https://people.eecs.berkeley.edu/~vazirani/algorithms/chap6.pdf