Question

2. In the BACKPACK problem, you are given a collection of books of different costs and are tasked with storing as expensive a subset of books as possible so you can sell them at the bookstore in only one trip. Unfortunately, the books are very heavy, and you are limited in how much total weight you can carry. Formally, you are given two arrays C[1.. n] and w[1..n] of positive integers where C[i] is the cost of book i in dollars and w[i] is the weight of book i in pounds. You are also given a positive integer M which is the maximum load you can carry in pounds. Your goal is to compute the maximum total cost of any subset of books you can carry from books 1 through n. (a) For any integers i and m with 0<i< n and 0 < m < M, let MaxCost(i, m) be the maximum cost of any subset of books 1 through i that have a total weight of at most m. Give a recurrence definition for MaxCost(i, m). Don't forget the base cases! (b) Design and analyze a dynamic programming algorithm for solving the BACKPACK problem based on your recurrence from part (a). You should get a running time of O(NM).