Dynamic Programming21 sections · 916 units
Open in Course

Book Shop - Recognizing the Pattern

It's a knapsack

Let's translate: you have nn items (books). Each item has a weight (price) and value (pages). Your knapsack capacity is xx (budget). get the highest value (pages). It's the same structure as 0/1 Knapsack! Each book is either bought or not.

You can't buy fractions. The constraints (nn ≤ 1000, xx10510^5) fit the standard DP approach. Recognizing disguised problems is a key skill. Many interview questions are classics in costume.