Dynamic Programming21 sections · 916 units
Open in Course

Book Shop - Problem Statement

Knapsack in disguise

You're in a book shop with nn books. Each book has a price and a number of pages. You have a budget of xx. Buy books to get the highest total pages.

Sound familiar? This is 0/1 Knapsack wearing a disguise. Budget=capacityBudget = capacity, price=weightprice = weight, pages=valuepages = value. Before reading on, try to map this problem to the knapsack framework you already know. Read the problem statement carefully, noting the constraints.