नैपसैक समस्या
भार सीमा वाला एक पैदल यात्री, बोरी लिए एक चोर, बजट और परियोजनाओं की सूची वाली एक कंपनी: सबके सामने एक ही सवाल है। सीमा पार किए बिना सबसे ज़्यादा मान पाने के लिए क्या-क्या रखना चाहिए? यही नैपसैक समस्या है, और जब भार मध्यम आकार की पूर्ण संख्याएँ हों, तो गतिशील प्रोग्रामिंग इसे ठीक-ठीक हल कर देती है।
समस्या
n वस्तुएँ हैं, हर एक का एक भार और एक मान है, और एक थैला है जिसमें अधिकतम W भार आ सकता है। वस्तुओं का ऐसा समूह चुनें जिसका कुल भार अधिकतम W हो और कुल मान जितना हो सके उतना बड़ा हो। हर वस्तु पूरी अंदर जाती है या बाहर रहती है, इसीलिए इसे 0/1 नैपसैक समस्या कहते हैं। n वस्तुओं के 2ⁿ संभव समूह होते हैं, इसलिए सबको आज़माना जल्द ही असंभव हो जाता है।
टेबल
मान लें best[i][w] वह सबसे बड़ा मान है जो सिर्फ़ पहली i वस्तुओं से भार w में समा सके। तब best[0][w] = 0 है, और आगे की हर पंक्ति के लिए दो विकल्प हैं: वस्तु i को छोड़ें, जिससे best[i − 1][w] मिलता है, या अगर उसका भार wᵢ समा जाए तो उसे रखें, जिससे उसका मान और best[i − 1][w − wᵢ] मिलता है। जो बड़ा हो, वही best[i][w] है। टेबल को पंक्ति-दर-पंक्ति भरने से जिन दो सेलों की ज़रूरत होती है, वे हमेशा पहले से तैयार रहते हैं।
एक उदाहरण
क्षमता 7 लें और चार वस्तुएँ जिनके भार 1, 3, 4 और 5 तथा मान 1, 4, 5 और 7 हैं। सिर्फ़ पहली वस्तु से, 1 और उससे ऊपर की हर क्षमता का मान 1 है। दूसरी जोड़ने पर क्षमता 4 में दोनों आ जाती हैं, मान 5। तीसरी जोड़ने पर क्षमता 7 में वस्तुएँ 2 और 3 आ जाती हैं, मान 9। चौथी वस्तु, भार 5 और मान 7, क्षमता 6 या 7 पर वस्तु 1 के साथ मिलकर 8 दे सकती है, पर 9 बेहतर है, इसलिए नीचे दायाँ सेल 9 है: भार 3 और 4 वाली वस्तुएँ रखें।
यह कितनी कठिन है?
टेबल को लगभग n·W चरण चाहिए। यह तेज़ लगता है, पर W एक संख्या है, और d अंकों वाली संख्या 10 की घात d जितनी बड़ी हो सकती है, इसलिए काम इनपुट की लंबाई के साथ घातांकी रूप से बढ़ता है। नैपसैक समस्या NP-कठिन है; यह 1972 की रिचर्ड कार्प की 21 NP-पूर्ण समस्याओं में से एक थी। व्यवहार में टेबल, ब्रांच एंड बाउंड और अच्छी सन्निकटन योजनाएँ बड़े वास्तविक उदाहरणों को अच्छी तरह संभाल लेती हैं।
इतिहास और उपयोग
यह नाम 20वीं सदी की शुरुआत में गणितज्ञ टोबियास डैंट्ज़िग से आता है, और उनके बेटे जॉर्ज डैंट्ज़िग ने 1957 में इसके लिए एक क्लासिक ग्रीडी विधि दी। नैपसैक समस्याएँ बजट बनाने और पोर्टफ़ोलियो चुनने में, कच्चे माल को कम से कम बर्बादी के साथ काटने में, माल लादने में, और शुरुआती पब्लिक-की क्रिप्टोग्राफ़ी में भी सामने आती हैं: 1978 की मर्कल–हेलमैन क्रिप्टोसिस्टम एक नैपसैक समस्या पर बनी थी, और कुछ साल बाद तोड़ दी गई।
इसे खुद आज़माएँ
ऐप खोलें, “टेबल” दृश्य पर जाएँ और “आगे” दबाएँ। नारंगी सेल भरा जा रहा है, और नीले सेल वे दो हैं जिनकी वह तुलना करता है: ठीक ऊपर वाला सेल, और ऊपर की पंक्ति में वस्तु के भार जितना बाईं ओर वाला सेल। आखिरी सेल के बाद, उलटा पढ़ना नीचे दाएँ कोने से नारंगी रंग में ऊपर चढ़ता है, और रखी गई वस्तुएँ टेबल के नीचे दिखती हैं।
अक्सर पूछे जाने वाले प्रश्न
0/1, बाउंडेड और अनबाउंडेड नैपसैक में क्या अंतर है?
0/1 रूप में हर वस्तु अधिकतम एक बार ली जाती है। बाउंडेड रूप में हर वस्तु की सीमित प्रतियाँ होती हैं, और अनबाउंडेड रूप में कितनी भी। इनके बीच टेबल बस थोड़ी-सी बदलती है।
क्या नैपसैक के लिए ग्रीडी विधि कभी सही होती है?
फ्रैक्शनल नैपसैक समस्या में, जहाँ वस्तुएँ बाँटी जा सकती हैं, प्रति भार सबसे अच्छा मान पहले लेना सबसे अच्छा है। पूरी वस्तुओं के लिए नतीजा बहुत दूर हो सकता है, फिर भी ग्रीडी और अकेली सबसे कीमती वस्तु में से जो बेहतर हो, वह हमेशा सबसे अच्छे मान का कम से कम आधा होता है।
टेबल को कितनी मेमोरी चाहिए?
पूरी टेबल के लिए (n + 1)·(W + 1) सेल, और वस्तुओं को उलटा पढ़ने के लिए यही चाहिए। अगर सिर्फ़ सबसे अच्छा मान चाहिए, तो W + 1 सेलों की एक पंक्ति काफ़ी है, जिसे दाएँ से बाएँ भरा जाता है।
क्या नैपसैक और सबसेट सम एक ही हैं?
सबसेट सम वह विशेष स्थिति है जिसमें हर वस्तु का मान उसके भार के बराबर होता है और सवाल यह है कि क्या थैला ठीक-ठीक भरा जा सकता है। यह भी NP-पूर्ण है और इसी तरह की टेबल से हल होती है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
नैपसैक समस्या आज़माएँ