इस्तेमाल हुए बिन
निचली सीमा
न्यूनतम संभव

      वस्तुओं के वज़न (kg)

        बिन पैकिंग समस्या के बारे में और

        बिन पैकिंग समस्या

        डिब्बे वैन में, फ़ाइलें डिस्क पर, काम मशीनों पर: बिन पैकिंग समस्या पूछती है कि वस्तुओं की एक सूची को जितने हो सकें उतने कम बराबर बिनों में कैसे समाया जाए। ऐसी कोई तेज़ विधि ज्ञात नहीं जो हमेशा सबसे अच्छी पैकिंग ढूँढ़ ले, लेकिन सरल नियम काफ़ी क़रीब पहुँच जाते हैं। एक नियम चुनें, उसे चरण-दर-चरण चलाएँ, और सटीक उत्तर से तुलना करें। शेल्फ़ पर किसी वस्तु पर टैप करें, फिर उस बिन पर टैप करें जिसमें उसे रखना है: हरे बिनों में उसके लिए जगह है, और “नया बिन” एक और बिन खोलता है। बिन में रखी वस्तु पर टैप करके उसे फिर से निकालें। सभी वस्तुओं को जितने हो सकें उतने कम बिनों में पैक करें; निचली सीमा (कुल वज़न को बिन के आकार से भाग देकर ऊपर की ओर पूर्णांकित) और न्यूनतम संभव दिखाते हैं कि आप कितने करीब हैं, और “सबसे कम बिन” सबसे अच्छी पैकिंग दिखाता है। पैनल में वस्तुओं के वज़न (किलोग्राम में) और बिन का आकार बदलें। “कदम दर कदम” व्यू दिखाता है कि तेज़ नियम कैसे पैक करते हैं: नेक्स्ट फ़िट, फ़र्स्ट फ़िट या बेस्ट फ़िट, वस्तुओं के लिखे गए क्रम में या सबसे बड़ी से शुरू करके छाँटकर, या गतिशील प्रोग्रामिंग से मिला सटीक उत्तर। वस्तुओं को बिनों में जाते देखने के लिए “चलाएँ” दबाएँ, या एक-एक कदम चलने के लिए “आगे” और “पीछे” दबाएँ, और कहीं भी जाने के लिए कदम स्लाइडर खींचें। बोर्ड चुना होने पर तीर कुंजियाँ एक-एक कदम चलती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।

        यह कैसे काम करता है

        1. किसी वस्तु पर टैप करें, फिर उसे रखने के लिए जगह वाले बिन पर टैप करें, या नया बिन खोलने के लिए “नया बिन” पर।
        2. जितने कम बिन हो सकें उतने इस्तेमाल करने की कोशिश करें, या सबसे अच्छी पैकिंग देखने के लिए “सबसे कम बिन” दबाएँ।
        3. “कदम दर कदम” दृश्य खोलें, कोई नियम चुनें और “चलाएँ” दबाएँ, ताकि देख सकें कि हर वस्तु बिनों को कैसे आज़माती है।

        नियम

        नेक्स्ट फ़िट सिर्फ़ आख़िरी बिन खुला रखता है: जो वस्तु उसमें नहीं समाती, वह नया बिन शुरू करती है। फ़र्स्ट फ़िट पहले बिन से शुरू करके बिन आज़माता है और जगह वाला पहला बिन लेता है। बेस्ट फ़िट हर बिन आज़माता है और जगह वाले बिनों में सबसे भरा बिन लेता है, जिससे सबसे कम जगह खाली रहती है। फ़र्स्ट फ़िट और बेस्ट फ़िट पहले वस्तुओं को सबसे बड़ी से सबसे छोटी तक छाँट भी सकते हैं, जिससे फ़र्स्ट फ़िट डिक्रीज़िंग और बेस्ट फ़िट डिक्रीज़िंग बनते हैं।

        सटीक उत्तर

        आख़िरी नियम कोई अंदाज़े वाला नियम नहीं है: यह वस्तुओं के समुच्चयों पर गतिशील प्रोग्रामिंग से सबसे कम बिन ढूँढ़ता है। वस्तुओं के हर समुच्चय के लिए यह उन्हें रखने वाले सबसे कम बिन याद रखता है और, उतने बिनों वाली पैकिंग में से, आख़िरी बिन का सबसे कम भार। समुच्चय एक बार में एक वस्तु से बढ़ता है, जो या तो आख़िरी बिन में जुड़ती है या नया बिन खोलती है। n वस्तुओं के 2ⁿ समुच्चय होते हैं, इसीलिए ऐप ज़्यादा से ज़्यादा 12 वस्तुएँ लेने देता है। निचली सीमा, यानी कुल आकार को बिन के आकार से भाग देकर ऊपर की ओर पूर्णांकित संख्या, दिखाती है कि कोई पैकिंग सबसे अच्छी के कितनी क़रीब है।

        अक्सर पूछे जाने वाले प्रश्न

        कौन-सा बिन पैकिंग नियम सबसे अच्छा है?

        तेज़ नियमों में फ़र्स्ट फ़िट डिक्रीज़िंग और बेस्ट फ़िट डिक्रीज़िंग सबसे मज़बूत हैं: वे कभी भी सबसे कम बिनों के 11/9 गुना और एक छोटे स्थिरांक से ज़्यादा बिन नहीं लगाते। बिना छँटी वस्तुओं पर फ़र्स्ट फ़िट और बेस्ट फ़िट सबसे कम बिनों के 1.7 गुना के भीतर रहते हैं, और नेक्स्ट फ़िट 2 गुना के भीतर।

        बिन पैकिंग कठिन क्यों है?

        यह तय करना कि वस्तुएँ सिर्फ़ दो बिनों में समा जाएँगी या नहीं, अपने आप में विभाजन समस्या (partition problem) है, जो NP-पूर्ण है। इसलिए जब तक P = NP न हो, कोई भी विधि हर इनपुट के लिए सबसे कम बिन जल्दी नहीं ढूँढ़ सकती, और सटीक विधियों को सबसे बुरी स्थिति में घातांकी समय लगता है।

        निचली सीमा क्या है?

        वस्तुओं के कुल आकार को बिन के आकार से भाग देकर ऊपर की ओर पूर्णांकित करने पर मिली संख्या। कोई भी पैकिंग इससे कम बिन नहीं लगा सकती, क्योंकि बिनों में सारी वस्तुएँ आनी चाहिए। अक्सर सबसे अच्छी पैकिंग इसके बराबर होती है, पर हमेशा नहीं: 10 आकार के बिनों के साथ आकार 6 की तीन वस्तुओं की निचली सीमा 2 है, पर 3 बिन चाहिए।

        क्या यह गतिशील प्रोग्रामिंग है?

        सटीक उत्तर है: यह वस्तुओं के हर समुच्चय की सबसे अच्छी पैकिंग छोटे समुच्चयों की सबसे अच्छी पैकिंग से बनाता है। तेज़ नियम लालची (ग्रीडी) विधियाँ हैं, जो एक बार तय करती हैं और फिर कभी पीछे मुड़कर नहीं देखतीं।

        क्या कुछ कहीं भेजा जाता है?

        नहीं। सब कुछ आपके ब्राउज़र में ही गिना जाता है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।

        आज़माने के लिए तैयार?

        अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

        एडिटर पर जाएँ