## Recursion, Memoization, and Dynamic Programming

The knapsack problem is posed as follows: A thief robbing a store
finds *n* items; the *i*th item is worth *v_i* dollars
and weights *w_i* points, where the cost and weight are
integers. He wants to take as valuable a load as possible, but he can
carry at most *W* pounds in his knapsack for some integer
*W*. What items should he take? [Formulation from *Introduction
to Algorithms*, by Cormen, Leiserson, and Rivest.]
Obviously this problem is very closely related to the our robot
world. Your job is to write first a naive recursive solution to the
problem, and then to use dynamic programming or memoization to produce
an efficient solution.

Here is the solution for this assignment: hw3Solution.ml