0-1 Knapsack Problem

Problem:
A thief robbing a store finds \(n\) items; the \(i\)th item is worth \(v_i\) dollars and weights \(w_i\) pounds, where \(v_i\) and \(w_i\) are integers. He 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?

Analysis:
There are two versions of this problem: fractional knapsack problem and 0-1 knapsack problem.

1. Fractional knapsack problem: the items can be broken into smaller pieces, and the thief can take fractions of items.
2. 0-1 knapsack problem: the items may not be broken into smaller pieces, and the thief must decide whether to take an item or leave it (binary choices).

For fractional knapsack problem, greedy algorithm exists and the problem can be solved in \(O(n\log n)\) time based on sorting. And a better approach may take \(O(n)\) time for the worst case based on linear-time SELECT algorithm.

For 0-1 knapsack problem, no greedy algorithm exists and we need turn to dynamic programming approach. The algorithm will take \(O(nW)\) time.

Solution:
Define \(c[i,w]\) to be the optimal value for items \(1,2,...,i\) and maximum weight \(w\). There are following recursive relations:
\[c[i,w]=\begin{cases}0, & i=0\text{ or }w=0\\c[i-1,w], & w_i\gt w\\ \max\{v_i+c[i-1,w-w_i], c[i-1,w]\}, & i>0 \text{ and }w_i \le w\end{cases}\] We can have the pseudocode:

DP_01_Knapsack(value, weight, W)
   assert value.length = weight.length
   n ← value.length
   for w ← 0 to W:
      c[0,w] ← 0
   for i ← 1 to n:
      c[i,0] ← 0
      for w ← 1 to W:
         c[i,w] ← c[i-1,w]
         if weight[i] ≤ w and value[i]+c[i-1,w-weight[i]] > c[i-1,w]:
            c[i-1,w] ← value[i]+c[i-1,w-weight[i]]

The set of items to take can be deduced from the table, starting at \(c[n,W]\) and tracing backwards where the optimal values came from. If \(c[i,w]=c[i-1,w]\), then item \(i\) is not part of the solution, and we are continue tracing with \(c[i-1,w]\). Otherwise item \(i\) is part of the solution, and we continue tracing with \(c[i-1,w-w_i]\).

References:

Dynamic Programming Solution to the 0-1 Knapsack Problem