Best-fit bin packing
बेस्ट-फिट बिन पैकिंग के लिए एक ऑनलाइन एल्गोरिदम है। इसका निवेश विभिन्न आकारों की वस्तुओं की एक सूची है। इसका उत्पादन एक पैकिंग है-वस्तुओं का एक निश्चित क्षमता के डिब्बे में विभाजन, जैसे कि प्रत्येक बिन में वस्तुओं के आकार का योग अधिकतम क्षमता पर हो। आदर्श रूप से, हम जितना संभव हो उतना कम डिब्बे का उपयोग करना चाहेंगे, लेकिन डिब्बे की संख्या को कम करना एक एन. पी.-कठिन समस्या है। सबसे उपयुक्त एल्गोरिथ्म निम्नलिखित शोध का उपयोग करता हैः यह खुले डिब्बे की एक सूची रखता है, जो शुरू में खाली होता है। जब कोई वस्तु आती है, तो उसे अधिकतम भार के साथ बिन मिलता है जिसमें वस्तु फिट हो सकती है, यदि कोई हो। यदि ऐसा बिन पाया जाता है, तो नई वस्तु को उसके अंदर रखा जाता है। अन्यथा, एक नया बिन खोला जाता है और आने वाली वस्तु को उसके अंदर रखा जाता है। सन्निकटन अनुपात बी. एफ. (एल) द्वारा सर्वश्रेष्ठ-फिट द्वारा उपयोग किए जाने वाले डिब्बों की संख्या को दर्शाता है, और ओ. पी. टी. (एल) द्वारा सूची एल के लिए संभव डिब्बों की इष्टतम संख्या को दर्शाता है। बी. एफ. (एल) का विश्लेषण कई चरणों में किया गया था। पहली ऊपरी सीमा 1971 में उलमैन द्वारा साबित की गई थी। गैरी, ग्राहम और उलमैन, जॉनसन और डेमर्स ने एक बेहतर ऊपरी सीमा साबित की। इसके बाद गैरी, ग्राहम, जॉनसन, उलमैन, याओ और ची-चिह ने इसमें सुधार किया। अंत में डोसा और स्गल द्वारा इस सीमा में सुधार किया गया। वे एक उदाहरण इनपुट सूची भी प्रस्तुत करते हैं, जो इस सीमा से मेल खाती है। सबसे खराब-फिट सबसे अच्छा-फिट करने के लिए एक "दोहरी" एल्गोरिथ्म हैः यह अगली वस्तु को न्यूनतम भार के साथ बिन में रखने की कोशिश करता है। यह एल्गोरिथ्म नेक्स्ट-फिट के रूप में बुरी तरह से व्यवहार कर सकता है, और इसके लिए सबसे खराब स्थिति सूची में ऐसा करेगा। इसके अलावा, यह मानता है। चूँकि वर्स्ट-फिट एक एनीफिट-एल्गोरिदम है, इसलिए एक एनीफिट-एल्गोरिदम मौजूद है। संदर्भ बिन पैकिंग