Book shop question from cses

#1

https://cses.fi/problemset/task/1158/

why this code is not correct?

#2

What logic you are using while using dp can you please elaborate?

#3

I just want to know the logic you are using.

#4

I had just made a DP array for storing pages of prizes from 0 to x at the end I print the pages I can buy with price x…

#5

Don’t you think if you are storing pages of prizes from 0 to x you will need a dp array of row and column.
Cause then only dp[i][x] = maximum number of pages we can get for price at most x, only buying among the first i books.

#6

i don’t understand what you want to tell but i think my algo will work if the same book has infinite times…

#7

See you have N number of Books as
B1 B2 B3 … Bn
And every Bi has Ci cost of the book and Pi pages of the book, right?
Now you have to maximise Number of pages with cost of X. As mentioned in the question.
It means it’s a clear concept of 0-1 knapsack problem.
Now I’ll help you visualise dp solution.
You have N books with X currency with you. You have 2 choices with it, and they are

  • choose nth book , you will still have a choice to choose any book from remaining n-1 books but you have to lose some value I.e., price of that nth book.
    I.e., (n-1, X- Cn, Initial pages + Pn)

  • don’t choose nth book , choose any book from remaining n-1 book and keep your currency as it.
    (n-1, X, Initial pages)

Therefore , recurrence relation is
Dp[i][x] = max(dp[i-1][x], Pi + dp[i-1][x-Ci])

#8


this is yet not working…

#9

Hey @ankit_verma I have debugged your code


Your conditions were wrong and for loop of I it should have been started from I=1 ,which I have corrected. I would request you that if this resolves your doubt. Please mark your doubt as resolved.

#10

your code shows wrong output

#11

Yes there was a small mistake, and now it’s correct https://ide.codingblocks.com/s/365133

#12

Please mark your doubt as resolved if it solves your query.

#13

from where i can clicked to resolved doubt option

#14

Lemme mark it as resolved, please rate your experience with it.

#15

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.