ডায়নামিক প্রোগ্রামিং৮ মিনিট পড়া

0/1 ন্যাপস্যাক (0/1 Knapsack)

সর্বোচ্চ মূল্যের (value) জন্য একটি ব্যাগ বা স্যুটকেস প্যাক করুন — যেখানে প্রতিটি জিনিস বা আইটেম হয় পুরোপুরি নিতে হবে নতুবা একদমই নেওয়া যাবে না (all-or-nothing)
time:সিউডো-পলিনোমিয়াল (Pseudo-poly) · \(O(n \cdot W)\)space:\(O(n \cdot W)\) বা \(O(W)\)each item:এটি নিন অথবা রেখে যান (take it or leave it)

ধরুন আপনি ভ্রমণের জন্য একটি ব্যাগ বা স্যুটকেস প্যাক করছেন বা গোছাচ্ছেন। আপনার কাছে জিনিসপত্রের বা আইটেমের একটি তালিকা রয়েছে — যার প্রতিটির একটি নির্দিষ্ট ওজন (weight) এবং একটি মূল্য (value) আছে — এবং আপনার ব্যাগটি সর্বোচ্চ W কিলোগ্রাম বা কেজি (kilograms) ওজন ধারণ করতে পারে। এখানকার মূল সীমাবদ্ধতাটি বা ক্যাচ (catch) হলো: আপনাকে হয় একটি আইটেম পুরোপুরি (whole) প্যাক করতে হবে নতুবা সেটিকে ফেলে রেখে যেতে হবে। আপনি চাইলে অর্ধেক জ্যাকেট বা চার ভাগের এক ভাগ ল্যাপটপ নিতে পারবেন না। এটিই হলো মূলত 0/1 ন্যাপস্যাক সমস্যা বা 0/1 Knapsack problem।

এখানকার "0/1" মূলত এটাই নির্দেশ করে যে প্রতিটি আইটেমের বা জিনিসের দুটি স্টেট বা অবস্থা রয়েছে: 0 (ফেলে বা রেখে যাওয়া) অথবা 1 (প্যাক বা ব্যাগে ভর্তি করা)। এতে কোনো প্রকার ভগ্নাংশ বা ফ্র্যাকশন (fractions) এবং ভাগ বা স্প্লিটিং (splitting) থাকে না বা গ্রহণ করা হয় না।

কেন গ্রিডি (Greedy) নীতিটি এখানে কাজ করে না (Why Greedy Doesn't Work Here)

আপনার সহজাত প্রবৃত্তি বা ইনস্টিঙ্কট (instinct) হয়তো বলবে: প্রথমে সবচেয়ে ভালো বা বেস্ট ভ্যালু-প্রতি-কিলো রেশিও (value-per-kilo ratio) বা ওজন-মূল্যের অনুপাত সম্পন্ন আইটেমটি নিন, এরপর দ্বিতীয় সেরাটি নিন এবং এভাবেই চলতে থাকুন। কিন্তু এই পদ্ধতিটি সাধারণত ব্যর্থ হয় বা ফেইল করে (fails)। হতে পারে সবচেয়ে ভালো রেশিওর বা অনুপাতের আইটেমটি নেওয়ার পর ব্যাগে থাকা বাকি অস্বস্তিকর বা বেমানান জায়গাটিতে এমন কিছু আইটেমই ধরবে যা মোটেও দামি বা ভালো ভ্যালুর নয়, বরং বেশ সস্তা (cheap filler)। মূলত আইটেমগুলো একে অপরের সাথে ইন্টারঅ্যাক্ট (interact) বা সম্পর্ক তৈরি করে — আর ডিপি (DP) ঠিক এই ধরনের সমস্যাগুলোকেই একদম নিখুঁতভাবে বা সঠিকভাবে পরিচালনা বা সমাধান করতে পারে।

মূল ধারণা বা দ্য বিগ আইডিয়া (The Big Idea): অন্তর্ভুক্ত (Include) যুক্ত বা বর্জন (Exclude) করুন

উভয়কে সংজ্ঞায়িত বা ডিফাইন করুন বা লিখুন dp[i][w] = সর্বোচ্চ মূল্য (maximum value) বা ভ্যালু যা আপনি প্রথম i সংখ্যক আইটেম এবং ঠিক w পরিমাণ ওজন বা ওয়েট লিমিট ব্যবহার করে প্যাক বা অর্জন করতে পারবেন। প্রতিটি আইটেমের জন্য, আপনি ঠিক দুটি সুযোগ বা চয়েচের (choices) সম্মুখীন হবেন:

i আইটেমটিকে ফেলে বা রেখে যাওয়া (Leave): dp[i][w] = dp[i-1][w] — অর্থাৎ এই আইটেমটি ছাড়াই পূর্বে থাকা সবচেয়ে ভালো বা বেস্ট (best) ভ্যালু বা মানের সমান।

i আইটেমটিকে প্যাক করা বা নেয়া (Pack) (শুধুমাত্র তখনই যখন এটি ব্যাগে ধরবে, অর্থাৎ wt[i] ≤ w): dp[i][w] = dp[i-1][w - wt[i]] + val[i]।

এই দুই চয়েস বা পছন্দের মধ্যে যেটির মান বেশি (larger), আপনি মূলত সেটিকেই গ্রহণ করবেন। এখানকার বেস কেসগুলো (Base cases) হলো: যেকোনো পরিমাণ w-এর জন্য dp[0][w] = 0 (কোনো আইটেম নেই = তাই এর কোনো ভ্যালুও নেই), এবং সমস্ত i-এর জন্য dp[i][0] = 0 (ওজন নেওয়ার জিরো বা শূন্য ক্যাপাসিটি (capacity) = অর্থাৎ কিছুই ব্যাগে ধরবে না)।

স্পেস বা জায়গাকে 1D-এ অপ্টিমাইজ করা বা কমানো (Space Optimization to 1D)

লক্ষ্য করুন যে, dp[i][w] মূলত শুধুমাত্র এর উপরের সারির (row i-1) দিকে তাকায়। তাই আপনি চাইলে 2D টেবিল বা ছকটিকে ভেঙে তা শুধুমাত্র একটি সিঙ্গেল বা একক 1D অ্যারেতে (array) রূপান্তর বা কলাপ্স (collapse) করতে পারবেন। কিন্তু এখানে একটি বাধা বা ক্যাচ বা শর্ত আছে: আপনাকে অবশ্যই ওজনের পরিমাণটি W থেকে শুরু করে wt[i]-এর দিকে নিচে (down) ইটারেট (iterate) করতে হবে। আর আপনি যদি এটিকে বাঁ থেকে ডান (left-to-right) দিকে পরিচালনা করতেন, তখন ভুলবশত আপনি আইটেম i-কে নিজেই নিজের সাথে যুক্ত হওয়ার সুযোগ করে দিতেন — অর্থাৎ এর মাধ্যমে সেটিকে আপনি মূলত একাধিকবার ব্যবহার করতেন। পক্ষান্তরে ডান-থেকে-বাম (Right-to-left) পদ্ধতিটি প্রতিটি আইটেমকে শুধুমাত্র একবার ব্যবহারের মধ্যেই সীমাবদ্ধ রাখে।

আপনি কী প্যাক বা বহন করেছেন তা পুনরায় গঠন করা বা পুনর্নির্মাণ করা (Reconstructing What You Packed)

এর একেবারে শেষের বা ফাইনাল dp[n][W]-টি আপনাকে সর্বোচ্চ বা ম্যাক্সিমাম ভ্যালু বা মূল্যের (maximum value) পরিমাণটা জানিয়ে দেয়। কিন্তু আপনি ঠিক কোন কোন (which) আইটেমগুলো প্যাক করেছেন তা বের করতে, আপনাকে সেল বা ঘর (n, W) থেকে শুরু করে পুরো 2D টেবিলটি বা ছকটি আবার ট্রেস ব্যাক (trace back) বা পেছনের দিকে অনুসরণ করতে হবে: যদি dp[i][w]-এর মান তার উপরের অর্থাৎ dp[i-1][w]-এর রোর বা কলামের ভ্যালুর চেয়ে আলাদা বা ভিন্ন (differs) হয়, তার মানে হলো আপনি আইটেম i-কে এর অন্তর্ভুক্ত বা ইনক্লুডেড (included) করেছিলেন — তাই এর ওজন বা ওয়েট বিয়োগ করুন বা বাদ দিন এবং এরপর উপরের সারিতে উঠে যান। অন্যথায় বা নতুবা, আপনি ধরে নিতে পারেন যে আইটেম i-কে স্কিপ বা বাদ দেওয়া (skipped) হয়েছিল — তাই শুধু সোজা উপরের সারিতে উঠে যান। মনে রাখবেন যে এই রিকনস্ট্রাকশন (Reconstruction) বা পুনর্নির্মাণের কাজটি সম্পন্ন করতে শুধুমাত্র শেষের সারির (last row) নয়, বরং আপনার পুরো 2D টেবিলেরই প্রয়োজন হবে।

দ্রষ্টব্য: 0/1 ন্যাপস্যাককে (0/1 Knapsack) মূলত একটি 'সিউডো-পলিনোমিয়াল (pseudo-polynomial)' বলা হয় কারণ \(O(n \cdot W)\)-কে সাধারণ চোখে একটি পলিনোমিয়ালের (polynomial) মতো দেখতে মনে হলেও মূলত বাইনারি নিয়মে W-এর পরিমাণটি খুব বিশাল বা অ্যাস্ট্রোনমিক্যাল (astronomically large) হতে পারে — যা থিওরি বা তত্ত্বে এই সমস্যাটিকে NP-হার্ড (NP-hard) করে তোলে, তবে যুক্তিসঙ্গত বা পরিমিত W-এর মানের জন্য বাস্তবে এটি বেশ দ্রুতগতিতে (fast) কাজ করে।

0/1 ন্যাপস্যাক (0/1 Knapsack) — 1D স্পেস অপ্টিমাইজড বা স্মৃতি-সাশ্রয়ী

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for cap in range(W, w - 1, -1):  # right to left!
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[W]


weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
print(knapsack(weights, values, 8))  # 10
Output
10

Complexity

⏱️ সময় বা টাইম (Time)
n সংখ্যক আইটেম × W+1 সংখ্যক ক্যাপাসিটি ভ্যালু বা মান — W-এর মান যুক্তিসঙ্গত বা পরিমিত হলে এটি বেশ দ্রুত (fast) কাজ করে
সিউডো-পলিনোমিয়াল (Pseudo-polynomial) \(O(n \cdot W)\)
📊 জায়গা বা স্পেস (2D টেবিল)
আপনি ঠিক কোন কোন আইটেমগুলো প্যাক করেছেন সেটি রিকনস্ট্রাকশন (reconstruct) বা পুনর্নির্মাণ করতে চাইলে এই সম্পূর্ণ টেবিলটি অপরিহার্য বা অত্যন্ত প্রয়োজনীয় (required)
সম্পূর্ণ বা ফুল টেবিল (Full table) \(O(n \cdot W)\)
🪄 জায়গা বা স্পেস (1D অপ্টিমাইজড (optimized))
এর ক্যাপাসিটি বা ধারণক্ষমতাকে ডান-থেকে-বামে (right-to-left) ইটারেট (Iterate) করুন; এর ফলে আপনার রিকনস্ট্রাকশন করার এবিলিটি বা ক্ষমতাটি (reconstruction ability) হারিয়ে যায়
একক সারি বা সিংগেল রো (Single row) \(O(W)\)
🔍 আইটেম রিকনস্ট্রাকশন বা পুনর্নির্মাণ (Item reconstruction)
2D টেবিল থেকে পিছনের দিকে (backwards) হেঁটে চলুন বা যান — যেখানে মোট \(O(n)\) সারিগুলো (rows) এবং \(O(W)\) ধাপগুলো (steps) রয়েছে
ট্রেস-ব্যাক (Trace-back) \(O(n + W)\)
🐌 ব্রুট ফোর্স বা সম্পূর্ণ চেষ্টা বা সাধারণ পদ্ধতি (Brute force - all subsets)
W-এর মান যখন আপনার নিয়ন্ত্রণে বা ম্যানেজেবল (manageable) থাকে, তখন ব্রুট ফোর্সের থেকে ডিপি-র (DP)'s \(O(n \cdot W)\) মূলত এক্সপোনেনশিয়ালভাবেই (exponentially) বা বহুগুণে ভালো বা বেটার কাজ করে।
এক্সপোনেনশিয়াল (Exponential) \(O(2^n)\)

ছোট কুইজ

1D সংস্করণে বা ভার্সনে ইনার লুপটিকে (inner loop) কেন উপরের দিকের মান W থেকে একদম নিচের দিক wt[i] (ডান থেকে বাম দিকে) পর্যন্ত যেতে হয়?

পড়া চালিয়ে যান

1D ডিপি (1D DP)
সিঁড়ি বেয়ে ওপরে ওঠার মতোই — ধাপে ধাপে নিজের উত্তর তৈরি বা নির্মাণ করুন
→
আনবাউন্ডেড ন্যাপস্যাক (Unbounded Knapsack)
প্রতিটি আইটেম যত খুশি ততবার নিতে পারেন — অনেকটা অফুরন্ত স্টকের কোনো বিশাল মুদি দোকানের মতো
→
ফ্র্যাকশনাল ন্যাপস্যাক বা ভগ্নাংশ ন্যাপস্যাক (Fractional Knapsack)
একটি ব্যাকপ্যাক সোনার ধুলো দিয়ে ভরছেন — প্রতি গ্রামের সর্বোচ্চ মূল্যের বস্তু আগে নিন
→