背包问题

In the backpack problem, we have a backpack that can carry $N$ lbs. Furthermore, we have some items, each with a value and a weight. We want to find the biggest value we can carry in the backpack without exceeding the weight capacity.

A sample set of values/weights is in the table below:

To solve this problem, we use dynamic programming. The particular technique we will use is memoization (not to be confused with memoRization), which is keeping a table of already computed values so we don't have to compute something many times.

Let's say we want to solve the problem with $n$ items of values and weights $(v_i,w_i)$, and our backpack holds $N$ lbs. The columns will be numbered $1,2,\dots,N$, and in the $k$th row of that column we will solve the backpack problem using just the first $k$ items of values and weights $(v_i,w_i)$.

We should also add a dummy column before all the others numbered $0$ and a dummy row before all the others filled with just zeros since no items implies total maximum value is $0$.

Now we iteratively compute the values in the $k$th row. The $0$th column will always be $0$ since the backpack can hold $0$ lbs. In column $C$, we enter the maximum of the following two quantities: the entry in column $C$, row $k-1$ or $v_k$ plus the entry in column $C-w_i$, row $k-1$.

This process essentially chooses at each step whether it would be optimal to carry that item or not.