Book Shop - Walkthrough

Book Shop has $n$ books with prices $p_i$ and page counts $s_i$. You have budget $x$. get the highest total pages. This is 0/1 Knapsack: price is weight, pages are value, budget is capacity.

Each book can be bought at most once. Let $dp[i][b]$ = max pages from books $1..i$ with budget $b$. Transition: $dp[i][b] = \max(dp[i-1][b], dp[i-1][b-p_i] + s_i)$ if $b \geq p_i$. space reduction: since we only look at the previous row, we can use 1D array and iterate budget in reverse. This is the standard 0/1 Knapsack trick.