০/১ ন্যাপসাক (0/1 knapsack)

আলীবাবা চিচিংফাক বলে ঢুকে পড়েছে ডাকাতদের গুহায়, তার সামনে চোখ ধাধানো মনী-মুক্তা,স্বর্ণ,হীরা...
তার চোখ তো ছানাবড়া, সে সব গুলো তার ব্যাগে ঢুকানো শুরু করল,আজ সে সব কিছু নিয়েই ছাড়বে। কিন্তু তখনই তার মনে পড়ল, সে মাত্র ১০ কেজি জিনিস নিতে পারবে।এর বেশি নিলে তার ব্যাগটা ছিঁড়ে যাবে, তাই সে চাইছে সে সব জিনিস নিতে, যেগুলো নিলে তার সবচেয়ে বেশি লাভ হবে।
সব জিনিস ছোট ছোট বাক্সে রাখা আছে, এই বাক্স ভেঙ্গে নেয়ার মত টাইম তার নাই। তাই কোন কিছু নিতে হলে হয় তাকে সম্পুর্ণ্টাই নিতে হবে নতুবা নিতে পারবে না, যেমন স্বর্ণ যে বাক্সে আছে, তার ওজন ৫ কেজি, তাই তাকে স্বর্ণ নিতে হলে ৫ কেজিই নিতে হবে।

তার সব কিছুর মার্কেট প্রাইজ জানা(চুরি করতে এসেছে, দাম না জানলে কি হয়!!)।কিন্তু সে কিছুতেই হিসেব করতে পারছে না, কি কি নিলে তার সবচেয়ে বেশি লাভ হবে। সে একটা চার্ট বানিয়ে ফেললঃ

জিনিসের নাম

ওজন(কেজি)

দাম(একক)

স্বর্ণ

হীরা

১৪

মুক্তা

মুর্তি

ভাল হত, যদি সে ৭ কেজি হীরা নিয়ে তারপর ৩ কেজি স্বর্ণ নিতে পারত, কিন্তু স্বর্ণ নিতে হলে তাকে পুরো ৫ কেজিই নিতে হবে, তখন ৭+৫=১২,যা তার ব্যাগের ধারণক্ষমতার বাইরে।
এটাই হল ০/১ ন্যাপসাক(
0/1 knapsack)
০/১ মানে হল না নিলে কিছুই নেয়া যাবে না, আর নিলে পুরোটাই নিতে হবে।
সোজা কথায়
0/1 knapsack মানে হলঃ আমাকে ব্যাগের সাইজ m দেয়া আছে, আর n সংখ্যক জিনিসের দাম ও ওজন দেয়া আছে, আমাকে এমন ভাবে জিনিস নিতে হবে,যাতে করে তাদের ওজন m এর বেশি না হয় আর দাম সবচেয়ে বেশি হয়।


এবার,কয়েন চেঞ্জ(coin change) এর এলগরিদমটা দেখে আসুন, তারপর নিচের অংশ পড়ুন,এতে বুঝতে সুবিধা হবে algorithm coin change
কয়েন চেঞ্জ এ একটা কয়েন অনেকবার নিলেও প্রবলেম ছিল না, কিন্তু এখানে একটা জিনিস একাধিকবার নেয়া যাবে না। এজন্য
2d array লাগবে।
ধরি,জিনিসগুলোর দাম আছে values[] array
তে, weight আছে weight[] array তে, আর কয়টা জিনিস আছে, তা আছে item variable এ,ব্যাগের ওজন দেয়া আছে knapsack_weight variable এ।
ধরি,যে
2d এরেটা লাগবে, তার নাম profit[][]. Profit[i][j] মানে হল, i তম জিনিস পর্যন্ত j ওজন পর্যন্ত বেস্ট solution কোনটা, মানে মোট কত কেজি জিনিস আলীবাবা তার ব্যাগে নিতে পারব।যেমনঃprofit[2][5] মানে হল, প্রথম ২ টা জিনিস নিয়ে এখন পর্যন্ত চেক করা হয়েছে, আর ব্যাগের ওজন ৫ হলে সে কত কেজি পর্যন্ত নিলে সবচেয়ে বেশি দাম পাবে।তাই profit[item][knapsack_weight] এ থাকবে, আলীবাবা তার ব্যাগে করে সর্বোচ্চ কত ওজনের জিনিস নিতে পারবে,যাতে লাভ সবচেয়ে বেশি হয়।
profit[i][0]=0,কারণ arrayএর ২য় element দারা বোঝাচ্ছে, মোত কত ওজন পর্জন্ত চেক করা হয়েছে।এখানে ২য় element 0,তার মানে এখনো কোন জিনিস নেয়া হয় নি, তাই ব্যাগে আছে ০ কেজি জিনিস।
আবার,
profit[0][w] = 0. কারণ, array এর ১ম উপাদান দিয়ে বোঝাচ্ছে, কয়টা জিনিস চেক করা হয়েছে,এখানে
প্রথম
element 0. মানে কোন element নেয়া হয় নি।তাই ব্যাগেও কিছু নাই।
এখন আমার
profit[][]
এরেটা এরকমঃ

0

0

0

0

0

0

0

0

0

0

0

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 


এখন খুব ভালমত খেয়াল করুনঃ আমরা সম্পুর্ণ ব্যাগের ধারণক্ষমতা ১০ কেজি ধরে নিয়ে কাজ করা শুরু করব না, বরং আমরা প্রথম
element(এখানে স্বর্ণ,হীরা... এগুলো কে একেকটা element বলছি) টা নিব আর প্রথমে ধরব ব্যাগের ধারণক্ষমতা ১ কেজি। তখন সবচেয়ে বেশি লাভ কত, তা বের করব। এই মান ব্যবহার করে বের করব, ব্যাগের ধারণক্ষমতা ২ কেজি হলে সবচেয়ে বেশি লাভ কত হবে। এই মান ব্যাবহার করে বের করব, ব্যাগের ধারণক্ষমতা ৩ কেজি হলে সবচেয়ে বেশি লাভ কত হবে... এভাবে একসময় ১ম element এর জন্য(আমাদের উদাহরণে স্বর্ণ) ব্যাগের ধারণক্ষমতা ১০ কেজি হলে সবচেয়ে বেশি লাভ কত হবে,তা বের হবে।
তারপর ২য়
element নিয়ে কাজ করব।এবার আবারো ব্যাগের ধারণক্ষমতা ১ কেজি হতে ১০ কেজি পর্যন্ত যাব, আর চেক করব তখন এই ২য় element টা নিলে লাভ বেশি, নাকি না নিলে লাভ বেশি। যেমনঃ ব্যাগের ধারণক্ষমতা যখন ২ কেজি, তখন ১ম element কে নিয়ে সবচেয়ে বেশি লাভ কত,তা আগেই বের করেছি,এখন দেখি, এই ২ কেজির জন্য ২য় element টা নিলে যে নতুন লাভ পাব, সেটা ভাল, নাকি ১ম elment পর্যন্ত যে সবচেয়ে বেশি লাভ আছে সেটা ভাল।
এর জন্য কয়েন চেঞ্জ এর মতো ২ টা লুপ লাগবে

for(i=1;i<=items;i++){

                                for(w=1;w<=knapsack_weight;w++){


কিছু কি বোঝা গেল? না বোঝা গেলেও সমস্যা নাই,নিচের উদাহরণ দেখলেই আশা করি বোঝা যাবেঃ
১ম
element নিয়ে ব্যাগের ওজন ৫ কেজি পর্জন্ত সবচেয়ে বেশি লাভ কত তা আছে profit[1][5] এ, যখন ২য় elemnt নিয়ে ৫ কেজির জন্য কাজ করব, তখন আগে দেখতে হবে, ১ম element এর জন্য ৫ কেজি তে কি solution ছিল। আর তা পাব profit[2-1][5] এ, এই 2 যদি i variable এ থাকে, আর ৫ কেজি w variable এ থাকে, তবে profit[i-1][w].
/*ধরি,
I তম element নিয়ে w তম weight এর জন্য কাজ করছি। I তম element না নিলে যে সবচেয়ে বেশি লাভ, তা আছে profit[i-1][w] তে। i-1 কেন? কারণ আগেই বলেছি, এই 2d array এর ১ম index দারা বোঝাচ্ছে, কোন element নিয়ে কাজ করছি। i-1 মানে, i এর আগের সব element নিয়ে কাজ করেছি। আর ২য় element w দিয়ে বোঝাচ্ছে, যখন ব্যাগের ধারণক্ষমতা w, তখন কি হবে তা ভাবছি।*/
I তম element আর w weight এর জন্য সবচেয়ে বেশি লাভ কত, তা চেক করব এভাবেঃ
profit[i][w] = max(profit[i-1][w],profit[i-1][w-weight[i]]+values[i])
profit[i-1][w-weight[i]]+values[i] এর মানে কি? কয়েন চেঞ্জ এর মতোই, যখন ২ টাকার কয়েন দিয়ে ৪ টাকা বানাতে চাচ্ছিলাম ,তখন হেল্প নিচ্ছিলাম ৪-২=২ টাকার। এখানেও, এখন কাজ করছি w নিয়ে, তাই যদি weight[i] নিতে চাই, তখন হেল্প নিতে হবে w-weight[i] এর। যেমনঃi=2,w=10,weight[i]=7 হলে, আমার দেখতে হবে profit[2-1][10-7]+values[2] বড়, নাকি profit[2-1][10] বড়।
এটা সি তে লিখলে এরকম হবেঃ

if(profit[i-1][w]>profit[i-1][w-weight[i]]+values[i]){

                                                                                profit[i][w] = profit[i-1][w];

                                                                }

                                                                else{

                                                                                profit[i][w] = profit[i-1][w-weight[i]]+values[i];

                                                                                track[profit[i][w]] = i;

                                                                }

Track array টা কি কাজ করছে, তা পরে বলছি।      

0

0

0

0

0

0

0

0

0

0

0

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

যখন ১ম element মানে স্বর্ণ নিয়ে কাজ করছিঃ স্বর্নের ওজন ৫ কেজি, দাম ৬ একক।মানে i=1,values[i]=6,weight[i]=5,তাই ২য় লুপে যতক্ষন w<4, ততক্ষন স্বর্ণ ব্যাগে নিতে পারব না, তাই সরাসরি আগের ধাপের মান গুলো বসে যাবে, মানে profit[1][1] এ বসবে profit[0][1] এর মান, profit[1][2] তে বসবে profit[0][2]এর মান, এভাবে profit[1][4] পর্যন্ত বসবে।যখন w = 5, তখন দেখি, স্বর্ণ নিলে লাভ বেশি,নাকি না নিলে লাভ বেশি।এজন্য উপরের সুত্র ব্যাবহার করি।
profit[i-1][w]= profit[1-1][5]=0, profit[i-1][w-weight[i]]+values[i]=profit[1-1][5-5]+6=profit[0][0]+6=0+6=6

এখন,৬>০, তাই profit[1][5]=6 হবে. এভাবে w=10 পর্যন্ত হিসাব করার পরে profit array
টা দাঁড়ায় এরকমঃ
      

0

0

0

0

0

0

0

0

0

0

0

0

6

6

6

6

6

6

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 

0

 

 

 

 

 

 

 

 

 

 


এবার ২য় element নিয়ে কাজ করার সময়ঃ i=2, weight[i]=7, values[i]=14,
যখন w=7, তখন, profit[i-1][w]=profit[1][7]=6, profit[i-1][w-weight[i]]+values[i]=profit[1][0]+14=14
14>6,
তাই, profit[2][7] 14 বসবে।
এভাবে সবাইকে নিয়ে কাজ করার পরে
profit[5][10] তে থাকবে, আলীবাবা সবচেয়ে লাভ করে মোট কত কেজি জিনিস নিতে পারবে।যেহেতু, items=5, knapsack_weight=10,
তাই উত্তর পাওয়া যাবে profit[items][knapsack_weight] এ।

for(i=1;i<=items;i++){

                                for(w=1;w<=knapsack_weight;w++){

                                                if(weight[i]>w){

                                                                profit[i][w] = profit[i-1][w];

                                                }

                                                else{

                                                                if(profit[i-1][w]>profit[i-1][w-weight[i]]+values[i]){

                                                                                profit[i][w] = profit[i-1][w];

                                                                }

                                                                else{

                                                                                profit[i][w] = profit[i-1][w-weight[i]]+values[i];

                                                                                track[profit[i][w]] = i;

                                                                }

                                                }

                                }

                }


কোন কোন জিনিস নিতে হবেঃ এ জন্য আছে track[] array টি।উপরে else এর মধ্যে লিখলাম,track[profit[i][w]]=i
মানে, যে লাভ হল, সেটা কোন element দিয়ে হল। যেমন আমাদের উদাহরণে, স্বর্ণের জন্য হিসাব করা শেষে track array
টা অবস্থা দাঁড়াবে এ রকমঃ
             track:

0

0

0

0

0

1

1

1

1

1

1

(এই হিসেবটা কষ্ট করে নিজে করে নিবেন ,আমি লিখতে লিখতে ক্লান্ত, আপনারাও মনে হয় পড়তে পড়তে ক্লান্ত L)
এখন আমি দেখতে পাচ্ছি,
profit[1][10]=6, আর আমি জানতে চাই কোন কোন element নিয়ে এই লাভ হয়েছে, তাহলে কি করব?কোন লাভের জন্য কোন element নিচ্ছি, তা আছে track array তে। track[profit[1][10]]=track[6]=1,
এই
1 মানে,আমাকে ১ম element টা নিতে হয়েছে। এই profit[1][10] যে ৬, তা আমি পেয়েছিলাম কিভাবে? এটা পেয়েছিলাম,এর আগ পর্যন্ত যত লাভ হয়েছিল, তার সাথে এই ১ম element এর দাম, মানে value[1] যোগ করে।তাই, এর আগের element কোনটা, সেটা পেতে হলে এই profit[1][10] হতে value[1]=6 বিয়োগ করি।যে মান পাব,track[] array এর সে position এ গেলেই পাব, এর আগের element কোনটা নিতে হয়েছিল। এক্ষেত্রে profit[1][10]-values[1] = 0
তার মানে,track[0] তে আছে, এর আগে কোন element নিতে হয়েছিল। track[0] = 0,তার মানে এর আগে কোন element নেই নাই। তাই যখন track[i]=0 পাব, তখন বুঝব, আর কোন element নেয়া বাকি নাই।
দেখাই যাচ্ছে, যে
element টা সবার লাস্টে নিয়েছিলাম, সেটা সবার আগে পেলাম, কিন্তু আমি চাই আগের জিনিস আগে পেতে।এ জন্য stack ব্যাবহার করতে হবে। স্ট্যাক কি? টেবিলে যখন একটা প্লেট এর উপরে আরেকটা প্লেট রাখি, তখন যে প্লেটটা সবার পরে রাখি, সে সবার উপরে থাকে। মানে যে লাস্টে এল, সে সবার আগে। এটাই হল স্ট্যাক।
এখন সি++ এ
stl এর মধ্যে স্ট্যাক আছে, আপনি চাইলেই এটা ব্যাবহার করতে পারেন, আমি এটাই ব্যাবহার করব।
ধরুণ আমি
st নামে একটা স্ট্যাক তৈরি করব, এজন্য লিখতে হবে stack<int> st;
আর ভাল কথা, এজন্য header file include করার জায়গায় লিখে আসতে হবে, #include<stack>
stl গুলো থাকে std namespace এ। তাই এটা use করতে হবে। এজন্য লিখি,using namespace std;
আর এটা লিখতে হবে সব header file include করার পরে।
using namespace std;
use করলে .h লিখা যায় না, আর সি এর যত header file আছে, তাদের include করার সময় তাদের নামের আগে c লিখতে হয়, যেমন stdio এর বদলে লিখব cstdio

#include<iostream>

#include<cstdio>

#include<stack>

 
আমি যখনই কোন element পাব, তখনই তা স্ট্যাকে ভরতে হবে, এজন্য আছে push function, আর স্ট্যাক হতে কোন কিছু read করার পরে তা মুছে ফেলার জন্য আছে pop function.
আর স্ট্যাকটা খালি কিনা,তা চেক করার জন্য লিখব,আছে empty function

i = profit[items][knapsack_weight];

     j = track[i];

     while(j!=0){

          st.push(values[j]);

          i = i - values[j];

          j=track[i];

          }

     while(!st.empty()){

          printf("%d ",st.top());

          st.pop();

     }

 আমার মূল কাজের জন্য প্রয়োজনীয় কোড এবার একসাথে দিলামঃ

scanf("%d %d",&knapsack_weight,&items);

for(i=0;i<=items;i++){

            profit[i][0] = 0;//no weight is taken, so no profit so far

      }

      for(w=0;w<=knapsack_weight;w++){

            profit[0][w] = 0;//no item is taken, so no profit so far.

      }

 

      for(i=1;i<=items;i++){

            for(w=1;w<=knapsack_weight;w++){

                  if(weight[i]>w){

                        profit[i][w] = profit[i-1][w];

                  }

                  else{

                        if(profit[i-1][w]>=profit[i-1][w-weight[i]]+values[i]){

                              profit[i][w] = profit[i-1][w];

                             

                        }

                        else{

                              profit[i][w] = profit[i-1][w-weight[i]]+values[i];

                              track[profit[i][w]] = i;

                        }

                  }

            }

      }

      //track the taken values

     

 

      i = profit[items][knapsack_weight];

      j = track[i];

      //for(j=track[knapsack_weight];j!=0;){

     

      while(j!=0){

            //i = track[j];

           

           

            st.push(values[j]);

            i = i - values[j];

            j=track[i];

            //j = j-values[j];

      }

      while(!st.empty()){

            printf("%d ",st.top());

            st.pop();

      }

      printf("sum:%d\n",profit[items][knapsack_weight]);

আমি এই tutorial লিখতে গিয়ে বুঝেছি, আসলে টিচারদের কি পরিমাণ কষ্ট করতে হয়।
আমি জানি না কতটুকু বুঝাতে পেরেছি, তবে আমি আমার স্বাধ্যমত চেষ্টা করেছি।
কেউ কোন ভুল পেলে বা কোন মতামত থাকলে জানাবেন,আমার ই-মেইল আড্রেসঃ
concept_right@yahoo.com
ধন্যবাদ সবাইকে।

ও আচ্ছা, এখন নিশ্চয়ই ভাবছেন আলীবাবার কি হল?এই আলীবাবা আধুনিককালের, তার সাথে ল্যাপটপ আছে, আর আছে ইন্টারনেট কানেকশান। সে এতক্ষনে মনে হয় এই সাইটে ঢুকে পড়েছে আর বুঝে ফেলেছে তাকে কি কি নিতে হবে(নাকি চুরি করতে হবে ;))।

এবার সলভ করে ফেলুনঃ

acm problem: 624,10130,562





Visitors:

Free Hit Counter

Comments