Review quiz problem
The 0/1 Knapsack Problem is a classic problem in computer
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
randknap.cpp produces random
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);
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.