0-1 knapsack problem

Problem Statement

The 0-1 knapsack problem is the following. A thief robbing a store finds n items. The $i$ th item is worth $v_i$ dollars and weighs $w_i$ pounds, where $v_i$ and $w_i$ are integers. The thief wants to take as valuable a load as possible, but he can carry at most $W$ pounds in his knapsack, for some integer $W$. Which items should he take? We call this the 0-1 knapsack problem because for each item, the thief must either take it or leave it behind; he cannot take a fractional amount of an item or take an item more than once. [1]

Now let’s take an exercise from our CLRS book [1].

Exercise 16.2-2 

Give a dynamic programming solution to the 0-1 knapsack problem that runs in $O(n \cdot W)$ time, where $n$ is the number of items and $W$ is the maximum weight of items that the thief can put in his knapsack. [1]

0-1 knapsack - Definition 

Let $n$ be the number of items, $W$ be the capacity of the knapsack. Let $i$ be the current item being considered, $v_i$ and $w_i$ be it’s value and weight respectively. Let $k[1 \ldots n][1 \ldots w]$ be a table holding optimal solutions to subproblems. Let $j$ be the size of the subproblem. We can write our recurrence to the 0-1 knapsack problem as follows:

$$k[i][j] =
\begin{cases}
max(v_i + k[i - 1][j - w_i], \;k[i-1][j]),  & \text{if $w_i \le j$} \\[2ex]
k[i-1][j], & \text{otherwise.}
\end{cases}$$

0-1 knapsack - Approach

If the $w_i \le j$, then we can put this item and take an optimal worth that we can achieve with the remaining capacity without including this item again. We also can exclude the item in the first place, and calculate the maximum worth that we can obtain with the given capacity. The maximum value of those two would be the optimal worth which we can achieve. Otherwise, we just calculate the maximal worth that we can obtain without including the $i^{th}$ item, since the $i^{th}$ item is heavier than the capacity $j$. Here’s the algorithm for finding maximum worth.

**Input:** value and weight arrays $v$, $w$ and $c-$ the capacity of the knapsack  
**Output:** Table $k$ which contains the maximum attainable worth  
$0-1KNAPSACK(v, w, c)$              
$\phantom{{}++{}}$ $n \gets v.length$  
$\phantom{{}++{}}$ let $k[1 \ldots n + 1][1 \ldots c + 1]$ be a new table  
$\phantom{{}++{}}$ `for` $i = 1$ to $n + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[i][1] \gets 0$  
$\phantom{{}++{}}$ `for` $j = 2$ to $c + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[1][j] \gets 0$  
$\phantom{{}++{}}$ `for` $i = 2$ to $n + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$ `for` $j = 2$ to $c + 1$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ `if` $w[i - 1] \le j$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[i][j] \gets max(v[i - 1] + k[i - 1][j - w[i - 1]], \;k[i - 1][j])$  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ `else`  
$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$$\phantom{{}++{}}$ $k[i][j] \gets k[i - 1][j]$  
$\phantom{{}++{}}$ return $k$

 

Figure 1 shows the table $k$ computed by the procedure $0-1KNAPSACK$ on the two input arrays $v = $[ 20, 5, 10, 40, 15, 25 ] and $w = $[ 1, 2, 3, 8, 7, 4 ] for a knapsack with capacity $c = 10$. 

$$\begin{array}{|c|c|c|}  \hline
 & \text{1}  & \text{2} & \text{3} & \text{4} & \text{5} & \text{6}& \text{7}& \text{8} & \text{9} & \text{10} & \text{11} \\ \hline
\text{1} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
\text{2} & 0 & 20 & 20 & 20 & 20 & 20 & 20 & 20 & 20 & 20 & 20 \\ \hline
\text{3} & 0 & 20 & 20 & 25 & 25 & 25 & 25 & 25 & 25 & 25 & 25 \\ \hline
\text{4} & 0 & 20 & 20 & 25 & 30 & 30 & 35 & 35 & 35 & 35 & 35 \\ \hline
\text{5} & 0 & 20 & 20 & 25 & 30 & 30 & 35 & 35 & 40 & 60 & 60 \\ \hline
\text{6} & 0 & 20 & 20 & 25 & 30 & 30 & 35 & 35 & 40 & 60 & 60 \\ \hline
\text{7} & 0 & 20 & 20 & 25 & 30 & 45 & 45 & 50 & 55 & 60 & 60 \\ \hline
\end{array}$$

Finding items in our knapsack

Now, we need to find the items that should be there in the knapsack from the table computed at step one. Here’s the algorithm for finding items in an optimal solution.

**Input:** Table $k$ computed at previous step and $w-$ the weight array  
**Output:** Items that should be in the knapsack in order to get the maximal worth  
$FIND-ITEMS(k, w)$  
$\phantom{{}++{}}$ $j \gets k[1].length$  
$\phantom{{}++{}}$ $n \gets k.length$  
$\phantom{{}++{}}$ `for` $i = n$ down to $2$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ `if` $k[i - 1][j] \lt k[i][j]$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ print $i - 1$  
$\phantom{{}++{}}$ $\phantom{{}++{}}$ $\phantom{{}++{}}$ $j \gets j - w[i - 1]$ 

We start from the bottom right position of the table $k$, tracing back all the way up until we reach the top row. At each step, we check whether the current cell is larger than the cell which lies above it. If so, we take the current item, deduct it's weight from the remaining capacity and move on to the next step.
Our approach of finding items in an optimal solution involves, $O(n)$ time and $O(1)$ space complexity.

Sample Implementation

Here’s the sample implementation of algorithms described above along with a driver program.

Analysis

Our approach of finding the most valuable load for a given knapsack capacity takes $O(\mathrm{n}^2)$ space and time complexity.

References

[1] https://www.amazon.com/Introduction-Algorithms-3rd-MIT-Press/dp/0262033844