C++ এ বিন প্যাকিং সমস্যা (ব্যবহৃত বিনের সংখ্যা কম করুন)?

বিভিন্ন ওজনের প্রদত্ত m উপাদানের ক্ষেত্রে এবং প্রতিটি C ধারণক্ষমতার বিনের ক্ষেত্রে, প্রতিটি উপাদানকে একটি বিনে বরাদ্দ করুন যাতে মোট বাস্তবায়িত বিনের সংখ্যা কম হয়। অনুমান করা উচিত যে সমস্ত উপাদানের ওজন বিন ক্ষমতার চেয়ে কম।

অ্যাপ্লিকেশানগুলি

একাধিক ডিস্কে ডেটা স্থাপন করা।
ট্রাকের মত কন্টেইনার লোড হচ্ছে।
নির্দিষ্ট দৈর্ঘ্যের রেডিও/টিভি স্টেশন বিরতিতে বিজ্ঞাপন প্যাক করা।
কাজের সময়সূচী।

উদাহরণ

ইনপুট:ওজন[] ={4, 1, 8, 1, 4, 2} বিন ক্যাপাসিটি c =10 আউটপুট:2 সমস্ত উপাদানকে মিটমাট করার জন্য আমাদের কমপক্ষে 2 টি বিন প্রয়োজন প্রথম বিনটি {4, 4, 2} এবং দ্বিতীয় বিন নিয়ে গঠিত {8, 2}

লোয়ার বাউন্ড

আমরা সর্বদা ceil() ফাংশন ব্যবহার করে প্রয়োজনীয় ন্যূনতম সংখ্যক বিনের উপর একটি নিম্ন সীমা গণনা করতে পারি। নিম্ন সীমা নিচে দেওয়া যেতে পারে −

ন্যূনতম সংখ্যা>=সিল (মোট ওজন) / (বিনের ক্ষমতা))
উপরের উদাহরণে, প্রথম উদাহরণের জন্য নিম্ন সীমা হল “ceil(4 + 1 + 8 + 2 + 4 + 1)/10” =2
এই সমস্যার জন্য নিম্নলিখিত আনুমানিক অ্যালগরিদমগুলি প্রয়োগ করা হয়েছে৷
৷

অনলাইন অ্যালগরিদম

এই অ্যালগরিদমগুলি বিন প্যাকিং সমস্যাগুলির জন্য প্রয়োগ করা হয় যেখানে উপাদানগুলি একবারে আসে (অজানা ক্রমে), পরবর্তী উপাদানগুলি বিবেচনা করার আগে প্রতিটিকে অবশ্যই একটি বিনের মধ্যে রাখতে হবে৷

পরবর্তী ফিট -

পরবর্তী উপাদান প্রক্রিয়াকরণ করার সময়, এটি শেষ উপাদান হিসাবে একই বিনে ফিট কিনা তা যাচাই করুন। একটি নতুন বিন প্রয়োগ করুন শুধুমাত্র যদি এটি না করে।

এই অ্যালগরিদমের জন্য C++ অ্যাপ্লিকেশান নিচে দেওয়া হল।

পরবর্তী ফিট অ্যালগরিদম বাস্তবায়নের জন্য প্রয়োজনীয় বিনের সংখ্যা গণনা করার জন্য C++ প্রোগ্রাম। [], int m, int C){ // ফলাফল (বিনের সংখ্যা) এবং বর্তমান বিনের অবশিষ্ট ক্ষমতা আরম্ভ করা হয়। int res =0, bin_rem =C; // (int i =0; i bin_rem) { res++; // একটি নতুন বিন ব্যবহার করুন bin_rem =C - weight1[i]; } অন্য bin_rem -=weight1[i]; } রিটার্ন রিটার্ন;}// ড্রাইভার প্রোগ্রামিং মেইন(){ int weight1[] ={ 3, 6, 5, 8, 2, 4, 9}; int C =10; int m =sizeof(weight1) / sizeof(weight1[0]); cout<<"Next Fit এ প্রয়োজনীয় বিনের সংখ্যা :" <

আউটপুট

পরবর্তী ফিটে প্রয়োজনীয় বিনের সংখ্যা :4

নেক্সট ফিটকে একটি সাধারণ অ্যালগরিদম হিসাবে বিবেচনা করা হয়। m উপাদানগুলি প্রক্রিয়া করার জন্য এটির শুধুমাত্র O(m) সময় এবং O(1) অতিরিক্ত স্থান প্রয়োজন৷

প্রথম ফিট-

পরবর্তী উপাদানটি প্রক্রিয়া করার সময়, পূর্ববর্তী বিনগুলিকে ক্রমানুসারে পরীক্ষা করুন বা স্ক্যান করুন এবং উপাদানটিকে মানানসই প্রথম বিনে রাখুন৷ যদি উপাদানটি সেই সময়ে বিদ্যমান বিনে ফিট না হয় তবে আমরা শুধুমাত্র একটি নতুন বিন শুরু করি৷

উদাহরণ

// ফার্স্ট ফিট অ্যালগরিদম বাস্তবায়নের জন্য প্রয়োজনীয় বিনের সংখ্যা খুঁজে পেতে C++ প্রোগ্রাম। #include নেমস্পেস std ব্যবহার করে;// ফার্স্ট ফিট অনলাইন অ্যালগরিদমিন্ট ফার্স্টফিট (int weight1) বাস্তবায়নের জন্য আমাদের প্রয়োজনীয় বিনের সংখ্যা ফেরত দিতে হবে [], int m, int C){ // আমাদের ফলাফল শুরু করতে হবে (বিনের সংখ্যা) int res =0; // বিনে অবশিষ্ট স্থান সংরক্ষণ করার জন্য আমাদের একটি অ্যারে তৈরি করতে হবে সেখানে সর্বাধিক n bins int bin_rem[m] হতে পারে; // আমাদের (int i =0; i =weight1[i]) { bin_rem[j] =bin_rem[j] - weight1[i]; বিরতি } } // যদি কোন বিন ওজন1[i] মিটমাট করতে না পারে যদি (j ==res) { bin_rem[res] =C - weight1[i]; res++; } } রিটার্ন রেস;}// ড্রাইভার প্রোগ্রামিং মেইন(){ int weight1[] ={ 2, 5, 4, 7, 1, 3, 8 }; int C =10; int m =sizeof(weight1) / sizeof(weight1[0]); cout<<"প্রথম ফিটে প্রয়োজনীয় বিনের সংখ্যা :" < আউটপুট
 প্রথম ফিটে প্রয়োজনীয় বিনের সংখ্যা :4
 
 ফার্স্ট ফিটের উপরোক্ত প্রয়োগটি O(m2) সময় ব্যয় করে, তবে ফার্স্ট ফিটটি O(m log m) সময়ে ব্যবহার করা যেতে পারে স্ব-ভারসাম্যপূর্ণ বাইনারি অনুসন্ধান ট্রিগুলি বাস্তবায়নের জন্য৷
 
 সেরা ফিট -
 
 ধারণাটি হল পরবর্তী আইটেমটিকে সবচেয়ে শক্ত অবস্থানে রাখা। তার মানে এটিকে বিনে রাখুন যাতে অন্তত খালি জায়গা থাকে।
 উদাহরণ
 সেরা ফিট অ্যালগরিদম বাস্তবায়নের জন্য প্রয়োজনীয় বিনের সংখ্যা গণনা করার জন্য C++ প্রোগ্রাম। [], int m, int C){ // আমাদের ফলাফল শুরু করতে হবে (বিনের সংখ্যা) int res =0; // বিনে অবশিষ্ট স্থান সংরক্ষণ করার জন্য আমাদের একটি অ্যারে তৈরি করতে হবে সেখানে সর্বাধিক n bins int bin_rem[m] হতে পারে; // একের পর এক উপাদান রাখুন (int i =0; i =weight1[i] &&bin_rem[j] - weight1[i]  আউটপুট
 বেস্ট ফিটে প্রয়োজনীয় বিনের সংখ্যা :4
 
 সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি বাস্তবায়নের জন্য O(m log m) সময়েও সেরা ফিট প্রয়োগ করা যেতে পারে।
 অফলাইন অ্যালগরিদম
 
 অফলাইন সংস্করণের ক্ষেত্রে, আমাদের কাছে সমস্ত উপাদানই রয়েছে। অনলাইন অ্যালগরিদমের একটি সমস্যা হল যে বড় উপাদানগুলি প্যাক করা কঠিন, বিশেষ করে যদি সেগুলি অনুক্রমের দেরিতে ঘটে। আমরা ইনপুট সিকোয়েন্স বাছাই করে এবং বড় উপাদানগুলিকে প্রথমে রেখে এটি কাটিয়ে উঠতে পারি।
 
 প্রথম ফিট হ্রাস -
 উদাহরণ
 // সি++ প্রোগ্রাম ফার্স্ট ফিট ক্রমবর্ধমান অ্যালগরিদম বাস্তবায়নের জন্য বিনের সংখ্যা সনাক্ত করতে প্রয়োজন। #include নেমস্পেস std ব্যবহার করে;/* আমরা উপরের থেকে firstFit() কপি করি */int firstFit(int weight1[] , int m, int C){ // আমাদের ফলাফল শুরু করতে হবে (বিনের সংখ্যা) int res =0; // বিনে অবশিষ্ট স্থান সংরক্ষণ করার জন্য আমাদের একটি অ্যারে তৈরি করতে হবে সেখানে সর্বাধিক n bins int bin_rem[m] হতে পারে; // আমাদের (int i =0; i =weight1[i]) { bin_rem[j] =bin_rem[j] - weight1[i]; বিরতি } } // যদি কোন বিন ওজন1[i] মিটমাট করতে না পারে যদি (j ==res) { bin_rem[res] =C - weight1[i]; res++; } }রিটার্ন রেস;}// প্রথম ফিট কমানো অফলাইন অ্যালগরিদমিন্ট ফার্স্টফিটডেক(int weight1[], int m, int C){ // প্রথমে আমরা সমস্ত ওজনকে হ্রাসকারী ক্রম অনুসারে সাজাই(ওজন1) , weight1 + m, std::grater()); // এখন আমরা সাজানো আইটেম রিটার্নের জন্য ফার্স্ট ফিট বলি firstFit(weight1, m, C);}// Driver programint main(){ int weight1[] ={ 2, 5, 4, 7, 1, 3, 8 }; int C =10; int m =sizeof(weight1) / sizeof(weight1[0]); cout<<"প্রথম ফিটে প্রয়োজনীয় বিনের সংখ্যা " <<"হ্রাস হচ্ছে :" < আউটপুট
 প্রথম ফিট কমতে প্রয়োজনীয় বিনের সংখ্যা :3
 
 প্রথম ফিট কমানো নমুনা ইনপুটের জন্য সর্বোত্তম ফলাফল তৈরি করে কারণ উপাদানগুলি প্রথমে সাজানো হয়৷
 
 ফার্স্ট ফিট ডিক্রিজিং O(m log m) সময়েও ব্যবহার করা যেতে পারে সেল্ফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি বাস্তবায়নের জন্য।