আনবাউন্ডেড ন্যাপস্যাক (Unbounded Knapsack)

বিস্কুট, চিপস বা চকলেটে ভরা একটি বিশাল মুদি দোকানের কথা ভাবুন। আপনার কাছে নির্দিষ্ট পরিমাণ টাকা আছে, এবং আপনি আপনার ইচ্ছামতো যেকোনো জিনিস যতবার খুশি কিনতে পারবেন — কোনো আইটেমের নির্দিষ্ট পরিমাণের সীমা নেই (কারণ তাদের গোডাউনে অফুরন্ত স্টক)। আপনি চেষ্টা করছেন আপনার টাকায় সর্বোচ্চ কী পরিমাণ জিনিস পাওয়া যায় তা বের করতে। এটিই হলো আনবাউন্ডেড ন্যাপস্যাক (Unbounded Knapsack)।

এটিকে 0/1 ন্যাপস্যাকের (0/1 Knapsack) সাথে তুলনা করুন, যেখানে প্রতিটি আইটেম অনন্য বা একবারই নেওয়া যায় (যেমন একটি সুটকেস গোছানো — আপনার কাছে কেবল একটি জ্যাকেট আছে)। এখানে, সরবরাহের কোনো শেষ নেই। এই একটিমাত্র পার্থক্য পুরো ডাইনামিক প্রোগ্রামিং (DP) আপডেটের দিক বা ডিরেকশনকে পুরোপুরি বদলে দেয়।

সেই একদিকের পরিবর্তন (The One-Direction Flip)

0/1 ন্যাপস্যাকের ক্ষেত্রে, একই আইটেম যাতে দ্বিতীয়বার ব্যবহার না হয়, সেজন্য আমরা ক্যাপাসিটি বা ধারণক্ষমতাকে ডান থেকে বাম দিকে (right to left) ইটারেট করেছিলাম। কিন্তু আনবাউন্ডেড ন্যাপস্যাকের ক্ষেত্রে, আমরা একই আইটেম বারবার ব্যবহার করতে চাই — তাই আমরা এটিকে বাম থেকে ডান দিকে (left to right) ইটারেট করি। যখন আমরা dp[cap] হিসেব করি, তখন বর্তমান পাসে ইতিমধ্যেই dp[cap - wt[i]] আপডেট হয়ে গেছে, যার মানে হলো i নম্বর আইটেমটি হয়তো আবার ব্যবহার করা হয়েছে। আর ঠিক এটিই আমরা চাই।

রিকারেন্স বা পুনরাবৃত্তি সূত্র: প্রতিটি আইটেম i এর জন্য dp[cap] = max(dp[cap], dp[cap - wt[i]] + val[i]), যেখানে cap এর মান wt[i] থেকে W পর্যন্ত ইটারেট করে।

কয়েন চেঞ্জ — ন্যূনতম কয়েন (Minimum Coins)

আপনাকে কিছু নির্দিষ্ট মানের কয়েন দেওয়া হলো, একটি নির্দিষ্ট পরিমাণ টাকা মেলাতে আপনার সবচেয়ে কম কয়টি কয়েন লাগবে? এটিও একটি আনবাউন্ডেড ন্যাপস্যাক সমস্যা যেখানে প্রতিটি "আইটেম" হলো একটি কয়েন, এর "ওজন" বা ওয়েট হলো কয়েনের মান, এবং আপনি সর্বোচ্চ লাভ খোঁজার বদলে কয়েনের সংখ্যা কমানোর চেষ্টা করছেন। সূত্রটি হলো dp[amount] = min over all coins c of (dp[amount - c] + 1)। প্রাথমিকভাবে dp[0] = 0, এবং w > 0 এর জন্য dp[w] = ∞ দিয়ে শুরু করতে হয়।

কয়েন চেঞ্জ ২ — উপায় গণনা (Count the Ways)

মোট কতটি ভিন্ন ভিন্ন কয়েনের মাধ্যমে লক্ষ্যমাত্রার পরিমাণটি মেলানো সম্ভব? প্রতিটি কয়েন c এর জন্য dp[w] += dp[w - c]। তবে এখানে একটু সাবধান হতে হবে: কয়েনগুলোকে বাইরের লুপে (outer loop) রাখুন এবং টাকার পরিমাণগুলোকে ভেতরের লুপে রাখুন। এর ফলে শুধু কম্বিনেশনগুলো (combinations) গণনা করা হবে (যেখানে [1,2] এবং [2,1] একই বোঝায়)। যদি আপনি লুপগুলো উল্টে দেন, তবে এটি পারমিউটেশন (permutations) বা বিন্যাস গণনা করতে শুরু করবে।

রড কাটিং (Rod Cutting)

n দৈর্ঘ্যের একটি রডকে কেটে ছোট টুকরো করে বিক্রি করা যায়। কাটার পর প্রতিটি ছোট টুকরোর দৈর্ঘ্যের একটি নির্দিষ্ট দাম আছে। আপনাকে সর্বোচ্চ আয় বা রেভিনিউ নিশ্চিত করতে হবে। এখানে কাটা প্রতিটি দৈর্ঘ্য একটি বারবার ব্যবহারযোগ্য বা রিউজেবল (reusable) "আইটেম" — এটি একটি পুরোপুরি আনবাউন্ডেড ন্যাপস্যাক সমস্যা। সূত্রটি হলো dp[l] = max over all cut lengths c of (price[c] + dp[l - c])।