C++ प्रोग्राम बिन पैकिंग एल्गोरिथम को लागू करने के लिए

बिन पैकिंग समस्या एक विशेष प्रकार की कटिंग स्टॉक समस्या है। बिन पैकिंग समस्या में, अलग-अलग आयतन की वस्तुओं को एक सीमित संख्या में कंटेनरों में पैक किया जाना चाहिए या प्रत्येक वॉल्यूम V के डिब्बे में इस तरह से पैक किया जाना चाहिए कि उपयोग किए जाने वाले डिब्बे की संख्या कम से कम हो। कम्प्यूटेशनल जटिलता सिद्धांत में, यह एक संयोजन एनपी-हार्ड समस्या है।

जब डिब्बे की संख्या 1 तक सीमित होती है और प्रत्येक वस्तु को एक मात्रा और एक मूल्य दोनों की विशेषता होती है, तो बिन में फिट होने वाली वस्तुओं के मूल्य को अधिकतम करने की समस्या को बस्ता समस्या के रूप में जाना जाता है।

एल्गोरिदम

Begin
   Binpacking(pointer, size, no of sets)
   Declare bincount, m, i
   Initialize bincount = 1, m=size
   For i = 0 to number of sets
   if (m - *(a + i) > 0) do
      m = m - *(a + i)
      Continue
   Else
      Increase bincount
      m = size;
      Decrement i
      Print number of bins required
End

उदाहरण कोड

#include<iostream>
using namespace std;
void binPacking(int *a, int size, int n) {
   int binCount = 1;
   int m = size;
   for (int i = 0; i < n; i++) {
      if (m - *(a + i) > 0) {
         m -= *(a + i);
         continue;
      } else {
         binCount++;
         m = size;
         i--;
      }
   }
   cout << "Number of bins required: " << binCount;
}
int main(int argc, char **argv) {
   cout << "Enter the number of items in Set: ";
   int n;
   cin >> n;
   cout << "Enter " << n << " items:";
   int a[n];
   for (int i = 0; i < n; i++)
      cin >> a[i];
   cout << "Enter the bin size: ";
   int size;
   cin >> size;
   binPacking(a, size, n);
}

आउटपुट

Enter the number of items in Set: 3
Enter 3 items:4
6
7
Enter the bin size: 26
Number of bins required: 1