014 — Book Shop

Source

• Original source: CSES Problem Set — Dynamic Programming section
• Platform: CSES — https://cses.fi/problemset/task/1158
• 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-এর শিক্ষা

1. Problem in simple words

একটা দোকানে n-টা বই, প্রতিটার একটা দাম price[i] আর কত পাতা pages[i]। তোমার হাতে মোট budget (x) টাকা। প্রতিটা বই সর্বোচ্চ একবার কিনতে পারো (একটাই কপি)। budget-এর মধ্যে থেকে সবচেয়ে বেশি মোট পাতা (pages) কিনতে চাও — সেই সর্বোচ্চ pages বের করো। এটা ধ্রুপদী 0/1 knapsack: price = weight, pages = value, budget = capacity।

budget = 10
price = [4, 8, 5, 3]
pages = [5, 12, 8, 1]
সেরা: বই 0 (দাম 4, পাতা 5) + বই 2 (দাম 5, পাতা 8) = দাম 9 <= 10, পাতা 13

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] এখনো আগের বইয়ের মান (এই বইটা এখনো যোগ হয়নি), তাই বই দুবার গোনা হয় না।

6. Real-life analogy

ভাবো নির্দিষ্ট বাজেট নিয়ে বইমেলায় গেছ, প্রতিটা বইয়ের একটা দাম আর তোমার চোখে একটা "মূল্য" (কত পাতা/আনন্দ)। প্রতিটা বইয়ের সামনে দাঁড়িয়ে ভাবো: "এটা কিনলে বাকি টাকায় বাকি বই থেকে সর্বোচ্চ কত পাব?" বনাম "এটা না কিনলে?" — বড়টা বেছে এগোও। প্রতিটা বই একটাই কপি, তাই একবার কিনলে সেটা আর তালিকায় নেই।

7. Visual explanation

dp[w] = budget w-তে max pages। budget=10, price=[4,8,5,3], pages=[5,12,8,1]:

শুরু: 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)। বাঁ-থেকে-ডান গেলে একই বই বহুবার কেনা হয়ে যেত।

8. Example input and output

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)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা বইয়ে recurse করে দুটো শাখা — কেনো (budget কমাও, pages যোগ) বা বাদ দাও।

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:

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 ঠিক করে দেয়।

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 পাতা। ✔

15. Python solution

# ---- 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]।

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!।

18. Time complexity

তিন version-ই O(n × budget) (pseudo-polynomial) — n বই, প্রতিটায় budget পর্যন্ত। CSES limit-এর জন্য যথেষ্ট।

19. Space complexity

• Memoization: O(n × budget) — dict + recursion stack।
• Full 2D: O(n × budget) — 2D array।
• 1D: O(budget) — এক array (CSES-এ এটাই পছন্দনীয়)।

20. Common mistakes

• 1D inner loop বাঁ-থেকে-ডান করা — তখন একই বই বহুবার কেনা হয় (unbounded), pages বেশি/ভুল আসে; 0/1-এর জন্য অবশ্যই ডান-থেকে-বাঁ।
• 2D-তে বই কেনার সময় dp[i][w-price] পড়া (dp[i-1][w-price]-এর বদলে) — তখনও একই row, বই দুবার গোনা হয়।
• price[i] <= w/rem শর্ত ভুলে যাওয়া — negative index বা অবৈধ কেনা; বই কেনার আগে সবসময় afford check।

21. Which basic problem this inherits from

ভিত্তি: #13-এর take-or-leave, boolean-কে value/max দিয়ে বদলানো; loop-direction শিক্ষা একই। ../state-transition-thinking.md-এর "Problem 6 — 0/1 Knapsack" section-এ ঠিক এই 2D state, 1D compression, আর direction warning আছে; ../patterns.md-এর "0/1 knapsack" family-ও এখানে।

22. Similar harder problems

• Partition Equal Subset Sum (boolean সংস্করণ) — https://leetcode.com/problems/partition-equal-subset-sum/ (এই tracker-এর #13)
• Coin Change (unbounded — loop direction উল্টো) — https://leetcode.com/problems/coin-change/ (#10)
• Target Sum (subset-sum-এ রূপান্তর) — https://leetcode.com/problems/target-sum/

23. Pattern learned

0/1 knapsack: state dp[i][w] (প্রথম i item, capacity w-তে max value), transition max(বাদ, নাও), base সব 0, 1D compression-এ inner loop right-to-left। loop-direction নিয়মটাই মূল শিক্ষা: ডান-থেকে-বাঁ = 0/1, বাঁ-থেকে-ডান = unbounded।

24. Final summary

ভবিষ্যতের আমাকে: "Book Shop = textbook 0/1 knapsack (price=weight, pages=value)।" State dp[w] = budget w-তে max pages, transition dp[w] = max(dp[w], dp[w-price]+pages), base সব 0, উত্তর dp[budget]। মনে রেখো: 0/1 নিশ্চিত করতে 1D inner loop ডান-থেকে-বাঁ — এটাই unbounded থেকে আলাদা করে।

25. JavaScript solution (with test cases)

0/1 knapsack (price=weight, pages=value); 1D inner loop ডান-থেকে-বাঁ যাতে প্রতিটা বই একবার।

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 বলে নিরাপদ।

26. TypeScript solution (with test cases)

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<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[number, number[], number[], number]> = [
  [10, [4, 8, 5, 3], [5, 12, 8, 1], 13],
  [5, [3, 7], [8, 9], 8],
  [100, [10, 20, 30], [60, 100, 120], 280],
  [0, [1, 2], [5, 6], 0],
  [50, [10, 20, 30], [60, 100, 120], 220],
];
for (const [budget, prices, pages, want] of cases) expect(bookShop(budget, prices, pages), want, "book");
console.log("সব TS test pass!");

TS টীকা: prices: number[], pages: number[] typing দিয়ে weight ও value array আলাদা করে স্পষ্ট; cases: Array<[number, number[], number[], number]> tuple-type প্রতিটা case-এর চার অংশ (budget, prices, pages, expected) locked করে, ভুল arity বা type compile-time-এ ধরা পড়ে।

27. কোথায় কাজে লাগে (real-world use)

• Budget-constrained selection: নির্দিষ্ট বাজেটে সর্বোচ্চ মোট মূল্য/উপযোগিতার item বাছা, প্রতিটা একবার (কেনাকাটা, procurement)।
• Project / feature portfolio: সীমিত resource-এ সর্বোচ্চ মোট value-র feature/project বাছা (capital budgeting)।
• Cargo / container loading: ওজন-সীমার মধ্যে সর্বোচ্চ মূল্যের পণ্য তোলা (classic 0/1 knapsack)।
• Ad / campaign selection: নির্দিষ্ট spend-এ সর্বোচ্চ প্রত্যাশিত return-এর বিজ্ঞাপন-সেট।
• Time-boxed task picking: নির্দিষ্ট সময়ে সর্বোচ্চ মোট মূল্যের কাজ সম্পন্ন করা।

মূল pattern: 0/1 knapsack — dp[w] = max(dp[w], dp[w-weight]+value), 1D inner loop right-to-left (item একবার); left-to-right হলে unbounded।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।