গ্রিডি এবং ডিপি দিয়ে ন্যাপস্যাক(Knapsack with Greedy & DP) | 0/1 Knapsack

গ্রিডি অ্যালগরিদম

গ্রিডি মানে লোভী! মানে যখন, আমি কারো থেকে কিছু জিনিস নিতে যাব, তখন আমি চেষ্টা করব যেন বেশি বেশি জিনিস নিতে পারি আবার অপরদিকে যখন আমি কাওকে কিছু দিতে যাব, তখন চেষ্টা করব কম কম দিতে। সহজ ভাষায়, এই যে এভাবে বেশি বেশি নিয়ে বা কম কম দিয়ে কাজ করার পদ্ধতিই হচ্ছে গ্রিডি অ্যালগরিদম।

Source: Wikipedia

ধরে নিলাম আমি একটি দোকানে গিয়েছি এবং সেখানে আজকে কিছু পণ্য ফ্রী দেওয়া হচ্ছে! কপাল খারাপ আমি যে ন্যাপস্যাক বা ব্যাগ নিয়ে গেছি তাতে ৮ কেজির বেশি পণ্য আটে না :| এখন কিছু পণ্য আমার সামনে দেওয়া হলো যেগুলো ফ্রী তে দেওয়া হচ্ছে। পণ্য গুলো হলো,
১ম পণ্যের ওজন ১ কেজি এবং মূল্য ১ টাকা,
২য় পণ্যের ওজন ৪ কেজি এবং মূল্য ৫ টাকা,
৩য় পণ্যের ওজন ৪ কেজি এবং মূল্য ৫ টাকা
এবং ৪র্থ পণ্যের ওজন ৫ কেজি এবং মূল্য ১০ টাকা।
এখানে ৪ কেজির পণ্য নিলে পুরোটাই নিতে হবে। এই পণ্য থেকে ১, ২ বা ৩ কেজি নেওয়া যাবে না। ধরে নিন পণ্যটি একটি টিভি।

এখন আমি কী করব? সাধারণত যেভাবে ৮ কেজি নির্বাচন করলে আমার লাভ হবে সেভাবে নির্বাচন করার লোভ আমার হবেই। তাই যার মূল্য বেশি আমি তাকেই প্রথমে নিব, এভাবে ৮ কেজি না হওয়া পর্যন্ত আমি নিতেই থাকব। তাহলে প্রথমে নিলাম ৫ কেজির পণ্যটি এরপর নিব ১ কেজির পণ্যটি। ৪ কেজির কোন পণ্য নিতে পারব না কারণ ৫ কেজি আগেই নিয়ে ফেলাতে ব্যাগে জায়গা হবে না। তাহলে আমার মোট লাভ হবে ১১ টাকা এবং তার মোট ওজন ৬ কেজি।

আশা করছি বিষয়টি বুঝে ফেলেছেন। এখন এই এমন সমস্যা সমাধান করব কীভাবে? যেহেতু যার মূল্য বেশি তাকে নিলেই আমার লাভ হচ্ছে, তাই মূল্য অনুযায়ী অ্যারে কে সর্ট করে বেশি দামি মূল্যের পণ্য নিতে শুরু করব। ততক্ষণ পর্যন্ত নিতে থাকব যতক্ষণ পর্যন্ত আমার ব্যাগে পণ্য নেওয়ার মত জায়গা খালি থাকবে। 

int Greedy(int n,int Cap,vector <pair<int,int> > ar) {   // sort the ar by Profit wise with increase order   sort(ar.begin(), ar.end());   int MaxProfit = 0;   // We start from back Cause we need max Profit   for (int i = n-1;i >= 0;i--) {     int Profit = ar[i].first;     int Weight = ar[i].second;     if (Weight <= Cap) {       // Add Cur Profit to Maxprofit       MaxProfit += Profit;       // Reduce Cap by Weight       Cap -= Weight;     } else {       // We can't take Current Profit       // Cause we don't have enough spaces     }   }   return MaxProfit; } int main() {   int n, Cap;   cin >> n >> Cap;   vector <pair <int, int> > ar(n);   for (int i = 0;i < n;i++) {     int Weight, Profit;     cin >> Weight >> Profit;     // We store Profit first,     // cause we will sort ar array with Profit wise     ar[i].first = Profit;     ar[i].second = Weight;   }   cout << Greedy(n, Cap, ar) << '\n';   return 0; }

আপনি যদি STL না শিখে থাকেন তাহলে এই ধরনের সমস্যা সমাধান করতে একটু বেশি কষ্ট করতে হবে। আর সম্ভবত উপরের প্রোগ্রাম বুঝতে পারবেন না। উপরের প্রোগ্রাম বুঝার জন্যে আপনার vector এবং pair শিখতে হবে। এই ভিডিও এবং এই লেখা থেকে শিখে নিতে পারেন।

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

একটি চিরন্তন সত্য হচ্ছে, সবসময় লোভ করা ভালো না :p যেমন, মাঝের ২টি পণ্যের দাম ৫ টাকা না হয়ে যদি ৬ টাকা করে হয় তাহলে কিন্তু গ্রিডি উপায়ে পণ্য নির্বাচন করলে ঠকতে হবে। গ্রিডি উপায়ে পণ্য নির্বাচন করলে শেষ আর প্রথম পণ্য টি নিবে এবং মোট মূল্য হবে ১১ টাকা কিন্তু আমি যদি মাঝের ২টি পণ্য নিতাম তাহলে কিন্তু আমি মোট ১২ টাকার জিনিস পেতাম!

তাহলে দেখলাম গ্রিডি অ্যালগরিদম সবসময় কাজ করে না। আমাদের এখন অন্য উপায় বের করতে হবে। একটি উপায় হচ্ছে, অ্যারেটির সবরকম সাবসিকোয়েন্স বিন্যাস বের করে, কোন সাবসিকোয়েন্স টি নিলে বেশি লাভ হবে তা দেখতে পারি। কিন্তু এর কমপ্লেক্সিটি হচ্ছে, O(2^N); এর ও বেশি। কিন্তু এটি O(N * Cap); (Cap=Bag Capacity) তেই সমাধান করা সম্ভব। 

এখন আলোচনা করব ডায়নামিক প্রোগ্রামিংয়ের একটি বিখ্যাত ও ক্লাসিক অ্যালগরিদম ০/১ ন্যাপস্যাক নিয়ে। আমাদের কাছে যে যে তথ্য গুলো আছে তা হচ্ছে,
ওজন Weight[] = {1, 4, 4, 5}; ,
মূল্য বা প্রফিট Profit[] = {1, 6, 6, 10};
এবংব্যাগ এর ক্যাপাসিটি Cap = 8।
একটি ২ ডাইমেনশনের অ্যারে নিতে হবে int dp[N+1][Cap+1]; এবং এর সবগুলো ইনডেক্সে 0 রেখে দিব। এরপর n বার লুপ চালাব এবং প্রতি n এর জন্য Cap তম বার লুপ চালাতে হবে। মানে বর্তমান পণ্যের জন্যে Cap এর প্রতি ইনডেক্সে দেখতে হবে সেই পণ্য টি নিলে বেশি লাভ নাকি না নিলে বেশি লাভ।

মূল আইডিয়াঃ
dp[i][j] = dp[i-1][j]; // বর্তমান পণ্য টি না নিয়ে।
যদি বর্তমান ক্যাপাসিটি মানে, dp[i][j] এর j বর্তমান পণ্যের Weight[i-1] এর থেকে বড় বা সমান হয়,
dp[i][j] = max(dp[i][j], dp[i-1][j-Weight[i-1]] + Profit[i-1]); // বর্তমান পণ্য নিয়ে যদি বেশি লাভ হয় তাহলে সেটি নিয়েই সামনে এগিয়ে যাব।

* কেইস ১ঃ যখন শূন্য টি পণ্য নিতেছি তখন আমাদের কোন প্রফিট নেই, dp[0][j] = 0; (0 ≤ j ≤ Cap)। ঠিক একই ভাবে যখন ব্যাগ এ কোন জায়গা নেই তখন ও প্রফিট নেই, dp[i][0] = 0; (0 ≤ i ≤ N)।

* কেইস ২ঃ এখন ১ম পণ্যটি নিলে যখন ব্যাগের ক্যাপাসিটি ১ তখন এই পণ্যটি নিতে পারব কারণ পণ্যটির ওজন ও ১ কেজি, তাই ১ তম ইনডেক্সে প্রফিট ১ বসিয়ে দিব dp[1][1] = 1;। যেহেতু ১ম পণ্য তে আছি বা একটি মাত্র পণ্য নিয়েছি তাই ব্যাগের ক্যাপাসিটি আর যতই বেশি হোক প্রফিট বেশি হওয়ার কোন সম্ভাবনা নেই। তাই পরের বাকি ইনডেক্স গুলো তেও প্রফিট ১ ই রেখে দিব।

* কেইস ৩ঃ dp[2][0] থেকে dp[2][3] পর্যন্ত ইনডেক্স গুলোতে যেহেতু ২য় পণ্যটি নিতে পারছি না তাই dp[2-1][0] থেকে dp[2-1][3] পর্যন্ত যা আছে তাই dp[2][0] থেকে dp[2][3] পর্যন্ত ইনডেক্স গুলোতে রেখে দিব। ২য় পণ্যটির ওজন ৪ কেজি তাই dp[2][4] = 6; রেখে দিব যদি না dp[2-1][4]; তে এর থেকে বেশি প্রফিট থাকে। dp[2][5] তে dp[2-1][5] এবং (dp[2-1][5-4] + ২য় পণ্যের প্রফিট) এর মাঝে ম্যাক্সিমাম টা রেখে দিব। dp[2][6] তে dp[2-1][6] এবং (dp[2-1][6-4] + ২য় পণ্যের প্রফিট) এর মাঝে ম্যাক্সিমাম টা রেখে দিব। এভাবে শেষ পর্যন্ত যেতে হবে।

এখানে dp[2-1][5-4]+Profit[2-1] বা dp[i-1][j - Weight[i-1]]+Profit[i-1] তে j এর সাথে ৪ বিয়োগ করছি কারণ বর্তমান পণ্যটির ওজন ৪ কেজি আর dp[2-1][5] বা dp[i-1][j] তে i এর সাথে ১ বিয়োগ করছি কারণ বর্তমান পণ্যটি না নিয়ে দেখতেছি তাই। i-1 এর j তম ইনডেক্স পর্যন্ত অবশ্যই বর্তমান পণ্য ছাড়া আগে যেসব পণ্য নিয়েছি তাদের ম্যাক্সিমাম প্রফিট আছে।

একই ভাবে বাকি পণ্য গুলোর জন্যেও দেখব এবং অবশ্যই ম্যাক্সিমাম উত্তর dp[N][Cap] তে গিয়ে জমা হবে। এখানে উল্লেখ্য বিষয় হচ্ছে, এই যে টেবিলের বিভিন্ন জায়গায় বিভিন্ন কেইসের কথা আলোচনা করলাম। এগুলো নিয়ে কিন্তু আমাদের আলাদা আলাদা চিন্তা করার দরকার নেই। মূল আইডিয়া অনুযায়ী আপনা-আপনিই কাজ হয়ে যাবে। তবে ১ম কেইস টির জন্য আগে থেকেই সব ইনডেক্সে শূন্য বসিয়ে নিতে হবে। এটির মেমোরি কমপ্লেক্সিটিও O(N * Cap);।

const int N = 100; int Weight[N+1], Profit[N+1]; int dp[N+1][N+1]; int n, Cap; int KnapSack() {   for (int i = 1;i <= n;i++) {     for (int j = 1;j <= Cap;j++) {       int WithoutCurProfit = 0;       int WithCurProfit = 0;       WithoutCurProfit = dp[i-1][j];       int wgt = Weight[i-1];       if (j-wgt >= 0)         WithCurProfit = dp[i-1][j-wgt] + Profit[i-1];       dp[i][j] = max(WithoutCurProfit, WithCurProfit);     }   }   return dp[n][Cap]; } int main() {   cin >> n >> Cap;   for (int i = 0;i < n;i++) {     cin >> Weight[i] >> Profit[i];   }   // Initialize with safe value   for (int i = 0;i <= N;i++) {     for (int j = 0;j <= N;j++) {       dp[i][j] = 0;     }   }   cout << KnapSack() << '\n';   return 0; }

এ ত গেল ইটারেটিভ পদ্ধতি, এখন রিকারশন দিয়ে সমাধান করব কীভাবে? শুরু করব ফাংশনের প্যারামিটার N এবং Cap দিয়ে। বেইস কেইস হচ্ছে যখন N শূন্য হয়ে যাবে তখন শূন্য রিটার্ন করে দিব। আরেকটি কাজ হচ্ছে dp[I][Cap]; (I=N) যদি ইতিমধ্যে ক্যালকুলেটেড হয়ে থাকে তাহলে আর নতুন করে ক্যালকুলেটেড করব না। এখানেই ডিপির কারসাজী। ওভারলেপিং সাব প্রবলেম গুলো ক্যালকুলেট না করা। এখন আমাদের মূল কাজ। আগের মতই বর্তমান পণ্য নিয়ে দেখব একবার এবং না নিয়ে দেখব একবার। যেটি ম্যাক্সিমাম হবে সেটিই নিয়ে রাখব।
dp[I][Cap] = KnapSack(I-1, Cap); // বর্তমান পণ্য টি না নিয়ে
যদি বর্তমান ক্যাপাসিটি মানে, dp[I][Cap] এর Cap বর্তমান পণ্যের Weight[I-1] এর থেকে বড় বা সমান হয়,
dp[I][Cap] = max(dp[I][Cap], KnapSack(I-1, Cap-Weight[I-1]) + Profit[I-1]); // বর্তমান পণ্য নিয়ে যদি বেশি লাভ হয় তাহলে সেটি নিয়েই সামনে এগিয়ে যাব।

const int N = 100; int Weight[N+1], Profit[N+1]; int dp[N+1][N+1]; int n, Cap; int KnapSack(int I, int C) {   // base case   if (I == 0) return 0;   // return if it already calculated   if (dp[I][C] != -1) return dp[I][C];   int WithoutCurProfit = 0;   int WithCurProfit = 0;   WithoutCurProfit = KnapSack(I-1, C);   int wgt = Weight[I-1];   if (C >= wgt)     WithCurProfit = KnapSack(I-1, C-wgt) + Profit[I-1];   return dp[I][C] = max(WithoutCurProfit, WithCurProfit); } int main() {   cin >> n >> Cap;   for (int i = 0;i < n;i++) {     cin >> Weight[i] >> Profit[i];   }   // Initialize with safe value   for (int i = 0;i <= N;i++) {     for (int j = 0;j <= N;j++) {       dp[i][j] = -1;     }   }   cout << KnapSack(n, Cap) << '\n';   return 0; }

যেহেতু স্টেট ২টা, N বা I এবং Cap, তাই এর কমপ্লেক্সিটি হবে আগের মতই O(N * Cap); তবে মেমোরাইজেশন না করলে মানে ক্যালকুলটেড ফাংশন ফিরিয়ে না দিলে কমপ্লেক্সিটি কিন্তু O(2^N) এর থেকেও বেশি হত। যেহেতু আমরা একটি ফাংশন থেকে আরো ২টি ফাংশন কল দিতেছি।

যদি এরপরেও বুঝতে সমস্যা হয় তাহলে নিচের ফিগার টি দেখে নিন, আশা করছি আরো ভালো বুঝতে পারবেন।

ফিগারে নীল ফাংশন কল গুলো কল হবে না কারণ, হয় এগুলো আগে কল হয়েছে অথবা জায়গা স্বল্পতা। এভাবেই ডায়নামিক প্রোগ্রামিং দিয়ে অতিরিক্ত কাজ গুলো এড়িয়ে যেতে পারি।

একটি বিষয় লক্ষণীয়, যদি ইটারেটিভ ন্যাপস্যাক ফিগার টির দিকে তাকান তাহলে দেখতে পারবেন আসলে, টেবিল টি তে আমার বর্তমান পণ্যের রো এবং তার আগের রো টি ব্যবহার হচ্ছে শুধু। তাহলে কি N টি রো না নিয়ে শুধু ২টি রো দিয়েই কাজ করতে পারব? উত্তর হচ্ছে, হ্যা পারব। আর এতে আমাদের মেমোরি অনেক বেচে যাচ্ছে। নিচে ফাংশন টি দিয়ে দিলাম তবে কোন ব্যাখ্যা দিলাম না।

const int N = 100; int Weight[N+1], Profit[N+1]; int dp[2][N+1]; int n, Cap; int KnapSack() {   for (int i = 1;i <= n;i++) {     for (int j = 1;j <= Cap;j++) {       int WithoutCurProfit = 0;       int WithCurProfit = 0;       int wgt = Weight[i-1];       if (i%2 == 0) {         WithoutCurProfit = dp[1][j];         if (j-wgt >= 0)           WithCurProfit = dp[1][j-wgt] + Profit[i-1];         dp[0][j] = max(WithoutCurProfit, WithCurProfit);       } else {         WithoutCurProfit = dp[0][j];         if (j-wgt >= 0)           WithCurProfit = dp[0][j-wgt] + Profit[i-1];         dp[1][j] = max(WithoutCurProfit, WithCurProfit);       }     }   }   return max(dp[0][Cap], dp[1][Cap]); }

এই বিষয়ে আরো টিউটোরিয়াল। 
টিউটোরিয়াল ১
টিউটোরিয়াল ২

প্র্যাক্টিস প্রবলেমঃ
Gambling (Greedy)
The Knapsack Problem (DP)