0-1 Knapsack example

The 0-1 Knapsack problem

You are given a set of n items to select from.
The items have weights w₁, w₂, …, w_n and values v₁, v₂, …, v_n.
You have a container with maximum weight capacity C.
Your goal is to select a subset of items with maximum value whose combined weight does not exceed the capacity of your container.

An exponentially large search space

The search space is the space of all possible subsets of the list {1,2,…,n}
There are 2ⁿ possible subsets to search.
Fortunately, there is a lot of redundancy in the search space.
For example, whether or not you decide to put item n in your container, you will have to consider all possible subsets of the list {1,2,…,n-1}

The optimal subset property

The optimal subset property says that any subset of an optimal solution is also optimal.

For example, suppose that {i₁ , i₂, …, i_k} is the list of indices of the items in an optimal subset with total value V. The sublist {i₁ , i₂, …, i_k-1} has total value V - v_{i_k} and will fit in a container with capacity C - w_{i_k}. The optimal subset property says that no other subset of the original set of items excluding item i_k that fits in a container with capacity C - w_{i_k} has value greater than V - v_{i_k}.

The proof is a simple proof by contradiction. If we were able to find a better subset, we could simply replace items i₁ , i₂, …, i_k-1 in the original solution with that subset to acheive a higher total value than the original solution had without exceeding the capacity of the container. This contradicts the claim that original solution is optimal.

Recursive solution

To construct an optimal subset we have to make a sequence of choices about the items in the list {1,2,…,n}.
For each item we have to examine two options: take the item or leave the item.
If we take an item we get to add its value to the total, but we also have to reduce the capacity of our container by the weight of the item we added.
We process the list in reverse order using a last-rest recursion.
The base case in the recursion comes when there are no more items left to select from. That case has a value of 0.

Pseudocode for the recursion

Suppose V[1..n] is an array of values and W[1..n] is an array of weights.

The function maxValue(k,c) computes the maximum value you can carry out in a knapsack with capacity c if you only get to select from items 1..k.

maxValue(k,c)
  if k == 0 return 0
  max = maxValue(k-1,c)
  if W[k] <= c and maxValue(k-1,c-W[k])+V[k] > max
    max = maxValue(k-1,c-W[k])+V[k]
  return max

The basic idea in the recursion is that for each item k in the list of possible items we have to decide whether or not to pack that item. The recursive code looks at both options, don't take the item and do take the item, and determines which of those two options produces the greater value. If you do decide to take the item, you first have to determine whether or not it will fit in your container.

Memoized version

Suppose V[1..n] is an array of values and W[1..n] is an array of weights.

The function maxValue(k,c) computes the maximum value you can carry out in a knapsack with capacity c if you only get to select from items 1..k.

The two dimensional array M[0..n,0..C] stores the maximum values as we find them. At start, all of the entries of this array are initialized to 0.

maxValue(k,c)
  if M[k,c] > 0 return M[k,c]
  if k == 0 return 0
  max = maxValue(k-1,c)
  if W[k] <= c and maxValue(k-1,c-W[k])+V[k] > max
    max = maxValue(k-1,c-W[k])+V[k]
  M[k,c] = max
  return max

Dynamic programming version

The dynamic programming version is a straightforward translation from the memoized version.

maxValue(cap)
  Let M[0..n,0..cap] be a new array
  for c = 0 to cap
    M[0,c] = 0
  for row = 1 to n
    for c = 0 to cap
      M[row,c] = M[row-1,c]
      if W[row] <= c and M[row-1,c-W[row]] + V[row] > M[row,c]
        M[row,c] = M[row-1,c-W[row]] + V[row]
  return M[n,cap]

There is just one thing we need to be careful about when setting up this code. We need to make sure that at any point where we are using a value from the table we have already filled in that value.

The algorithm handles this problem by filling row 0 of the table first with base cases, and then working down the rows of the table. The code only ever uses values that come from earlier rows, so we are safe.

A final problem

The dynamic programming solution can tell us the maximum value that we can carry out, but it can not tell us directly which set of items to put in our subset. The fix for this problem is relatively straightforward. We introduce a second two dimensional array T[0..n,0..C] that stores decisions about whether or not take items. If we are considering whether or not to put item k into a container with maximum capacity c, we store our decision in T[k,c].

maxValue(cap)
  Let M[0..n,0..cap] be a new array
  Let T[0..n,0..cap] be a new array
  for c = 0 to cap
    M[0,c] = 0
    T[0,c] = False
  for row = 1 to n
    for c = 0 to cap
      M[row,c] = M[row-1,c]
      T[row,c] = False
      if W[row] <= c and M[row-1,c-W[row]] + V[row] > M[row,c]
        M[row,c] = M[row-1,c-W[row]] + V[row]
        T[row,c] = True
  return M[n,cap]

We then use the values stored in the second table to construct and print the optimal solution:

printOptimal(k,c)
  if c > 0 and k > 0
    if T[k,c] == True
      printOptimal(k-1,c-W[k])
      print k + " : " + V[k]
    else
      printOptimal(k-1,c)

To print the list of items in the optimal solution we call printOptimal(n,C).