0-1 Knapsack#
\( \begin{aligned} n && \text{items} \\ w(j) && \text{weight of item } j \\ v(j) && \text{value of item } j \\ \end {aligned} \)
select a subset of items to maximize the total value, within a weight limit \(W\)
\(j\) |
\(w\) |
\(v\) |
|---|---|---|
\(1\) |
\(6\) |
\(30\) |
\(2\) |
\(3\) |
\(16\) |
\(3\) |
\(4\) |
\(16\) |
\(4\) |
\(2\) |
\(8\) |
EXAMPLE
\(\max_{W \le 7} V\)
Heuristic: greedy, select the item with the most value
\(I = \{ 1 \}, w = 1, v = 30\)
Optimal
\(I = \{ 2, 3 \}, w = 0, v = 32\)
since greedy doesn’t work, we have to search the entire space: \(O(2^n)\)
A different approach
maximize the value \(v(j)\) over a given subset of items \(1\) through \(j\)
first solve \(v(0)\)
then solve \(v(1)\) which relies on \(v(0)\)
so on
\(O(n)\)
maximize the value of all items obtainable from a particular weight limit \(v(w)\)
\(O(w)\)
Running this approach over subsets of items first, we find the following
\( \begin{aligned} v(1) = 30, && I &= \{ 1 \} \\ v(2) = 30, && I &= \{ 1 \} \\ v(3) = 32, && I &= \{ 2, 3 \} \\ v(4) = 32, && I &= \{ 2, 3 \} \\ \end {aligned} \)
Since the item set of \(v(2)\) is not a prefix of the item set of \(v(3)\), the optimal substructure property does not hold. We cannot use the optimal problem for \(v(2)\) in the optimal problem for \(v(3)\). This would also occur for optimizing over weights
Expand the search space into higher dimensionality
\(j\) |
\(w\) |
\(v\) |
|---|---|---|
\(1\) |
\(6\) |
\(30\) |
\(2\) |
\(3\) |
\(16\) |
\(3\) |
\(4\) |
\(16\) |
\(4\) |
\(2\) |
\(8\) |
\( \text{weight} \overset{\text{item}}{ \begin{array}{c|c|c|c|c|c} & 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 0 & 0 & 0 & 0 \\ \hline 2 & 0 & 0 & 0 & 0 & 8 \\ \hline 3 & 0 & 0 & 16 & 16 & 16 \\ \hline 4 & 0 & 0 & 16 & 16 & 16 \\ \hline 5 & 0 & 0 & 16 & 16 & 24 \\ \hline 6 & 0 & 30 & 30 & 30 & 30 \\ \hline 7 & 0 & 30 & 30 & 32 & 32 \\ \end {array}} \)