- भरा जा रहा है
- यहाँ से पढ़ा
- उत्तर
नैपसैक समस्या
आप सीमित भार ही उठा सकते हैं, और हर वस्तु का एक भार और एक मान है। सबसे ज़्यादा मान ले जाने के लिए आप कौन-सी वस्तुएँ लें? हर संयोजन आज़माने पर हर नई वस्तु के साथ काम दोगुना हो जाता है। वस्तुओं की पंक्तियों और क्षमताओं के कॉलम वाली एक टेबल एक-एक सेल करके सबसे अच्छा थैला ढूँढ लेती है। किसी वस्तु को थैले में रखने के लिए उस पर टैप करें, और उसे निकालने के लिए उस पर फिर से टैप करें (चाहे वह थैले में हो या शेल्फ़ पर)। थैला भार से भरता है, और टाइलें दिखाती हैं कि आपने कितने डॉलर रखे और सबसे अच्छा संभव कितना है। सबसे अच्छा थैला देखने के लिए “सबसे अच्छी पैकिंग” दबाएँ। पैनल में वस्तुओं के किलोग्राम और डॉलर बदलें, वस्तुएँ जोड़ें या हटाएँ, और थैले की क्षमता तय करें। “टेबल” व्यू दिखाता है कि डायनामिक प्रोग्रामिंग सबसे अच्छा थैला कैसे ढूँढ़ती है: टेबल को भरते देखने के लिए “चलाएँ” दबाएँ, या एक-एक कदम चलने के लिए “आगे” और “पीछे” दबाएँ, और कहीं भी पहुँचने के लिए कदम वाले स्लाइडर को खींचें। हर पंक्ति एक वस्तु जोड़ती है, हर कॉलम किलोग्राम में एक क्षमता है, और हर सेल में समा सकने वाले सबसे ज़्यादा डॉलर होते हैं। टेबल चुनी होने पर तीर कुंजियाँ एक-एक कदम चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- वस्तुओं के डिब्बों पर टैप करके उन्हें थैले में रखें, और देखें कि थैला किलोग्राम में वज़न के हिसाब से कैसे भरता है।
- डॉलर में सबसे अच्छा संभव मूल्य पाने की कोशिश करें, या सबसे अच्छा थैला देखने के लिए “सबसे अच्छी पैकिंग” दबाएँ।
- “टेबल” दृश्य खोलें और चलाएँ दबाएँ, ताकि देख सकें कि हर सेल किसी वस्तु को रखने और छोड़ने के बीच कैसे चुनता है।
टेबल कैसे काम करती है
हर पंक्ति एक वस्तु जोड़ती है और हर कॉलम 0 से लेकर थैले की क्षमता तक की एक क्षमता है। एक सेल में वह सबसे बड़ा मान होता है जो उसकी पंक्ति तक की वस्तुओं से उस क्षमता में समा सके। नई वस्तु के बिना, यह ऊपर वाला सेल है। नई वस्तु के साथ, अगर वह समा जाए, तो यह वस्तु का मान और बचे हुए भार का सबसे अच्छा मान है, जो ऊपर की पंक्ति में वस्तु के भार जितना बाईं ओर है। सेल दोनों में से बड़ा मान रखता है। पहली पंक्ति, जिसमें कोई वस्तु नहीं है, पूरी शून्य होती है।
वस्तुओं को उलटा पढ़ना
नीचे दायाँ सेल सबसे अच्छा मान है। वस्तुएँ ढूँढने के लिए वहीं से शुरू करें और उसकी तुलना ऊपर वाले सेल से करें: अगर दोनों बराबर हैं, तो आखिरी वस्तु की ज़रूरत नहीं थी; अगर वह बड़ा है, तो वस्तु थैले में है, इसलिए उसका भार घटाएँ और उस कॉलम पर जाएँ। पहली पंक्ति तक हर बार एक पंक्ति ऊपर जाएँ। ऐप यह उलटा पढ़ना नारंगी रंग में दिखाता है और रखी गई वस्तुओं की सूची टेबल के नीचे देता है।
अक्सर पूछे जाने वाले प्रश्न
0/1 नैपसैक समस्या में 0/1 का क्या मतलब है?
हर वस्तु एक बार रखी जाती है या बिल्कुल नहीं, कभी आधी-अधूरी नहीं और कभी दो बार नहीं। अगर वस्तुओं को चावल के दानों की तरह बाँटा जा सकता, तो प्रति भार सबसे अच्छे मान वाली वस्तु पहले रखना सबसे अच्छा होता; उसे फ्रैक्शनल नैपसैक समस्या कहते हैं।
प्रति भार सबसे अच्छे मान वाली वस्तु पहले क्यों न रखें?
क्योंकि पूरी वस्तुएँ खाली जगह छोड़ सकती हैं। क्षमता 7 हो और वस्तुओं के भार 1, 3, 4 और 5 तथा मान 1, 4, 5 और 7 हों, तो प्रति भार सबसे अच्छा मान भार 5 वाली वस्तु का है, जिसके बाद सिर्फ़ भार 1 वाली वस्तु की जगह बचती है, और कुल 8 होता है। भार 3 और 4 वाली वस्तुओं का मान मिलकर 9 है।
नैपसैक एल्गोरिदम कितना तेज़ है?
टेबल में (वस्तुओं की संख्या + 1) गुणा (क्षमता + 1) सेल होते हैं, और हर सेल एक चरण में भरता है। छोटी क्षमताओं के लिए यह तेज़ है, पर क्षमता बहुत बड़ी संख्या हो सकती है, इसलिए सामान्य रूप से यह समस्या NP-कठिन है; टेबल वाली इस विधि को छद्म-बहुपद (pseudo-polynomial) कहते हैं।
क्या एक ही वस्तु दो बार रखी जा सकती है?
यहाँ नहीं। अनबाउंडेड नैपसैक समस्या में हर वस्तु कितनी भी बार ली जा सकती है; तब टेबल ऊपर की पंक्ति के बजाय उसी पंक्ति में बाईं ओर वाला सेल पढ़ती है, जैसा सिक्कों के छुट्टे वाले ऐप में होता है।
क्या कुछ कहीं भेजा जाता है?
नहीं। सारी गणना आपके ब्राउज़र में होती है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ