1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This problem is known as Knapsack (en.wikipedia.org/wiki/Knapsack_problem). $\endgroup$ – Vince Jun 20 at 11:58
  • $\begingroup$ Can you edit the question to explain your recursive equation? For example, explain the meaning of $f(x,y)$? How does the equation make sense? $\endgroup$ – Apass.Jack Jun 20 at 18:16
  • $\begingroup$ @Apass.Jack Edited. Anyways This is just the modified version of the Knapsack problem. $\endgroup$ – Het Jun 20 at 18:43
  • $\begingroup$ How does the recurrence equation make sense? Please explain as detailed as possible. I suspect that your equation is wrong since I cannot understand it. $\endgroup$ – Apass.Jack Jun 20 at 19:10
  • 1
    $\begingroup$ Sure, Although I had already figured it out. Accepted your answer, will be useful to others. $\endgroup$ – Het Jul 5 at 18:15
1
$\begingroup$

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 >= 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 >= 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.

$\endgroup$
  • $\begingroup$ My corrected equation: f(x, 'indx') = max( f(x-price[indx], indx+1) + pages[indx], f(x,indx+1) ), actually f(x,0) is the answer and not the recurrence relation which I was mentioning earlier. The answer I was getting with my equation is correct but I am getting TLE, My code: ide.codingblocks.com/s/99933 $\endgroup$ – Het Jul 5 at 18:13
  • $\begingroup$ cses.fi/problemset/task/1158 $\endgroup$ – Het Jul 5 at 18:16
  • 1
    $\begingroup$ @Het Instead of recursive calls, you should compute the entries iteratively. I will use my notation. First, $g(i,0)=0$ are known. Then compute $g(i,1)$ for all $i$. Then compute $g(i,2)$ for all $i$. And so on. Finally, $g(x,n)$ is the answer. $\endgroup$ – Apass.Jack Jul 5 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.