## 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: 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