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(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?

1 Like

Hint: This is classic knapsack problem with Weight of each item being the price of book and value being the number of pages.

2 Likes

Thanks! That solved the problem.!

1 Like

Seems as if you are solving dp problems these days. If you encounter some good level dp problems on your way, then you can make their list and post it on discuss so everybody can benefit. :slight_smile:

2 Likes

Sure, I will…! But for now I am just on to the basic level problems.
Here’s a list which you might find interesting : https://codeforces.com/blog/entry/67679
Codeforces have many great blogs like this on other topics as well.

I already saved that list a few days ago :stuck_out_tongue:

1 Like

Bade log… :joy: :raised_hands: