सी ++ में बिन पैकिंग समस्या (प्रयुक्त डिब्बे की संख्या कम करें)?

अलग-अलग भार के दिए गए m तत्वों और प्रत्येक क्षमता C के डिब्बे के मामले में, प्रत्येक तत्व को एक बिन में असाइन करें ताकि कुल कार्यान्वित डिब्बे की संख्या कम से कम हो। धारणा यह होनी चाहिए कि सभी तत्वों का भार बिन क्षमता से कम है।

अनुप्रयोग

• एकाधिक डिस्क पर डेटा रखना।

• ट्रक जैसे कंटेनर लोड हो रहे हैं।

• विज्ञापनों को निश्चित लंबाई के रेडियो/टीवी स्टेशन ब्रेक में पैक करना।

• जॉब शेड्यूलिंग।

उदाहरण

Input: weight[] = {4, 1, 8, 1, 4, 2}
Bin Capacity c = 10
Output: 2
We require at least 2 bins to accommodate all elements
First bin consists {4, 4, 2} and second bin {8, 2}

निचला बाउंड

हम हमेशा छत () फ़ंक्शन का उपयोग करके आवश्यक न्यूनतम संख्या में डिब्बे पर निचली सीमा की गणना कर सकते हैं। निचली सीमा नीचे दी जा सकती है -

• न्यूनतम संख्या वाले डिब्बे>=छत ((कुल वजन) / (बिन क्षमता))

• उपरोक्त उदाहरण में, पहले उदाहरण के लिए निचली सीमा "सील(4 + 1 + 8 + 2 + 4 + 1)/10" =2

  है

• इस समस्या के लिए निम्नलिखित अनुमानित एल्गोरिदम लागू किए गए हैं।

ऑनलाइन एल्गोरिदम

इन एल्गोरिदम को बिन पैकिंग समस्याओं के लिए कार्यान्वित किया जाता है जहां तत्व एक समय में (अज्ञात क्रम में) आते हैं, प्रत्येक को अगले तत्व पर विचार करने से पहले एक बिन में रखा जाना चाहिए।

अगला फ़िट -

अगले तत्व को संसाधित करते समय, सत्यापित करें कि क्या यह अंतिम तत्व के समान बिन में फिट बैठता है। एक नया बिन तभी लागू करें जब ऐसा न हो।

इस एल्गोरिथम के लिए निम्नलिखित C++ एप्लिकेशन है।

// C++ program to calculate number of bins required implementing next fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing next fit online algorithm
int nextFit(int weight1[], int m, int C){
   // Result (Count of bins) and remaining capacity in current bin are initialized.
   int res = 0, bin_rem = C;
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // If this element can't fit in current bin
      if (weight1[i] > bin_rem) {
         res++; // Use a new bin
         bin_rem = C - weight1[i];
      }
      else
      bin_rem -= weight1[i];
      }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 3, 6, 5, 8, 2, 4, 9 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in Next Fit : "
   <<nextFit(weight1, m, C);
   return 0;
}

आउटपुट

Number of bins required in Next Fit : 4

नेक्स्ट फिट को एक साधारण एल्गोरिथम के रूप में माना जाता है। इसे m तत्वों को संसाधित करने के लिए केवल O(m) समय और O(1) अतिरिक्त स्थान की आवश्यकता होती है।

पहली फ़िट—

अगले तत्व को संसाधित करते समय, पिछले डिब्बे को क्रम में जांचें या स्कैन करें और उस तत्व को पहले बिन में रखें जो फिट बैठता है। यदि तत्व उस समय किसी भी मौजूदा डिब्बे में फिट नहीं होता है तो हम केवल एक नया बिन शुरू करते हैं।

उदाहरण

// C++ program to find number of bins needed implementing First Fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing first fit online algorithm
int firstFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // We have to find the first bin that can accommodate weight1[i]
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
            bin_rem[j] = bin_rem[j] - weight1[i];
            break;
         }
      }
      // If no bin could accommodate weight1[i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in First Fit : "
   <<firstFit(weight1, m, C);
   return 0;
}

आउटपुट

Number of bins required in First Fit : 4

First Fit के उपरोक्त क्रियान्वयन में O(m2) समय लगता है, लेकिन First Fit का उपयोग O(m log m) समय में सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री को लागू करने में किया जा सकता है।

बेस्ट फ़िट -

अवधारणा अगले आइटम को सबसे सख्त स्थिति में रखना है। इसका मतलब है कि इसे बिन में रख दें ताकि कम से कम खाली जगह बची रहे।

उदाहरण

// C++ program to calculate number of bins required implementing Best fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to returns number of bins required implementing best fit online algorithm
int bestFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // Place elements one by one
   for (int i = 0; i < m; i++){
      // Find the best bin that can accomodate weight1[i]
      int j;
      // We have to initialize minimum space left and index of best bin
      int min = C + 1, bi = 0;
      for (j = 0; j < res; j++){
         if (bin_rem[j] >= weight1[i] && bin_rem[j] - weight1[i] < min) {
         bi = j;
         min = bin_rem[j] - weight1[i];
      }
   }
   // We create a new bin,if no bin could accommodate weight1[i],
   if (min == C + 1) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   else // Assign the element to best bin
   bin_rem[bi] -= weight1[i];
   }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in Best Fit : "
   <<bestFit(weight1, m, C);
   return 0;
}

आउटपुट

Number of bins required in Best Fit : 4

सर्वश्रेष्ठ फिट को ओ (एम लॉग एम) समय में स्व-संतुलन बाइनरी सर्च ट्री को लागू करने में भी लागू किया जा सकता है।

ऑफ़लाइन एल्गोरिदम

ऑफ़लाइन संस्करण के मामले में, हमारे पास सभी तत्व सामने हैं। ऑनलाइन एल्गोरिदम के साथ एक समस्या यह है कि बड़े तत्वों को पैक करना मुश्किल है, खासकर यदि वे अनुक्रम में देर से होते हैं। हम इनपुट अनुक्रम को क्रमबद्ध करके और बड़े तत्वों को पहले रखकर इसे दूर कर सकते हैं।

पहला फिट घटाना -

उदाहरण

// C++ program to locate number of bins needed implementing First Fit Decreasing algorithm.
#include <bits/stdc++.h>
using namespace std;
/* We copy firstFit() from above */
int firstFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // We have to find the first bin that can accommodate weight1[i]
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
         bin_rem[j] = bin_rem[j] - weight1[i];
         break;
      }
   }
   // If no bin could accommodate weight1[i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
return res;
}
// We have to returns number of bins required implementing first fit decreasing offline algorithm
int firstFitDec(int weight1[], int m, int C){
   // At first we sort all weights in decreasing order
   sort(weight1, weight1 + m, std::greater<int>());
   // Now we call first fit for sorted items
   return firstFit(weight1, m, C);
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in First Fit "
   << "Decreasing : " << firstFitDec(weight1, m, C);
   return 0;
}

आउटपुट

Number of bins required in First Fit Decreasing : 3

पहले फिट घटने से नमूना इनपुट के लिए सबसे अच्छा परिणाम उत्पन्न होता है क्योंकि तत्वों को पहले क्रमबद्ध किया जाता है।

पहली फ़िट घटाने का उपयोग ओ (एम लॉग एम) समय में स्व-संतुलन बाइनरी सर्च ट्री को लागू करने में भी किया जा सकता है।