Reading

These notes.

Homework

Homework

0/1 Knapsack

The 0/1 Knapsack Problem is a classic problem in computer science. It's called "0/1" because each item is either all in, or all out. There is no possibility to put some portion of the item in the knapsack.

randknap.cpp produces random knapsack problems.

0/1 Knapsack: Greed is bad

A first attempt at an efficient 0/1 Knapsack algorithm is, of course, a greedy approach. That means we need to pose the problem as a series of "actions", or "choices" to make. For 0/1 Knapsack, this is easy. We look at the last item in our list and decide for it to either "put in knapsack", or "throw away". We then update by removing it from the list of available objects and, if the choice was "put in knapsack", reduce the capacity of the knapsack by the object's weight.

We looked at several greedy choices and found that none worked, i.e. none always produced optimal solutions.

0/1 Knapsack: a simple recursive example

So, we're going to have to try something other than a greedy algorithm. As with the longest common subsequence problem, we're going to start by considering an easier problem than the true 0/1 knapsack. Instead of asking for which objects go into the knapsack in order to achieve the maximum value, we will simply try first to determine what the maximum achievable value is. If we can solve that efficiently, maybe we can augment it to solve the real 0/1 Knapsack problem. We'll call this problem "0/1 Knapsack Value".

We get a simple recursive algorithm for 0/1 Knapsack Value by considering the same actions available to our failed greedy algorithms, but instead of picking one action and never going back, we simply try both actions and see which gives the better result. In other words, we proceed by examining the last item from the list and recursively trying out both adding it to the knapsack and not adding it to the knapsack. Whichever gives a greater total value ... that's what we go with.

int maxval(vector<Obj> &V, int n, int cap)
{
  if (n == 0) return 0;
  int v0 = maxval(V,n-1,cap);
  int rem = cap - V[n-1].weight;
  int v1 = rem < 0 ? -1 : V[n-1].value + maxval(V,n-1,rem);
  return max(v0,v1);
}
      

knap.cpp

0/1 Knapsack: You've got to memoize

The above algorithm is calling out to be memoized. We discussed how to do this in class.

knapmemo.cpp

Augmenting to recover the 0/1 Knapsack solution

Now we have a better algorithm for solving 0/1 Knapsack. Well ... a better algorithm for 0/1 Knapsack Value. We still haven't solved the original 0/1 Knapsack problem. To do that, we need to determin which weights to put in the knapsack in order to achieve that maximum value. As with the Longest Common Subsequence problem, the idea is to return to our greedy algorithm. We can now run the original greedy algorithm, but use the table from the memoized version to make the correct greedy decision at each step. If the remaining capacity in the knapsack is $C'$ and there are $n'$ objects left unconsidered, here's what we do. If the rightmost unconsidered item is $(w,v)$, we look at $T[n'-1][C'- w]$ and $T[n'-1][C']$. Here's the rule: If $T[n'-1][C'- w] + v \gt T[n'-1][C']$, the item goes in the knapsack; otherwise, the item is thrown away.

So do we have an efficient solution to 0/1 Knapsack?

Even with many items, our memoized solution is quite fast. However, when the weights and capacity get large, this algorithm is slow even with relatively few weights. In fact, we basically have an $O(nC)$ algorithm, where $n$ is the number of items and $C$ is the capacity. So is this "efficient", or not? In the coming lessons, we'll have more to say about this!