Book Shop - Implementation

Initialize $dp[0..x]$ = 0. For each book (price, pages), update $dp[j]$ = max($dp[j]$, $dp[j-price]$ + pages) for $j$ from $x$ down to price. The reverse iteration is key. If you go forward, you might count the same book multiple times (that's unbounded knapsack, not 0/1). Answer is $dp[x]$. Time: $O(n \times x)$, Space: $O(x)$. The code directly follows the recurrence relation. Trace through a small example by hand to see how each value is computed.

Time complexity: $O(n \cdot X)$.

Space complexity: $O(X)$.