DP: Knapsack 2

The Knapsack problem is famous. How to fill a sack with items that are of maximal value without breaking the sack?

Last class we discussed how to do this using a classic algorithm. This time we will combine dynamic programming with divide and conquer to make a truly fast version that can solve knapsack with repetitions.