अलग-अलग वजन के m तत्वों और प्रत्येक की क्षमता C वाले बिन्स दिए गए हैं, प्रत्येक तत्व को एक बिन में असाइन करें ताकि उपयोग किए गए कुल बिन्स की संख्या न्यूनतम हो। मान लें कि सभी तत्वों का वजन बिन क्षमता से कम है।
अनुप्रयोग
एकाधिक डिस्क पर डेटा रखना।
ट्रकों जैसे कंटेनरों की लोडिंग।
निश्चित लंबाई के रेडियो/टीवी स्टेशन ब्रेक में विज्ञापन पैक करना।
जॉब शेड्यूलिंग।
उदाहरण
इनपुट: weight[] = {4, 1, 8, 1, 4, 2} बिन क्षमता c = 10 आउटपुट: 2 हमें सभी तत्वों को समायोजित करने के लिए कम से कम 2 बिन्स की आवश्यकता है पहला बिन {4, 4, 2} और दूसरा बिन {8, 2} से बना हैनिचली सीमा
हम ceil() फ़ंक्शन का उपयोग करके आवश्यक न्यूनतम बिन्स की संख्या पर निचली सीमा की गणना कर सकते हैं। निचली सीमा नीचे दी जा सकती है -
न्यूनतम बिन्स >= ceil ((कुल वजन) / (बिन क्षमता))
उपरोक्त उदाहरण में, पहले उदाहरण के लिए निचली सीमा "ceil(4 + 1 + 8 + 2 + 4 + 1)/10" = 2 है
इस समस्या के लिए निम्नलिखित सन्निकटन एल्गोरिदम लागू किए जाते हैं।
ऑनलाइन एल्गोरिदम
ये एल्गोरिदम बिन पैकिंग समस्याओं के लिए लागू किए जाते हैं जहां तत्व एक समय में आते हैं (अज्ञात क्रम में), प्रत्येक को अगले तत्व पर विचार करने से पहले एक बिन में रखा जाना चाहिए।
नेक्स्ट फिट -
अगले तत्व को प्रोसेस करते समय, जांचें कि क्या यह अंतिम तत्व के समान बिन में फिट बैठता है। केवल तभी नया बिन उपयोग करें जब यह फिट न हो।
इस एल्गोरिदम के लिए C++ एप्लिकेशन निम्नानुसार है।
// नेक्स्ट फिट एल्गोरिदम का उपयोग करके आवश्यक बिन्स की संख्या की गणना करने के लिए C++ प्रोग्राम। #include <bits/stdc++.h> using namespace std; // नेक्स्ट फिट ऑनलाइन एल्गोरिदम का उपयोग करके आवश्यक बिन्स की संख्या लौटानी है int nextFit(int weight1[], int m, int C){ // परिणाम (बिन्स की संख्या) और वर्तमान बिन में शेष क्षमता इनिशियलाइज़ करें। int res = 0, bin_rem = C; // हमें तत्वों को एक-एक करके रखना है for (int i = 0; i < m; i++) { // यदि यह तत्व वर्तमान बिन में फिट नहीं हो सकता if (weight1[i] > bin_rem) { res++; // एक नया बिन उपयोग करें bin_rem = C - weight1[i]; } else bin_rem -= weight1[i]; } return res; } // ड्राइवर प्रोग्राम 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++ प्रोग्राम। #include <bits/stdc++.h> using namespace std; // फर्स्ट फिट ऑनलाइन एल्गोरिदम का उपयोग करके आवश्यक बिन्स की संख्या लौटानी है int firstFit(int weight1[], int m, int C){ // परिणाम इनिशियलाइज़ करें (बिन्स की संख्या) int res = 0; // बिन्स में शेष स्थान संग्रहीत करने के लिए एक सरणी बनाएं अधिकतम n बिन्स हो सकते हैं int bin_rem[m]; // हमें तत्वों को एक-एक करके रखना है for (int i = 0; i < m; i++) { // पहला बिन ढूंढें जो 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; } } // यदि कोई बिन weight1[i] को समायोजित नहीं कर सका if (j == res) { bin_rem[res] = C - weight1[i]; res++; } } return res; } // ड्राइवर प्रोग्राम 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
फर्स्ट फिट के उपरोक्त कार्यान्वयन में O(m2) समय लगता है, लेकिन फर्स्ट फिट को सेल्फ-बैलेंसिंग बाइनरी सर्च ट्रीज़ का उपयोग करके O(m log m) समय में लागू किया जा सकता है।
बेस्ट फिट -
अवधारणा अगले आइटम को सबसे तंग स्थिति में रखना है। इसका मतलब है इसे उस बिन में रखें ताकि कम से कम खाली जगह बचे।
उदाहरण
// बेस्ट फिट एल्गोरिदम का उपयोग करके आवश्यक बिन्स की संख्या की गणना करने के लिए C++ प्रोग्राम। #include <bits/stdc++.h> using namespace std; // बेस्ट फिट ऑनलाइन एल्गोरिदम का उपयोग करके आवश्यक बिन्स की संख्या लौटानी है int bestFit(int weight1[], int m, int C){ // परिणाम इनिशियलाइज़ करें (बिन्स की संख्या) int res = 0; // बिन्स में शेष स्थान संग्रहीत करने के लिए एक सरणी बनाएं अधिकतम n बिन्स हो सकते हैं int bin_rem[m]; // तत्वों को एक-एक करके रखें for (int i = 0; i < m; i++){ // वह बेस्ट बिन ढूंढें जो weight1[i] को समायोजित कर सके int j; // न्यूनतम शेष स्थान और बेस्ट बिन के इंडेक्स को इनिशियलाइज़ करें 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]; } } // यदि कोई बिन weight1[i] को समायोजित नहीं कर सका तो नया बिन बनाएं if (min == C + 1) { bin_rem[res] = C - weight1[i]; res++; } else // तत्व को बेस्ट बिन में असाइन करें bin_rem[bi] -= weight1[i]; } return res; } // ड्राइवर प्रोग्राम 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
बेस्ट फिट को भी सेल्फ-बैलेंसिंग बाइनरी सर्च ट्रीज़ का उपयोग करके O(m log m) समय में लागू किया जा सकता है।
ऑफलाइन एल्गोरिदम
ऑफलाइन संस्करण के मामले में, हमारे पास सभी तत्व पहले से होते हैं। ऑनलाइन एल्गोरिदम के साथ एक समस्या यह है कि बड़े तत्वों को पैक करना मुश्किल होता है, खासकर यदि वे अनुक्रम में देर से आते हैं। हम इनपुट अनुक्रम को सॉर्ट करके और बड़े तत्वों को पहले रखकर इसे दूर कर सकते हैं।
फर्स्ट फिट डिक्रीजिंग -
उदाहरण
// फर्स्ट फिट डिक्रीजिंग एल्गोरिदम का उपयोग करके आवश्यक बिन्स की संख्या खोजने के लिए C++ प्रोग्राम। #include <bits/stdc++.h> using namespace std; /* हम ऊपर से firstFit() कॉपी करते हैं */ int firstFit(int weight1[], int m, int C){ // परिणाम इनिशियलाइज़ करें (बिन्स की संख्या) int res = 0; // बिन्स में शेष स्थान संग्रहीत करने के लिए एक सरणी बनाएं अधिकतम n बिन्स हो सकते हैं int bin_rem[m]; // हमें तत्वों को एक-एक करके रखना है for (int i = 0; i < m; i++) { // पहला बिन ढूंढें जो 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; } } // यदि कोई बिन weight1[i] को समायोजित नहीं कर सका if (j == res) { bin_rem[res] = C - weight1[i]; res++; } } return res; } // फर्स्ट फिट डिक्रीजिंग ऑफलाइन एल्गोरिदम का उपयोग करके आवश्यक बिन्स की संख्या लौटानी है int firstFitDec(int weight1[], int m, int C){ // सबसे पहले हम सभी वजन को घटते क्रम में सॉर्ट करते हैं sort(weight1, weight1 + m, std::greater<int>()); // अब हम सॉर्ट किए गए आइटम्स के लिए फर्स्ट फिट कॉल करते हैं return firstFit(weight1, m, C); } // ड्राइवर प्रोग्राम 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
फर्स्ट फिट डिक्रीजिंग सैंपल इनपुट के लिए सर्वोत्तम परिणाम उत्पन्न करता है क्योंकि तत्व पहले सॉर्ट किए जाते हैं।
फर्स्ट फिट डिक्रीजिंग को भी सेल्फ-बैलेंसिंग बाइनरी सर्च ट्रीज़ का उपयोग करके O(m log m) समय में लागू किया जा सकता है।
