Knapsack Problem:
================

You're given a knapsack with capacity C (a nonnegative integer) and a
collection of items, each of which has a weight w_i and a value v_i.
So formally, your input is a list of nonnegative integer weights
w_1,...,w_n, a list of nonnegative integer values v_1,...,v_n, and a
nonnegative integer capacity C. You want to fill up your knapsack
with items so that you get the maximum possible value; putting in
more than one object of the same type is allowed. So formally, your
output should be a list of indices i_1,...,i_k (for some k) such that
w_{i_1} + ... + w_{i_k} <= C and v_{i_1} + ... + v_{i_k} is maximum.

For example, if C = 11, w_1 = 3, w_2 = 4, w_3 = 5, w_4 = 7, v_1 = 2,
v_2 = 3, v_3 = 4, v_4 = 5, then the best solution is i_1 = 3, i_2 = 3
for total value 8.

- How do we solve a problem like this using dynamic programming?
  The first step is to try to understand the structure of the problem.
In other words, *if* we had a solution to the problem, what could we
say about this solution in terms of solutions to subproblems? So,
imagine that we have a solution i_1,...,i_k. Now, if we look at the
first k-1 items in this solution, i_1,...,i_{k-1}, do we know that
they form a solution to some subproblem of the original problem? 
In this case, yes: if i_1,...,i_k gives us the maximum possible value
for capacity C, then i_1,...,i_{k-1} must give us the maximum possible 
value for capacity C - w_{i_k}.

- Now that we have this idea, we can define an array as follows: What
  are we trying to maximize? The total value of the items selected.
So we'll keep track of the maximum value possible for certain
subproblems. How do we index this array? Well, we've already thought 
of how solutions break up into subsolutions, so it makes sense to use 
the following definition:

      V[j] = maximum value attainable for maximum capacity j.

Obviously, the answer to the problem is the value V[C]. Moreover, we
can write the following recurrence for V[j], based on the structure
of the problem mentioned above:

      V[0] = 0
      V[j] = max { V[j-1],     max     { v_i + V[j-w_i] } }   for j > 0
                           i : w_i <= j

- Now, to compute the values according to the recurrence, the most
  natural thing to do would be to write a recursive function that
computes V[C] by calling itself to get the values for smaller indices. 
Unfortunately, this will be very inefficient: it turns out that we 
will be recomputing some of the same values many times, which will 
cause a significant increase in the running time.

- Instead, since we know that we will need potentially all values of V
  for smaller indices to compute V[C], we will simply compute the
values bottom-up (starting at j = 0 and letting j increase). From
the recurrence, we can directly write an algorithm that computes the
values of V[j] according to this idea. Let us write the algorithm "in
C++", assuming that `C' is an int containing the maximum capacity,
that arrays w[n] and v[n] have already been defined (storing values
from index 0 to n-1 in the C++ convention), and that an array V[C+1]
has already been declared.

      V[0] = 0;
      for ( int j = 1; j <= C; j++ ) {
         V[j] = V[j-1];
         for ( int i = 0; i < n; i++ ) {
             if ( w[i] <= j && v[i] + V[j-w[i]] > V[j] ) {
                V[j] = v[i] + V[j-w[i]];
             } //end if
         } //end for
      } //end for

- Running time? Obviously O(n*C). Is this polynomial-time? If C
  happens to be bounded by a polynomial in n, then yes.

- What about the actual solution? At the end of this algorith, we only
  know the *value* of the solution, but not the actual list of items
that make it up. There is an easy way to modify this so that we get
the actual list, by keeping track of a second array L[j] whose value
is the index of the *last* item put in to get the value of V[j].

More precisely, we can add the following few lines to the algorithm
to compute the values of L[j]:

       V[0] = 0;
       L[0] = -1;
       for ( int j = 1; j <= C; j++ ) {
           V[j] = V[j-1];
           L[j] = L[j-1];
           for ( int i = 0; i < n; i++ ) {
               if ( w[i] <= j && v[i] + V[j-w[i]] > V[j] ) {
                  V[j] = v[i] + V[j-w[i]];
                  L[j] = i;
               } //end if
           } //end for
       } //end for

- At the end, how do we get the actual answer from this? Simple: start
  at L[C], which is the index of the last item to put in, in order to
get the maximum value of V[C]. We know that if we put in an item
number L[C], we reduce the capacity by w[L[C]], so look next at
L[C-w[L[C]]] for the next item, and so on...

More precisely, we can output the list of item numbers to put in with
this simple loop:

      for ( int j = C; L[j] >= 0; j -= w[L[j]] ) {
          cout << L[j];
      } //end for

- For the example with C = 11, w_1 = 3, w_2 = 4, w_3 = 5, w_4 = 7, and
  v_1 = 2, v_2 = 3, v_3 = 4, v_4 = 5, the algorithm will compute the
following values:

        j | V | L     For example, the value V[5] is computed like this:
      -------------   
        0 | 0 | 0     V[5] = max { V[4], 2 + V[2], 3 + V[1], 4 + V[0] }
        1 | 0 | 0          = max { 3, 2, 3, 4 } = 4
        2 | 0 | 0     
        3 | 2 | 1     and
        4 | 3 | 2     
        5 | 4 | 3     L[5] = 3 (the index of the last item put in to
        6 | 4 | 3               get value V[5] = 4).
        7 | 5 | 1     
        8 | 6 | 1     The final answer is (3, 3), as we would expect,
        9 | 7 | 2     and as can easily be checked by tracing the output
       10 | 8 | 3     routine given above with the values in the table.
       11 | 8 | 3