2.2 Knapsack

In the knapsack problem we have n items, where each item i has an integer value vi and an integer price pi , and we also have a budget of B. The goal is to find the maximum total value of items that can be picked without exceeding the budget. In particular, out of all sets of items whose total price is at most B, we want the set of highest total value. In class, we gave a dynamic programming algorithm to solve this problem whose running time was O(nB). One issue, though, is that if the prices are large, then O(nB) may not be so good. In this problem, we want you to come up with an alternative algorithm whose running time is O(nV ), where V is the value of the optimal solution. So, this would be a better algorithm if the prices are much larger than the values. Describe in English the idea of your algorithm. Define the memo table that you will use and write the base case and recursive step needed to fill the table. Finally write the pseudo code. You dont need to provide a proof of correctness.

[Note: Your algorithm should work even if V is not known in advance, but you may want to first assume you are given V up front and then afterwards figure out how to remove that requirement.]