ফ্রাকশনাল ন‍্যাপস‍্যাক ( ব্রুটফোর্স মেথড )

মনে করুন আপনার কাছে বেশ কয়েকদিন ধরে কোনো টাকা পয়সা নেই (মাসের শেষের দিক ) ! এদিকে আপনার বন্ধুর আবার টাকা পয়সার অভাব নেই (বন্ধুর বাপের অনেক  টাকা :P ) । আপনি আপনার বন্ধুর কাছে টাকা ধার চাইলেন আর সে কিনা ঘাড় বাঁকা করে চলে গেলো । আপনারতো রাগ উঠে গেলো .. !! রেগেমেগে আপনি সিদ্ধান্ত নিলেন কোনো এক শপিংমলে চুরি করবেন। যেমনি বলা অমনি কাজ , আপনি করলেন কি রাতের বেলা একটা ব্যাগ নিয়ে  শপিংমলে ঢুকে গেলেন । ( সি সি ক্যামেরা নাই :P ) ।

গিয়ে দেখলেন আপনার আগেই অন্য একটা চোর সম্পূর্ণ কেনা যায় এমন ((টুথপেস্ট,ব্রাশ,শেম্পু,সাবান,নুডলস ইত্যাদি ইত্যাদি :D :D ) সব জিনিস  চুরি  করে নিয়ে গেছে । আপনার ভাগ্যে আছে  (ডাল,ময়দা,আলু,পটোল ইত্যাদি ইত্যাদি ) | মনে করুন :

৫ কেজি ডাল ৬০০ টাকা 

৭  কেজি ময়দা ৭০০ টাকা

৬ কেজি আলু ২৪০ টাকা

৯ কেজি পটল ২৭০ টাকা

কিন্তু সমস্যাটা তৈরী হলো এখন। আপনার ব্যাগের  লিমিট ১৫ কেজি।সুতরাং আপনি চাচ্ছেন  এমন কিছু জিনিস নিতে যাতে আপনার বাগটিও খালি না থেকে এবং জিনিসগুলোর দামও যাতে বেশি থাকে । এখানে আপনি চাইলে কোনো একটি জিনিস সম্পূর্ণও নিতে পারেন আবার চাইলে অর্ধেক বা আপনার প্রয়োজন মত নিতে পারেন কিন্তু আপনাকে খেয়াল রাখতে হবে যাতে ব্যাগ ভরার সাথে সাথে আপনার প্রফিটও সর্বোচ্চ হয় । আর এটাকেই বলা হয় ফ্রাকশনাল ন‍্যাপস‍্যাক ! 


আপনি যদি ৯ কেজি পটল আর ৬ কেজি আলু কিনে ব্যাগ ভরে ফেলেন তবে তা অনেক বোকামির কাজ হবে কেননা এখানে আপনার প্রফিট বাড়ানোর সুযোগ ছিল । আপনি চাইলেই (৪ কেজি ডাল , ৫ কেজি ময়দা , ৩ কেজি আলু , ৩ কেজি পটল )  অথবা ( ৫ কেজি ডাল ৬ কেজি ময়দা , ২ কেজি আলু , ২ কিজি পটল ) অথবা অন্য কোনোভাবে ১৫ কেজি মিলিয়ে প্রফিট বাড়াতে পারতেন । অর্থাৎ জিনিসগুলো আপনাকে এমনভাবে নিতে হবে যাতে আপনার প্রফিট সর্বোচ্চ হয় এবং আপনার ব্যাগ ও পরিপূর্ণ হয় :D :P 


সমস্যাটা কিভাবে সমাধান করা যায় তা নিয়ে একটু চিন্তা করি। একটু খেয়াল করলে দেখবেন আপনি  যদি প্রত্যেকটির এককমূল্য ( ১ কেজির দাম) বের করেন এবং যার দাম বেশি সেটা আগে ব্যাগ এ ভরাতে থাকেন তাহলে সর্বোচ্চ প্রফিট করতে পারছেন । প্রয়োজনে বিভিন্ন রকম উদাহরণ নিয়ে খাতায় আঁকিবুকি শুরু করে দিতে পারেন| আপাতত উপরের উদাহরণের কোথায় যদি আমরা চিন্তা করি সেখানে দেখতে পাবো ,

১ কেজি ডাল ১২০ টাকা 

১  কেজি ময়দা ১০০ টাকা

১ কেজি আলু ৪০ টাকা

১ কেজি পটল ৩০  টাকা

এখানে ডালের দাম সর্বোচ্চ সুতরাং প্রথমে আপনি ডাল নেবেন । এখানে ডাল আছে ৫ কেজি আর আমাদের ব্যাগ এর লিমিট ১৫ কেজি সুতরাং আপনি ডাল ৫ কিজি পুরোটাই নিতে পারেন !তাহলে ডাল নেয়ার পর আপনার ব্যাগ এর লিমিট দাড়াল ১৫-৫=১০ কেজি। এরপরের সর্বোচ্চ মূল্য ময়দা। প্রতি কেজি ১০০ টাকা | এখানে ময়দা আছে ৭ কেজি যা আমরা পুরোটাই নিতে পারবেন কেননা ব্যাগ এর লিমিট এখন ও ১০ কেজি | তাহলে ময়দা নেয়ার পর আপনার ব্যাগ এর লিমিট দাড়াল ১০-৭=৩ কেজি| এরপরের সর্বোচ্চ মূল্য প্রতি কেজি আলু ৪০ টাকা| এখানে লক্ষণীয় বিষয় হলো আপনার  ব্যাগ এর লিমিট ৩ কেজি আর আলু আছে ৫ কেজি আপনি চাইলেই ৫ কেজি আলু নিতে পারবেন না কারণ আপনার  ব্যাগ এর লিমিট ৩ কেজি |সুতরাং আপনি  এখানে ৩কেজির বেশি আলু নিতে পারবেননা| আলু নেয়ার পর আপনার ব্যাগ এর লিমিট দাড়াল ৩-৩=০ কেজি| যেহেতু আপনার ব্যাগ পরিপপূর্ণ সেহেতু বাদবাকি পণ্যগুলো আপনি আর নিতে পারবেননা| তাহলে আপনার সর্বমোট প্রফিট দাঁড়ালো ((১২০*৫)+(১০০*৭)+(৪০*৩))=১৪২০ টাকা  ( সাধ্যের মধ্যে সর্বোচ্চ প্রফিট :P :D ) |





এবার কিভাবে এটাকে কোডে ইমপ্লিমেন্ট করতে হয় সেটা দেখবো | এখানে যেহেতু পণ্যের দাম,ওজন এবং প্রতি কেজি পণ্যের দামকে একসাথে নিয়ে কাজ করতে হবে সুতরাং এগুলোকে স্ট্রাক্ট এ ডিক্লেয়ার করতে পারি |  এরপর পণ্যের সংখ্যা অনুসারে একটি এরে ডিক্লেয়ার করতে হবে |তাহলে ভেরিয়েবল ডিক্লেয়ারের কোডটা দাড়াবে এমন -

struct item{ double profit,weight,cost_per_unit; }; int main() { item ar[100]; //Assume that number of product is less than 101 int number_of_products; double capacity; }

এবার আমরা কোডের ধাপগুলো আর একবার ঝালাই করে নেই |


১| ইনপুট
২|  প্রতিবার ইনপুটের সাথে সাথে  cost_per_unit  নির্ণয় করি
৩| এর ভিত্তিতে ডিসেন্ডিং অর্ডার এ এরেকে সর্ট করি
৪| যতক্ষণ না  ব্যাগ পূর্ণ না হয় অথবা এরের n টি এলিমেন্ট চেক না হয় ততক্ষন *প্রয়োজন অনুসারে           ব্যাগ পূর্ণ করি এবং প্রফিট যোগ করি | ( *  যদি এরের আই তম পজিশনের পণ্যের ওজন প্রয়োজনের                       তুলনায় (কম বা সমান হয়) অথবা  (বেশি হয় ))



ধাপ ১ ও ২ :

cin>>number_of_products>>capacity; for(int i=0;i<n;i++) { cin>>ar[i].profit>>ar[i].weight; ar[i].cost_per_unit=(ar[i].profit/ar[i].weight); }

মনে করুন শপিংমলে ৭ টি পণ্য  ছিল যাদের মূল্য এবং ওজন যথাক্রমে,

মূল্য -----------------ওজন

10                            2
6                              3
15                            5
7                              7
6                              1
20                            4
3                              1



তাহলে এরের ভিতর এদের অবস্থান হবে এমন-


Index-------cost---------weight-------cost_per_unit

1                 10                2                        5

2                  6                 3                        2

3                  15               5                        3

4                   7                7                        1

5                   6                1                        6

6                   20              4                        5

7                    3               1                        3



ধাপ ৩  :

for(int i=0;i<number_of_products;i++) { for(int j=0;j<number_of_products;j++) { if(ar[j].cost_per_unit<ar[j+1].cost_per_unit) swap(ar[j],ar[j+1]); } }

After sorting (step 3) we get the array ,



Index-------cost---------weight-------cost_per_unit

1                  6                 1                        6

2                  10               2                        5

3                  20               4                        5

4                   15               5                       3

5                   3                1                        3

6                   6                3                        2

7                    7               7                        1






ধাপ ৪  :

double total_profit=0,take=0; for(int i=0;i<number_of_products;i++) { double need=(m-take); if(ar[i].weight<=need) { take+=ar[i].weight; total_profit+=ar[i].profit; } else { take+=need; total_profit+=(need*ar[i].cost_per_unit); } }



আশারাখি পুরো বিষয়টা বুঝতে পেরেছেন | এখানে ব্রুটফোর্স মেথড অবলম্বনে কোড করা আছে ভবিষ্যতে আরো ইফিসিয়েন্ট ওয়েতে কিভাবে করা যায় তা আলোচনা করবো | ধন্যবাদ |