Given price and number of pages of each book, What is the maximum number of pages you can buy? You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

Example:

In:
4 10
4 8 5 3  //price
5 12 8 1 //pages
Out:
13
Explaination: You can buy books 1 and 3. Their price is 4+5=9 and the number of pages is 5+8=13


This is my recursive approach :

f(i,j) is max pages, when you can afford i units of money and j is the index in vector uptill the jth book. ie 0 to jth books are considered.

f(x, 0)=max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) );


I am having difficulty making the base case, what should be the base case?

Thank you.
I am afraid that the following recurrence equation as in the question is incorrect.

f(x, 0) = max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) )




Let g(i,j) be the maximum number of pages possible when you have i units of money to spare and books 0..j available to select, where 0..j means 0, 1, ..., and j. (I use g instead of f since I am not absolutely sure of the definition of f in the question. It looks like g(i,j) should be the same as f(i,j) in the question. )

Here is the recurrence equation.

g(x, indx+1) = ( x &gt;= price[indx+1] ) ? 
              max( g(x - price[indx+1], indx) + pages[indx+1], g(x,indx) ) :
              g(x, indx)


In plain words, there are (at most) two possibilities when books 0..(indx+1) are available to select.


Book indx+1 is selected (when x &gt;= price[indx+1]). You have pages[indx+1] more pages. 

Then you are left with x - price[indx+1] units of money and books 0..indx to select.
Otherwise.

Then you are left with x units of money and books 0..indx to select.


Note that the available books on the right-hand side of the equation are always less than the available books on the left-hand side. That reduction of a larger problem to a smaller problem signifies the power of recursion.

The base case are when no books are available, i.e., g(i,0) = 0 for all i, and when there is no money to spare, i.e., g(0, j) = 0 for all j.