Problem link ও উৎস
- **Original source:** CSES Problem Set — Dynamic Programming section
- **Platform:** CSES —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** 0/1 knapsack
- **Basic idea inherited from:** #13 Partition Equal Subset Sum — একই take-or-leave, কিন্তু boolean-এর বদলে value maximize; loop-direction-এর শিক্ষা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা দোকানে `n`-টা বই, প্রতিটার একটা দাম `price[i]` আর কত পাতা `pages[i]`। তোমার হাতে মোট `budget` (`x`) টাকা। প্রতিটা বই সর্বোচ্চ **একবার** কিনতে পারো (একটাই কপি)। budget-এর মধ্যে থেকে সবচেয়ে বেশি মোট পাতা (pages) কিনতে চাও — সেই সর্বোচ্চ pages বের করো। এটা ধ্রুপদী **0/1 knapsack**: price = weight, pages = value, budget = capacity।
```text
budget = 10
price = [4, 8, 5, 3]
pages = [5, 12, 8, 1]
সেরা: বই 0 (দাম 4, পাতা 5) + বই 2 (দাম 5, পাতা 8) = দাম 9 <= 10, পাতা 13
```
### Input ও output {#8-example-input-and-output}
```text
Input : budget=10, price=[4,8,5,3], pages=[5,12,8,1] -> Output: 13
Input : budget=5, price=[3,7], pages=[8,9] -> Output: 8 (শুধু বই 0 ধরে)
Input : budget=100,price=[10,20,30],pages=[60,100,120] -> Output: 280 (সব কেনা যায়)
Edge case 1: budget=0, price=[1,2], pages=[5,6] -> Output: 0 (কিছু কেনা যায় না)
Edge case 2: budget=50,price=[10,20,30],pages=[60,100,120] -> Output: 220 (subset)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো নির্দিষ্ট বাজেট নিয়ে বইমেলায় গেছ, প্রতিটা বইয়ের একটা দাম আর তোমার চোখে একটা "মূল্য" (কত পাতা/আনন্দ)। প্রতিটা বইয়ের সামনে দাঁড়িয়ে ভাবো: "এটা কিনলে বাকি টাকায় বাকি বই থেকে সর্বোচ্চ কত পাব?" বনাম "এটা না কিনলে?" — বড়টা বেছে এগোও। প্রতিটা বই একটাই কপি, তাই একবার কিনলে সেটা আর তালিকায় নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি #13 Partition Equal Subset Sum-এর take-or-leave কঙ্কাল — প্রতিটা item-এ "নাও/বাদ দাও," প্রতিটা একবার। তফাত: সেখানে শুধু boolean reachability track করতাম; এখানে প্রতিটা budget-এ অর্জনযোগ্য **max value** (pages) ধরি। আর সেই একই loop-direction শিক্ষা ফেরে: **0/1 = inner loop ডান-থেকে-বাঁ**, যাতে প্রতিটা বই একবারই কেনা হয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic প্রতিটা বইয়ে একটা সিদ্ধান্ত: **কেনো, না কেনো না।** কিনলে `pages[i]` পাও কিন্তু `price[i]` টাকা খরচ — তখন বাকি budget `w - price[i]`, এবং বইটা আর available নয় (তাই আগের item-set-এ হাত যায়)। না কিনলে value অপরিবর্তিত, budget অপরিবর্তিত। দুই বিকল্পের max-ই সেই (item, budget) অবস্থার উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
ধারণাগতভাবে একটা **2D array** `dp[i][w]` = প্রথম `i` বই বিবেচনায়, budget `w`-তে max pages। যেহেতু row `i` শুধু row `i-1` পড়ে, এটা একটা **1D array** `dp[w]`-তে compress হয় (size `budget + 1`)। Top-down করলে dict (`(i, rem)` → value)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State দুটো fact: কোন বই পর্যন্ত বিবেচনা করেছি, আর কত budget বাকি। তাই 2D নিখুঁত — কিন্তু একটা row শুধু আগেরটা পড়ে বলে 1D-তে নামে। 1D-তে 0/1 ধরে রাখতে inner loop **right-to-left**: তখন `dp[w - price]` এখনো *আগের* বইয়ের মান (এই বইটা এখনো যোগ হয়নি), তাই বই দুবার গোনা হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা বইয়ে recurse করে দুটো শাখা — কেনো (budget কমাও, pages যোগ) বা বাদ দাও।
```text
best(i, rem): # বই i..n-1 থেকে budget rem-এ max pages
if i == n or rem <= 0: return 0
skip = best(i+1, rem)
take = (best(i+1, rem - price[i]) + pages[i]) if price[i] <= rem else 0
return max(skip, take)
answer = best(0, budget)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এই recursion **O(2^n)** — প্রতিটা বইয়ে দুটো শাখা, সব subset (2^n)। একই `(i, rem)` জোড়া বহুবার পৌঁছানো হয় (overlapping subproblems)। CSES-এর `n` ও budget বড় হলে সম্পূর্ণ অসম্ভব।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct state মাত্র `n × budget`-টা** (`(i, rem)` জোড়া)। প্রতিটার উত্তর একবার গুনে রাখলে exponential subset-search pseudo-polynomial O(n × budget) হয়ে যায়। আর 1D compression-এ শুধু budget-অক্ষ রাখলেই চলে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[i][w]` = শুধু প্রথম `i` বই বিবেচনায়, মোট খরচ সর্বোচ্চ `w` রেখে অর্জনযোগ্য max pages। (1D-তে: `dp[w]` = এ পর্যন্ত process করা বই দিয়ে budget `w`-তে max pages।)
**Transition:**
```text
2D: dp[i][w] = max( dp[i-1][w], # বই i বাদ
dp[i-1][w - price[i]] + pages[i] ) # বই i কেনো (price[i] <= w হলে)
1D (right-to-left): dp[w] = max( dp[w], dp[w - price[i]] + pages[i] )
```
কারণ: বই `i` কিনলে হাত যায় row `i-1`-এ (যেখানে বইটা তখনো কেনা হয়নি) — এটাই "at most once" enforce করে।
**Base case:** `dp[0][w] = 0` সব `w`-এর জন্য (বই নেই, pages নেই); 1D-তে `dp` সব 0 দিয়ে শুরু।
**Answer location:** `dp[n][budget]` (2D), বা `dp[budget]` (1D)।
Memoization (top-down): `best(i, rem)` recursion, dict। Tabulation: প্রতিটা বইয়ে inner loop **ডান-থেকে-বাঁ** — এই direction-ই 0/1 নিশ্চিত করে। বাঁ-থেকে-ডান করলে নিঃশব্দে unbounded (একই বই বারবার) হয়ে যেত।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** এটা #13-এর প্রায় অভিন্ন — শুধু `or` (boolean) বদলে `max` (value)। এই দুই problem পাশাপাশি রেখে loop-direction নিয়মটা মুখস্থ করো: **ডান-থেকে-বাঁ = 0/1, বাঁ-থেকে-ডান = unbounded।** এই একটামাত্র direction-ই Coin Change (unbounded) আর Book Shop (0/1)-এর পুরো পার্থক্য। তাই code লেখার আগে নিজেকে জিজ্ঞেস করো: "item বারবার নেওয়া যায়?" — উত্তর direction ঠিক করে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[w]` = budget `w`-তে max pages। `budget=10`, `price=[4,8,5,3]`, `pages=[5,12,8,1]`:
```text
শুরু: dp = [0]*11
প্রতিটা বই i-তে, ডান-থেকে-বাঁ (w = budget .. price[i]):
dp[w] = max( dp[w], dp[w - price[i]] + pages[i] )
বই 0 (দাম4, পাতা5): dp[4..10] = 5
বই 1 (দাম8, পাতা12): dp[8..10] = max(5, dp[w-8]+12)=12; dp[12+5? না] -> dp[8..]=12 (12>5)
বই 2 (দাম5, পাতা8): dp[9]=max(12, dp[4]+8)=max(12,13)=13; dp[10]=max(12, dp[5]+8)=13
বই 3 (দাম3, পাতা1): ছোট যোগ, 13 বদলায় না
dp[10] = 13 <- answer
```
ডান-থেকে-বাঁ যাওয়া জরুরি: একই বই দুবার কেনা আটকায় (0/1)। বাঁ-থেকে-ডান গেলে একই বই বহুবার কেনা হয়ে যেত।
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`budget=5`, `price=[3,7]`, `pages=[8,9]`, 1D tabulation:
1. `dp = [0,0,0,0,0,0]`
2. বই 0 (দাম3, পাতা8), w=5..3: `dp[5]=max(0,dp[2]+8)=8`; `dp[4]=max(0,dp[1]+8)=8`; `dp[3]=max(0,dp[0]+8)=8` → `dp=[0,0,0,8,8,8]`
3. বই 1 (দাম7, পাতা9): price 7 > budget 5, inner loop চলেই না → কোনো বদল নেই
4. return `dp[5] = 8`
হাতে মিলিয়ে: বই 1 খুব দামি (7 > 5), শুধু বই 0 কেনা যায় → 8 পাতা। ✔
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
# ---- way 1: memoization (top-down) ----
def book_shop_memo(budget, prices, pages):
n = len(prices)
memo = {}
def best(i, rem): # বই i..n-1 থেকে budget rem-এ max pages
if i == n or rem <= 0:
return 0
if (i, rem) in memo:
return memo[(i, rem)]
skip = best(i + 1, rem)
take = 0
if prices[i] <= rem:
take = best(i + 1, rem - prices[i]) + pages[i]
memo[(i, rem)] = max(skip, take)
return memo[(i, rem)]
return best(0, budget)
# ---- way 2: tabulation, full 2D ----
def book_shop_2d(budget, prices, pages):
n = len(prices)
dp = [[0] * (budget + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(budget + 1):
dp[i][w] = dp[i - 1][w] # বই বাদ
if prices[i - 1] <= w:
cand = dp[i - 1][w - prices[i - 1]] + pages[i - 1]
if cand > dp[i][w]:
dp[i][w] = cand # বই কেনো
return dp[n][budget]
# ---- way 3: 1D, right-to-left = 0/1 ----
def book_shop_tab(budget, prices, pages):
n = len(prices)
dp = [0] * (budget + 1)
for i in range(n):
for w in range(budget, prices[i] - 1, -1): # ডান-থেকে-বাঁ -> 0/1
cand = dp[w - prices[i]] + pages[i]
if cand > dp[w]:
dp[w] = cand
return dp[budget]
# ---- tests ----
cases = [
(10, [4, 8, 5, 3], [5, 12, 8, 1], 13), # CSES sample
(5, [3, 7], [8, 9], 8), # শুধু বই 0
(100, [10, 20, 30], [60, 100, 120], 280), # সব কেনা যায়
(0, [1, 2], [5, 6], 0), # budget 0
(50, [10, 20, 30], [60, 100, 120], 220), # subset
(3, [3], [10], 10), # ঠিক fit
]
for budget, prices, pages, want in cases:
assert book_shop_memo(budget, prices, pages) == want, (budget, book_shop_memo(budget, prices, pages))
assert book_shop_2d(budget, prices, pages) == want, (budget, book_shop_2d(budget, prices, pages))
assert book_shop_tab(budget, prices, pages) == want, (budget, book_shop_tab(budget, prices, pages))
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `book_shop_memo`: `best(i, rem)` বই `i` থেকে শুরু করে budget `rem`-এ max pages; শেষ/শূন্য budget → 0; কেনা (price ≤ rem হলে) vs বাদ-এর max; `memo` repeated কাজ এড়ায়।
- `book_shop_2d`: পূর্ণ 2D — প্রতিটা `(i, w)`-তে আগের row-এর "বাদ" মান, আর কিনলে `dp[i-1][w-price]+pages`-এর max; row `i-1`-এ হাত দেওয়াই 0/1 নিশ্চিত করে।
- `book_shop_tab`: 1D, inner loop **ডান-থেকে-বাঁ** — তখন `dp[w-price]` এখনো আগের বইয়ের মান, তাই প্রতিটা বই একবারই গোনা; answer `dp[budget]`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`cases`-এ ছয়টা input — CSES sample `13`, একটা যেখানে শুধু সস্তা বই fits (`8`), all-fit (`280`), budget-0 edge (`0`), একটা subset (`220`), আর একটা ঠিক-fit (`10`)। প্রতিটার জন্য তিন function (memo, 2D, 1D) মিলতে হবে — বিশেষত 1D-র direction যাচাই হয়। সব pass হলে শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
0/1 knapsack (price=weight, pages=value); 1D inner loop **ডান-থেকে-বাঁ** যাতে প্রতিটা বই একবার।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[w] = budget w-তে max pages; ডান-থেকে-বাঁ -> 0/1 (প্রতিটা বই একবার)
function bookShop(budget, prices, pages) {
const n = prices.length;
const dp = new Array(budget + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let w = budget; w >= prices[i]; w--) { // ডান-থেকে-বাঁ
const cand = dp[w - prices[i]] + pages[i];
if (cand > dp[w]) dp[w] = cand;
}
}
return dp[budget];
}
// ---- test cases (example + edge) ----
const cases = [
[10, [4, 8, 5, 3], [5, 12, 8, 1], 13], // CSES sample
[5, [3, 7], [8, 9], 8], // শুধু সস্তা বই fits
[100, [10, 20, 30], [60, 100, 120], 280], // সব কেনা যায়
[0, [1, 2], [5, 6], 0], // budget 0 edge
[50, [10, 20, 30], [60, 100, 120], 220], // subset
[3, [3], [10], 10], // ঠিক fit
];
for (const [budget, prices, pages, want] of cases) {
assert(bookShop(budget, prices, pages) === want, "book " + budget);
}
console.log("সব JS test pass!");
```
> **JS টীকা:** 0/1 নিশ্চিত করতে inner loop **`w = budget` থেকে `prices[i]` পর্যন্ত নিচে** (`w--`) — তখন `dp[w - prices[i]]` এখনো *আগের* বইয়ের মান, তাই বই দুবার গোনা হয় না। বাঁ-থেকে-ডান (`w++`) করলে নিঃশব্দে unbounded (একই বই বহুবার) হয়ে যেত। `new Array(budget+1).fill(0)` primitive বলে নিরাপদ।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function bookShop(budget: number, prices: number[], pages: number[]): number {
const n: number = prices.length;
const dp: number[] = new Array(budget + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let w = budget; w >= prices[i]; w--) {
const cand: number = dp[w - prices[i]] + pages[i];
if (cand > dp[w]) dp[w] = cand;
}
}
return dp[budget];
}
function expect