Recursion, Memoization, and Dynamic Programming
The knapsack problem is posed as follows: A thief robbing a store
finds n items; the ith 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