Book Shop has books with prices and page counts . You have budget . 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 = max pages from books with budget . Transition: if . 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.