How to solve problems on this type of DP (choose items, but without repetitions)?

Question

C++ / C#

There is a task: https://cses.fi/problemset/task/1158
I understand how to do when you can repeat items, but when you can’t, I don’t understand how.
I will be grateful for the answer.

Answer 1

This is a classic knapsack problem.
We can compose the following DP: F(c, k) - the maximum number of pages that can be typed from the first k books with a total cost of exactly c.
Base: F(0,0) = 0, F(0,*) = F(*,0) = -infinity.
Recalculation:

F(c, k) = max(F(c-cost[k], k-1) + pages[k], F(c,k-1))

This DP is given in Wikipedia, for example. The answer is the maximum over all c F(c,k).
There is one trick in the implementation - you can get by with only one row of this matrix if you do not need to restore the entire set of books in the answer, but only its best value (you just need to swap the parameters - a row the size of the maximum price). This will reduce memory consumption by a factor of K if you have K books. This does not affect the speed of the solution.
First, implement all dp on the matrix from bottom to top, in two cycles.
Now, if you drive the inner loop from the end to the beginning, then you will not need to look at the values ​​​​already rewritten at the current iteration of the outer loop, and you can score on the second parameter of the DP and simply rewrite the line in place.