बिन पैकिंग समस्या कटिंग स्टॉक समस्या का एक विशेष प्रकार है। बिन पैकिंग समस्या में, विभिन्न आयतन की वस्तुओं को V आयतन के परिमित संख्या के कंटेनरों या बिन्स में इस तरह पैक किया जाना चाहिए कि उपयोग किए गए बिन्स की संख्या न्यूनतम हो। कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी में, यह एक संयोजन NP-हार्ड समस्या है।
जब बिन्स की संख्या 1 तक सीमित होती है और प्रत्येक आइटम को आयतन और वैल्यू दोनों द्वारा वर्णित किया जाता है, तो बिन में फिट होने वाली वस्तुओं की वैल्यू को अधिकतम करने की समस्या को नैपसैक समस्या के रूप में जाना जाता है।
एल्गोरिदम
Begin
Binpacking(पॉइंटर, आकार, सेट्स की संख्या)
bincount, m, i घोषित करें
bincount = 1, m = आकार इनिशियलाइज़ करें
i = 0 से सेट्स की संख्या तक
यदि (m - *(a + i) > 0) करें
m = m - *(a + i)
जारी रखें
अन्यथा
bincount बढ़ाएं
m = आकार;
i घटाएं
आवश्यक बिन्स की संख्या प्रिंट करें
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
