Reading

These notes.

Quiz questions

Review quiz problem

0/1 Knapsack

The 0/1 Knapsack Problem is a classic problem in computer science.
Problem: O/1 Knapsack
Given: capacity $C$ and $n$ items $(w_1,v_1), (w_2,v_2), \ldots, (w_n,v_n)$ with "weight" and "value"
Find: a subset of items whose total weight does not exceed the capacity $C$ and whose total value is maximized
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

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

We get a simple recursive algorithm for 0/1 Knapsack 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