नैपसैक समस्या

एक आयामी (बाधा) नैकपैक समस्या का उदाहरण: कुल वजन को 15 किग्रा से कम या बराबर रखते हुए धन की मात्रा को अधिकतम करने के लिए कौन से बक्सों को चुना जाना चाहिए? नैपसैक समस्याओं की एक सूची # एकाधिक प्रतिबंध बॉक्स के वजन और मात्रा दोनों पर विचार कर सकते हैं।
(समाधान: यदि प्रत्येक बॉक्स की कोई संख्या उपलब्ध है, तो तीन पीले बॉक्स और तीन ग्रे बॉक्स; यदि केवल दिखाए गए बॉक्स उपलब्ध हैं, तो हरे बॉक्स को छोड़कर सभी।)

संयोजी अनुकूलन में बस्ता समस्या निम्नलिखित समस्या है:

वस्तुओं का एक सेट दिया गया है, प्रत्येक वजन और मूल्य के साथ, यह निर्धारित करें कि संग्रह में कौन सी वस्तुओं को शामिल करना है ताकि कुल वजन दी गई सीमा से कम या उसके बराबर हो और कुल मूल्य जितना संभव हो उतना बड़ा हो।' '

इसका नाम किसी ऐसे व्यक्ति के सामने आने वाली समस्या से लिया गया है जो एक निश्चित आकार के थैले से विवश है और इसे सबसे मूल्यवान वस्तुओं से भरना चाहिए। समस्या अक्सर संसाधन आवंटन में उत्पन्न होती है जहां निर्णय लेने वालों को क्रमशः एक निश्चित बजट या समय की कमी के तहत गैर-विभाज्य परियोजनाओं या कार्यों के एक सेट से चुनना पड़ता है।

नैकपैक समस्या का अध्ययन एक सदी से भी अधिक समय से किया जा रहा है, जिसमें शुरुआती कार्य 1897 तक के हैं। नैपसेक नाम की समस्या गणितज्ञ टोबियास डेंजिग (1884-1956) के शुरुआती कार्यों से मिलती है, और सामान को ओवरलोड किए बिना सबसे मूल्यवान या उपयोगी वस्तुओं को पैक करने की सामान्य समस्या को संदर्भित करता है।

अनुप्रयोग

नैपसैक समस्याएँ विभिन्न प्रकार के क्षेत्रों में वास्तविक दुनिया की निर्णय लेने की प्रक्रियाओं में प्रकट होती हैं, जैसे कि कच्चे माल को कम से कम बेकार तरीके से काटना, निवेश और पोर्टफोलियो (वित्त) का चयन, प्रतिभूतिकरण के लिए संपत्ति का चयन | संपत्ति-समर्थित प्रतिभूतिकरण, और मर्कल-हेलमैन नैपसैक क्रिप्टोसिस्टम के लिए कुंजी उत्पन्न करना। मर्कल-हेलमैन और अन्य नैकपैक क्रिप्टो सिस्टम सिस्टम।

Knapsack एल्गोरिदम का एक प्रारंभिक अनुप्रयोग परीक्षणों के निर्माण और स्कोरिंग में था जिसमें परीक्षार्थियों के पास यह विकल्प होता है कि वे किस प्रश्न का उत्तर दें। छोटे उदाहरणों के लिए, परीक्षार्थियों को इस तरह का विकल्प प्रदान करना काफी सरल प्रक्रिया है। उदाहरण के लिए, यदि किसी परीक्षा में 10 अंकों के 12 प्रश्न हैं, तो परीक्षार्थी को अधिकतम 100 अंक प्राप्त करने के लिए केवल 10 प्रश्नों के उत्तर देने की आवश्यकता है। हालांकि, बिंदु मानों के विषम वितरण वाले परीक्षणों पर, विकल्प प्रदान करना अधिक कठिन होता है। Feuerman और Weiss ने एक प्रणाली प्रस्तावित की जिसमें छात्रों को कुल 125 संभावित अंकों के साथ एक विषम परीक्षा दी जाती है। छात्रों को अपनी क्षमताओं के अनुसार सभी प्रश्नों के उत्तर देने के लिए कहा जाता है। समस्याओं के संभावित उपसमुच्चयों में से जिनके कुल अंक मान 100 तक जोड़ते हैं, एक नैपसैक एल्गोरिथ्म यह निर्धारित करेगा कि कौन सा उपसमुच्चय प्रत्येक छात्र को उच्चतम संभव स्कोर देता है। 1999 में स्टोनी ब्रुक यूनिवर्सिटी एल्गोरिथम रिपॉजिटरी के एक अध्ययन से पता चला है कि कॉम्बिनेटरियल एल्गोरिदम और एल्गोरिथम इंजीनियरिंग के क्षेत्र से संबंधित 75 एल्गोरिथम समस्याओं में से, नैपसैक समस्या 19वीं सबसे लोकप्रिय और प्रत्यय पेड़ों और बिन पैकिंग समस्या के बाद तीसरी सबसे अधिक आवश्यक थी। .

परिभाषा

हल की जा रही सबसे आम समस्या 0-1 नैकपैक समस्या है, जो संख्या को प्रतिबंधित करती है$x_{i}$प्रत्येक प्रकार के आइटम की प्रतियों की संख्या शून्य या एक। का एक सेट दिया$n$आइटम 1 से गिने गए$n$, प्रत्येक वजन के साथ$w_{i}$और एक मूल्य$v_{i}$, अधिकतम वजन क्षमता के साथ$W$,

अधिकतम करें $\sum _{i=1}^{n}v_{i}x_{i}$

का विषय है $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ और $x_{i}\in \{0,1\}$.

यहाँ$x_{i}$आइटम के उदाहरणों की संख्या का प्रतिनिधित्व करता है$i$थैले में शामिल करने के लिए। अनौपचारिक रूप से, समस्या थैले में वस्तुओं के मूल्यों के योग को अधिकतम करने की है ताकि वजन का योग थैले की क्षमता से कम या उसके बराबर हो।

'बाउंडेड नैपसैक प्रॉब्लम' ('बीकेपी') प्रतिबंध को हटाता है कि प्रत्येक आइटम में से केवल एक है, लेकिन संख्या को प्रतिबंधित करता है $x_{i}$ अधिकतम गैर-ऋणात्मक पूर्णांक मान के लिए प्रत्येक प्रकार के आइटम की प्रतियों की संख्या $c$:

अधिकतम करें $\sum _{i=1}^{n}v_{i}x_{i}$

का विषय है $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ और $x_{i}\in \{0,1,2,\dots ,c\}.$

अनबाउंड नैपसैक प्रॉब्लम (यूकेपी) प्रत्येक प्रकार के आइटम की प्रतियों की संख्या पर कोई ऊपरी सीमा नहीं रखती है और इसे ऊपर के रूप में तैयार किया जा सकता है सिवाय इसके कि केवल प्रतिबंध $x_{i}$ यह है कि यह एक गैर-ऋणात्मक पूर्णांक है।

अधिकतम करें $\sum _{i=1}^{n}v_{i}x_{i}$

का विषय है $\sum _{i=1}^{n}w_{i}x_{i}\leq W$ और $x_{i}\in \mathbb {Z} ,\ x_{i}\geq 0.$

असीमित नैपसैक समस्या का एक उदाहरण इस आलेख के आरंभ में दिखाए गए चित्र और उस चित्र के शीर्षक में प्रत्येक बॉक्स की कोई संख्या उपलब्ध होने पर पाठ का उपयोग करके दिया गया है।

कम्प्यूटेशनल जटिलता

कंप्यूटर विज्ञान के दृष्टिकोण से नैकपैक समस्या कई कारणों से दिलचस्प है:

• Knapsack समस्या का निर्णय समस्या रूप (क्या वजन W से अधिक हुए बिना कम से कम V का मान प्राप्त किया जा सकता है?) NP-पूर्ण है, इस प्रकार कोई ज्ञात एल्गोरिथम नहीं है जो सभी में सही और तेज़ (बहुपद-समय) दोनों हो मामलों।
• जबकि निर्णय समस्या एनपी-पूर्ण है, अनुकूलन समस्या नहीं है, इसका समाधान कम से कम उतना ही कठिन है जितना कि निर्णय समस्या, और कोई ज्ञात बहुपद एल्गोरिथ्म नहीं है जो यह बता सके कि समाधान दिया गया है कि क्या यह इष्टतम है (जो होगा) इसका मतलब है कि बड़े वी के साथ कोई समाधान नहीं है, इस प्रकार एनपी-पूर्ण निर्णय समस्या को हल करना)।
• गतिशील प्रोग्रामिंग का उपयोग करते हुए एक छद्म-बहुपद समय एल्गोरिथ्म है।
• एक बहुपद-समय सन्निकटन योजना है।
• कई मामले जो व्यवहार में उत्पन्न होते हैं, और कुछ वितरणों से यादृच्छिक उदाहरण, फिर भी ठीक से हल किए जा सकते हैं।

इसमें निर्णय और अनुकूलन समस्याओं के बीच एक लिंक है, यदि कोई बहुपद एल्गोरिदम मौजूद है जो निर्णय की समस्या को हल करता है, तो बहुपद समय में अनुकूलन समस्या के लिए अधिकतम मूल्य पा सकते हैं, इस एल्गोरिथ्म को k के मान में वृद्धि करते हुए पुनरावृत्त रूप से लागू कर सकते हैं। दूसरी ओर, यदि एक एल्गोरिथ्म बहुपद समय में अनुकूलन समस्या का इष्टतम मूल्य पाता है, तो बहुपद समय में इस एल्गोरिथ्म द्वारा समाधान आउटपुट के मूल्य की तुलना k के मान से करके निर्णय समस्या को हल किया जा सकता है। इस प्रकार, समस्या के दोनों संस्करण समान कठिनाई वाले हैं।

शोध साहित्य में एक विषय यह पहचानना है कि नैकपैक समस्या के कठिन उदाहरण क्या दिखते हैं, या किसी अन्य तरीके से देखा जाता है, यह पहचानने के लिए कि व्यवहार में उदाहरणों के कौन से गुण उन्हें उनके सबसे खराब स्थिति वाले एनपी-पूर्ण व्यवहार से अधिक उत्तरदायी बना सकते हैं। इन कठिन उदाहरणों को खोजने का लक्ष्य सार्वजनिक कुंजी क्रिप्टोग्राफ़ी सिस्टम में उनके उपयोग के लिए है, जैसे मर्कल-हेलमैन नैपसैक क्रिप्टोसिस्टम

इसके अलावा, उल्लेखनीय तथ्य यह है कि नैकपैक समस्या की कठोरता इनपुट के रूप पर निर्भर करती है। यदि वजन और मुनाफा पूर्णांक के रूप में दिया जाता है, तो यह कमजोर रूप से एनपी-पूर्ण होता है, जबकि वजन और मुनाफे को तर्कसंगत संख्या के रूप में दिया जाता है, जबकि यह दृढ़ता से एनपी-पूर्ण होता है। रेफरी का नाम = वोज्त्ज़क18 >{{cite journal|last1=Wojtczak|first1=Dominik|title=मजबूत एनपी-तर्कसंगत समस्याओं की पूर्णता पर|journal=International Computer Science Symposium in Russia|volume=10846|year=2018|pages=308–320|doi=10.1007/978-3-319-90530-3_26|arxiv=1802.09465|isbn=978-3-319-90529-7|series=Lecture Notes in Computer Science|s2cid=3637366}</रेफ> हालांकि, तर्कसंगत वजन और मुनाफे के मामले में यह अभी भी एक बहुपद-समय सन्निकटन योजना को स्वीकार करता है। पूरी तरह से बहुपद-समय सन्निकटन योजना।

सुलझाना

डायनेमिक प्रोग्रामिंग दृष्टिकोण के आधार पर नैकपैक समस्याओं को हल करने के लिए कई एल्गोरिदम उपलब्ध हैं, शाखा और बाध्य दृष्टिकोण या दोनों दृष्टिकोणों का हाइब्रिड एल्गोरिदम।

डायनेमिक प्रोग्रामिंग इन-एडवांस एल्गोरिथम

असीमित नैपसैक समस्या (यूकेपी) प्रत्येक प्रकार के आइटम की प्रतियों की संख्या पर कोई प्रतिबंध नहीं लगाती है। इसके अलावा, यहाँ हम मानते हैं $x_{i}>0$

$m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)$

का विषय है $\sum _{i=1}^{n}w_{i}x_{i}\leq w'$ और $x_{i}>0$

उसका अवलोकन करो $m[w]$ निम्नलिखित गुण हैं:

1. $m[0]=0\,\!$ (शून्य मदों का योग, यानी खाली सेट का योग)।

2. $m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])$ , $w_{i}\leq w$, कहाँ $v_{i}$ का मूल्य है $i$-वें प्रकार की वस्तु।

दूसरी संपत्ति को विस्तार से समझाने की जरूरत है। इस तरीके के चलने की प्रक्रिया के दौरान हमारा वजन कैसे बढ़ता है $w$? केवल वहाँ ही $i$ तरीके और पिछले वजन हैं $w-w_{1},w-w_{2},...,w-w_{i}$ जहां कुल हैं $i$ विभिन्न वस्तुओं के प्रकार (अलग-अलग कहने से हमारा मतलब है कि वजन और मूल्य पूरी तरह से समान नहीं हैं)। अगर हम इनमें से प्रत्येक मान को जानते हैं $i$ आइटम और संबंधित अधिकतम मूल्य पहले, हम बस उनकी एक दूसरे से तुलना करते हैं और अंततः अधिकतम मूल्य प्राप्त करते हैं और हम कर रहे हैं।

यहां खाली सेट का अधिकतम शून्य लिया जाता है। से परिणामों को सारणीबद्ध करना $m[0]$ के माध्यम से $m[W]$ समाधान देता है। प्रत्येक की गणना के बाद से $m[w]$ अधिक से अधिक जांच करना शामिल है $n$ आइटम, और अधिक से अधिक हैं $W$ के मान $m[w]$ गणना करने के लिए, डायनेमिक प्रोग्रामिंग सॉल्यूशन का रनिंग टाइम बिग ओ नोटेशन है$O(nW)$. डिवाइडिंग $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ उनके सबसे बड़े सामान्य विभाजक द्वारा रनिंग टाइम को बेहतर बनाने का एक तरीका है।

भले ही पी बनाम एनपी समस्या | पी≠ एनपी, द $O(nW)$ जटिलता इस तथ्य का खंडन नहीं करती है कि नैकपैक समस्या एनपी-पूर्ण है, क्योंकि $W$, विपरीत $n$, समस्या के इनपुट की लंबाई में बहुपद नहीं है। की लंबाई $W$ समस्या का इनपुट बिट्स की संख्या के समानुपाती होता है $W$, $\log W$, नहीं करने के लिए $W$ अपने आप। हालाँकि, चूंकि यह रनटाइम छद्मबहुपद है, यह (निर्णय संस्करण) नैकपैक समस्या को एक कमजोर एनपी-पूर्णता | कमजोर एनपी-पूर्ण समस्या बनाता है।

0-1 बस्ता समस्या

गतिशील प्रोग्रामिंग दृष्टिकोण का प्रदर्शन।

0-1 नैपसैक समस्या के लिए एक समान गतिशील प्रोग्रामिंग समाधान छद्म-बहुपद समय में भी चलता है। मान लीजिए $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ सख्ती से सकारात्मक पूर्णांक हैं। परिभाषित करना $m[i,w]$ वह अधिकतम मान होना चाहिए जो उससे कम या उसके बराबर वजन के साथ प्राप्त किया जा सकता है $w$ तक की वस्तुओं का उपयोग करना $i$ (पहला $i$ सामान)।

हम परिभाषित कर सकते हैं $m[i,w]$ पुनरावर्ती रूप से इस प्रकार है: (परिभाषा ए)

• $m[0,\,w]=0$
• $m[i,\,w]=m[i-1,\,w]$ अगर $w_{i}>w\,\!$ (नया आइटम वर्तमान वजन सीमा से अधिक है)
• $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ अगर $w_{i}\leqslant w$.

फिर गणना करके समाधान निकाला जा सकता है $m[n,W]$. इसे कुशलतापूर्वक करने के लिए, हम पिछली संगणनाओं को संग्रहीत करने के लिए एक तालिका का उपयोग कर सकते हैं।

निम्नलिखित गतिशील कार्यक्रम के लिए स्यूडोकोड है:

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
// NOTE: The array "v" and array "w" are assumed to store all relevant values starting at index 1.

array m[0..n, 0..W];
for j from 0 to W do:
    m[0, j] := 0
for i from 1 to n do:
    m[i, 0] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

इसलिए यह समाधान अंदर चलेगा $O(nW)$ समय और $O(nW)$ अंतरिक्ष। (यदि हमें केवल m [n, W] मान की आवश्यकता है, तो हम कोड को संशोधित कर सकते हैं ताकि आवश्यक मेमोरी की मात्रा O (W) हो जो सरणी m की हाल की दो पंक्तियों को संग्रहीत करती है।)

हालाँकि, अगर हम इसे एक या दो कदम आगे ले जाते हैं, तो हमें पता होना चाहिए कि यह विधि बीच के समय में चलेगी $O(nW)$ और $O(2^{n})$. परिभाषा ए से, हम जानते हैं कि सभी भारों की गणना करने की कोई आवश्यकता नहीं है जब वस्तुओं की संख्या और हमारे द्वारा चुने गए आइटम स्वयं तय होते हैं। कहने का तात्पर्य यह है कि ऊपर दिया गया प्रोग्राम आवश्यकता से अधिक गणना करता है क्योंकि वजन अक्सर 0 से W में बदलता रहता है। इस दृष्टिकोण से, हम इस पद्धति को प्रोग्राम कर सकते हैं ताकि यह पुनरावर्ती रूप से चले।

<सिंटैक्सहाइलाइट लैंग = सी लाइन = 1> // इनपुट: // मान (सरणी v में संग्रहीत) // वजन (सरणी डब्ल्यू में संग्रहीत) // विशिष्ट मदों की संख्या (एन) // बस्ता क्षमता (डब्ल्यू) // नोट: सरणी v और सरणी w को इंडेक्स 1 से शुरू होने वाले सभी प्रासंगिक मानों को संग्रहीत करने के लिए माना जाता है।

मूल्य परिभाषित करें [एन, डब्ल्यू]

सभी मान प्रारंभ करें [i, j] = -1

परिभाषित एम: = (आई, जे) // फ़ंक्शन एम को परिभाषित करें ताकि यह उस अधिकतम मूल्य का प्रतिनिधित्व करे जो हम शर्त के तहत प्राप्त कर सकते हैं: पहले आई आइटम का उपयोग करें, कुल वजन सीमा जे है {

   अगर मैं == 0 या जे <= 0 तो:
       मान [i, j] = 0
       वापस करना

   if (value[i-1, j] == -1) तो: // m[i-1, j] की गणना नहीं की गई है, हमें फ़ंक्शन m को कॉल करना होगा
       एम (आई -1, जे)

   अगर w[i] > j तो: // आइटम बैग में फिट नहीं हो सकता
       मान [i, j] = मान [i-1, j]
   अन्य:
       if (value[i-1, j-w[i == -1) तो: // m[i-1,j-w[i की गणना नहीं की गई है, हमें फ़ंक्शन m को कॉल करना होगा
           एम (आई-1, जे-डब्ल्यू [i])
       मान [i, j] = अधिकतम (मान [i-1, j], मान [i-1, jw[i + v[i])

}

एम (एन, डब्ल्यू) चलाएं </वाक्यविन्यास हाइलाइट>

उदाहरण के लिए, 10 अलग-अलग आइटम हैं और वज़न की सीमा 67 है। इसलिए,

$${\begin{aligned}&w[1]=23,w[2]=26,w[3]=20,w[4]=18,w[5]=32,w[6]=27,w[7]=29,w[8]=26,w[9]=30,w[10]=27\\&v[1]=505,v[2]=352,v[3]=458,v[4]=220,v[5]=354,v[6]=414,v[7]=498,v[8]=545,v[9]=473,v[10]=543\\\end{aligned}}$$

यदि आप गणना करने के लिए उपरोक्त विधि का उपयोग करते हैं $m(10,67)$, आपको यह प्राप्त होगा, उत्पन्न होने वाली कॉलों को छोड़कर $m(i,j)=0$:

इसके अलावा, हम रिकर्सन को तोड़ सकते हैं और इसे एक पेड़ में बदल सकते हैं। तब हम कुछ पत्तियों को काट सकते हैं और समानांतर कंप्यूटिंग का उपयोग करके इस पद्धति को चलाने में तेजी ला सकते हैं।

वस्तुओं के वास्तविक उपसमुच्चय को खोजने के लिए, केवल उनके कुल मूल्य के बजाय, हम इसे ऊपर दिए गए फ़ंक्शन को चलाने के बाद चला सकते हैं:<syntaxhighlight lang= c line= 1 > /**

* इष्टतम नैकपैक की वस्तुओं के सूचकांक लौटाता है।
* i: हम नैकपैक में 1 से i तक के आइटम शामिल कर सकते हैं
* जे: बैकपैक का अधिकतम वजन
*/

फ़ंक्शन नैपसैक (i: int, j: int): सेट <int> {

   अगर मैं == 0 तो:
       वापस करना {}
   अगर एम [आई, जे]> एम [आई -1, जे] तो:
       वापसी {i} ∪ बस्ता (i-1, j-w [i])
   अन्य:
       वापसी बस्ता (i-1, j)

}

बस्ता (एन, डब्ल्यू) </वाक्यविन्यास हाइलाइट>

बीच-बीच में मिलना

1974 में खोजे गए 0-1 नैकपैक के लिए एक और एल्गोरिदम और कभी-कभी मीट-इन-द-बीच हमले के समानांतर होने के कारण मीट-इन-द-बीच कहा जाता है, विभिन्न वस्तुओं की संख्या में घातीय है लेकिन डीपी एल्गोरिदम के लिए बेहतर हो सकता है जब $W$ n की तुलना में बड़ा है। विशेष रूप से, यदि $w_{i}$ गैर-नकारात्मक हैं लेकिन पूर्णांक नहीं हैं, हम अभी भी गतिशील प्रोग्रामिंग एल्गोरिदम का उपयोग स्केलिंग और राउंडिंग (यानी निश्चित-बिंदु अंकगणितीय का उपयोग करके) कर सकते हैं, लेकिन यदि समस्या की आवश्यकता है $d$ सही उत्तर पर पहुंचने के लिए परिशुद्धता के भिन्नात्मक अंक, $W$ द्वारा स्केल करने की आवश्यकता होगी $10^{d}$, और डीपी एल्गोरिदम की आवश्यकता होगी $O(W10^{d})$ अंतरिक्ष और $O(nW10^{d})$ समय।

एल्गोरिदम मीट-इन-द-बीच है
    इनपुट: वजन और मूल्यों के साथ वस्तुओं का एक सेट।
    आउटपुट: सबसेट का सबसे बड़ा संयुक्त मूल्य।

    सेट {1...n} को लगभग समान आकार के दो सेट A और B में विभाजित करें
    प्रत्येक सेट के सभी उपसमूहों के वजन और मूल्यों की गणना करें

    ए के प्रत्येक उपसमुच्चय के लिए करें
        सबसे बड़े मान का B का सबसेट ज्ञात करें जैसे कि संयुक्त वजन W से कम हो

    अब तक देखे गए सबसे बड़े संयुक्त मूल्य का ट्रैक रखें

एल्गोरिदम लेता है $O(2^{n/2})$ अंतरिक्ष, और चरण 3 के कुशल कार्यान्वयन (उदाहरण के लिए, वजन के आधार पर बी के सबसेट को छांटना, बी के सबसेट को छोड़ना जो अधिक या समान मूल्य के बी के अन्य सबसेट से अधिक वजन का होता है, और सर्वोत्तम मिलान खोजने के लिए बाइनरी खोज का उपयोग करना) परिणाम में का एक रनटाइम $O(n2^{n/2})$. जैसा कि क्रिप्टोग्राफी में मीट-इन-द-बीच हमले के साथ होता है, इसमें सुधार होता है $O(n2^{n})$ एक भोली क्रूर बल दृष्टिकोण का रनटाइम (सभी सबसेट की जांच $\{1...n\}$), स्थिर स्थान के बजाय घातांक का उपयोग करने की कीमत पर (बेबी-स्टेप जाइंट-स्टेप भी देखें)। मीट-इन-द-मिडल एल्गोरिद्म में कला सुधार की वर्तमान स्थिति, सबसेट सम के लिए श्रोएप्पल और शमीर के एल्गोरिथम से अंतर्दृष्टि का उपयोग करते हुए, नैपसैक के लिए एक यादृच्छिक एल्गोरिथम के रूप में प्रदान करता है जो $O^{*}(2^{n/2})$ (बहुपद कारकों तक) चलने का समय और अंतरिक्ष आवश्यकताओं को कम कर देता है $O^{*}(2^{0.249999n})$ (देखना उपप्रमेय 1.4).

सन्निकटन एल्गोरिदम

अधिकांश एनपी-पूर्ण समस्याओं के लिए, यह व्यावहारिक समाधान खोजने के लिए पर्याप्त हो सकता है, भले ही वे इष्टतम न हों। अधिमानतः, हालांकि, सन्निकटन समाधान के मूल्य और इष्टतम समाधान के मूल्य के बीच अंतर की गारंटी के साथ आता है।

कई उपयोगी लेकिन कम्प्यूटेशनल रूप से जटिल एल्गोरिदम के साथ, एल्गोरिदम बनाने और विश्लेषण करने पर पर्याप्त शोध किया गया है जो एक समाधान का अनुमान लगाता है। नैपसैक समस्या, हालांकि एनपी-हार्ड, एल्गोरिदम के संग्रह में से एक है जिसे अभी भी किसी निर्दिष्ट डिग्री तक अनुमानित किया जा सकता है। इसका मतलब है कि समस्या में एक बहुपद समय सन्निकटन योजना है। सटीक होने के लिए, नैकपैक समस्या में एक पूर्ण बहुपद समय सन्निकटन योजना (FPTAS) है।

लालची सन्निकटन एल्गोरिथम

जॉर्ज डेंजिग ने अनबाउंड नैपसैक समस्या को हल करने के लिए एक लालची एल्गोरिथम सन्निकटन एल्गोरिथम प्रस्तावित किया। उनका संस्करण वजन की प्रति इकाई मूल्य के घटते क्रम में वस्तुओं को क्रमबद्ध करता है, $v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}$. यह तब उन्हें बोरी में डालने के लिए आगे बढ़ता है, पहले प्रकार के आइटम की जितनी संभव हो उतनी प्रतियों के साथ शुरू होता है जब तक कि बोरी में और अधिक जगह न हो। बशर्ते कि प्रत्येक प्रकार की वस्तु की असीमित आपूर्ति हो, यदि $m$ बोरी में फिट होने वाली वस्तुओं का अधिकतम मूल्य है, तो लालची एल्गोरिदम कम से कम मूल्य प्राप्त करने की गारंटी देता है $m/2$.

परिबद्ध समस्या के लिए, जहाँ प्रत्येक प्रकार की वस्तु की आपूर्ति सीमित है, उपरोक्त एल्गोरिथम इष्टतम से बहुत दूर हो सकता है। फिर भी, एक साधारण संशोधन हमें इस मामले को हल करने की अनुमति देता है: सादगी के लिए मान लें कि सभी आइटम व्यक्तिगत रूप से बोरे में फिट होते हैं ($w_{i}\leq W$ सभी के लिए $i$). एक समाधान तैयार करें $S_{1}$ यथासंभव लंबे समय तक वस्तुओं को लालच से पैक करके, अर्थात। $S_{1}=\left\{1,\ldots ,k\right\}$ कहाँ $k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W$. इसके अलावा, एक दूसरा समाधान बनाएँ $S_{2}=\left\{k+1\right\}$ जिसमें पहला आइटम फिट नहीं हुआ। तब से $S_{1}\cup S_{2}$ समस्या की रैखिक प्रोग्रामिंग छूट के लिए एक ऊपरी सीमा प्रदान करता है, सेट में से एक का मूल्य कम से कम होना चाहिए $m/2$; हम इस प्रकार जो भी लौटाते हैं $S_{1}$ और $S_{2}$ प्राप्त करने के लिए बेहतर मूल्य है $1/2$-सन्निकटन।

यह दिखाया जा सकता है कि औसत प्रदर्शन त्रुटि दर पर वितरण में इष्टतम समाधान में परिवर्तित हो जाता है $n^{-1/2}$

पूरी तरह से बहुपद समय सन्निकटन योजना

नैपसैक समस्या के लिए पूरी तरह से बहुपद समय सन्निकटन योजना (एफपीटीएएस) इस तथ्य का लाभ उठाती है कि समस्या का कोई ज्ञात बहुपद समय समाधान नहीं है क्योंकि वस्तुओं से जुड़े लाभ प्रतिबंधित नहीं हैं। यदि कोई लाभ मूल्यों के कम से कम महत्वपूर्ण अंकों में से कुछ को गोल करता है तो वे एक बहुपद और 1/ε से बंधे होंगे जहां ε समाधान की शुद्धता पर बाध्य है। इस प्रतिबंध का मतलब है कि एक एल्गोरिदम बहुपद समय में समाधान ढूंढ सकता है जो इष्टतम समाधान के (1-ε) के कारक के भीतर सही है।

एल्गोरिथम FPTAS है

    इनपुट: ε ∈ (0,1]
           एन वस्तुओं की सूची ए, उनके मूल्यों द्वारा निर्दिष्ट, $v_{i}$, और वजन
    आउटपुट: S' FPTAS समाधान

    पी: = अधिकतम $\{v_{i}\mid 1\leq i\leq n\}$ // उच्चतम आइटम मूल्य
    कः= ε ${\frac {P}{n}}$

मैं 1 से एन के लिए करते हैं $v'_{i}$ := $\left\lfloor {\frac {v_{i}}{K}}\right\rfloor$ के लिए समाप्त

    समाधान वापस करें, S', का उपयोग करके $v'_{i}$ ऊपर उल्लिखित गतिशील कार्यक्रम में मान

प्रमेय: सेट $S'$ उपरोक्त एल्गोरिथम द्वारा गणना संतुष्ट करती है $\mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})$, कहाँ $S^{*}$ एक इष्टतम उपाय है।

प्रभुत्व संबंध

असीमित नैपसेक समस्या का समाधान उन वस्तुओं को फेंक कर आसान बनाया जा सकता है जिनकी कभी आवश्यकता नहीं होगी। किसी दिए गए आइटम के लिए $i$, मान लें कि हमें आइटम्स का एक सेट मिल सकता है $J$ जैसे कि उनका कुल वजन के वजन से कम है $i$, और उनका कुल मान के मान से अधिक है $i$. तब $i$ इष्टतम समाधान में प्रकट नहीं हो सकता है, क्योंकि हम हमेशा किसी भी संभावित समाधान में सुधार कर सकते हैं $i$ प्रतिस्थापित करके $i$ सेट के साथ $J$. इसलिए हम अवहेलना कर सकते हैं $i$-वें आइटम पूरी तरह से। इस तरह के मामलों में, $J$ हावी बताया जाता है $i$. (ध्यान दें कि यह बाउंडेड नैकपैक समस्याओं पर लागू नहीं होता है, क्योंकि हो सकता है कि हम पहले ही आइटम का उपयोग कर चुके हों $J$.)

प्रभुत्व संबंध ढूँढना हमें खोज स्थान के आकार को महत्वपूर्ण रूप से कम करने की अनुमति देता है। कई अलग-अलग प्रकार के प्रभुत्व संबंध हैं,जो सभी फॉर्म की असमानता को पूरा करते हैं:

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$, और $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ कुछ के लिए $x\in Z_{+}^{n}$ कहाँ $\alpha \in Z_{+}\,,J\subsetneq N$ और $i\not \in J$. सदिश $x$ के प्रत्येक सदस्य की प्रतियों की संख्या को दर्शाता है $J$.

सामूहिक प्रभुत्व: $i$वें>-वें आइटम का सामूहिक रूप से प्रभुत्व है $J$, के रूप में लिखा गया है $i\ll J$, यदि मदों के कुछ संयोजन का कुल भार $J$ डब्ल्यू से कम है_iऔर उनका कुल मान v से अधिक है_i. औपचारिक रूप से, $\sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}$ और $\sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ कुछ के लिए $x\in Z_{+}^{n}$, अर्थात। $\alpha =1$. इस प्रभुत्व को सत्यापित करना कम्प्यूटेशनल रूप से कठिन है, इसलिए इसका उपयोग केवल एक गतिशील प्रोग्रामिंग दृष्टिकोण के साथ किया जा सकता है। वास्तव में, यह एक छोटी नैकपैक निर्णय समस्या को हल करने के बराबर है $V=v_{i}$, $W=w_{i}$, और आइटम प्रतिबंधित हैं $J$. दहलीज प्रभुत्व: $i$वां>-वां आइटम दहलीज का प्रभुत्व है $J$, के रूप में लिखा गया है $i\prec \prec J$, अगर कुछ प्रतियों की संख्या $i$ का बोलबाला है $J$. औपचारिक रूप से, $\sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$, और $\sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ कुछ के लिए $x\in Z_{+}^{n}$ और $\alpha \geq 1$. यह सामूहिक प्रभुत्व का एक सामान्यीकरण है, जिसे पहली बार में पेश किया गया थाऔर EDUK एल्गोरिथ्म में उपयोग किया जाता है। सबसे छोटा ऐसा $\alpha$ आइटम की दहलीज को परिभाषित करता है $i$, लिखा हुआ $t_{i}=(\alpha -1)w_{i}$. इस मामले में, इष्टतम समाधान में अधिकतम शामिल हो सकता है $\alpha -1$ की प्रतियां $i$. एकाधिक प्रभुत्व: $i$वें>-वें आइटम में एक ही आइटम का गुणन होता है $j$, के रूप में लिखा गया है $i\ll _{m}j$, अगर $i$ की कुछ प्रतियों का प्रभुत्व है $j$. औपचारिक रूप से, $w_{j}\,x_{j}\ \leq w_{i}$, और $v_{j}\,x_{j}\ \geq v_{i}$ कुछ के लिए $x_{j}\in Z_{+}$ अर्थात। $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$. प्रीप्रोसेसिंग के दौरान इस प्रभुत्व का कुशलता से उपयोग किया जा सकता है क्योंकि इसका अपेक्षाकृत आसानी से पता लगाया जा सकता है। मॉड्यूलर प्रभुत्व: चलो $b$ सर्वोत्तम वस्तु हो, अर्थात् ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ सभी के लिए $i$. यह मूल्य के सबसे बड़े घनत्व वाला आइटम है। $i$th>-th आइटम मॉड्यूलर रूप से एकल आइटम का प्रभुत्व है $j$, के रूप में लिखा गया है $i\ll _{\equiv }j$, अगर $i$ का बोलबाला है $j$ साथ ही की कई प्रतियाँ $b$. औपचारिक रूप से, $w_{j}+tw_{b}\leq w_{i}$, और $v_{j}+tv_{b}\geq v_{i}$ अर्थात। $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$.

विविधताएं

Main article: List of knapsack problems

नैकपैक समस्या के कई रूप हैं जो मूल समस्या के अनुप्रयोगों की विशाल संख्या से उत्पन्न हुए हैं। मुख्य विविधताएं कुछ समस्या पैरामीटरों की संख्या जैसे मदों की संख्या, उद्देश्यों की संख्या, या यहां तक ​​कि नैपैक्स की संख्या को बदलकर उत्पन्न होती हैं।

बहुउद्देश्यीय नैकपैक समस्या

यह भिन्नता थैला भरने वाले व्यक्ति के लक्ष्य को बदल देती है। एक उद्देश्य के बजाय, जैसे कि मौद्रिक लाभ को अधिकतम करना, उद्देश्य के कई आयाम हो सकते हैं। उदाहरण के लिए, पर्यावरण या सामाजिक सरोकार के साथ-साथ आर्थिक लक्ष्य भी हो सकते हैं। जिन समस्याओं को अक्सर संबोधित किया जाता है उनमें पोर्टफोलियो और परिवहन रसद अनुकूलन शामिल हैं। उदाहरण के तौर पर, मान लीजिए कि आप एक क्रूज जहाज चलाते हैं। आपको यह तय करना होगा कि कितने प्रसिद्ध कॉमेडियन को हायर करना है। यह नाव एक टन से अधिक यात्रियों को नहीं संभाल सकती है और मनोरंजन करने वालों का वजन 1000 पाउंड से कम होना चाहिए। प्रत्येक कॉमेडियन का वजन होता है, उनकी लोकप्रियता के आधार पर व्यवसाय में लाता है और एक विशिष्ट वेतन मांगता है। इस उदाहरण में, आपके पास कई उद्देश्य हैं। बेशक, आप अपने मनोरंजनकर्ताओं की लोकप्रियता को अधिकतम करना चाहते हैं जबकि उनके वेतन को कम करना चाहते हैं। साथ ही, आप अधिक से अधिक मनोरंजनकर्ता चाहते हैं।

बहुआयामी नैकपैक समस्या

इस भिन्नता में, थैला आइटम का वजन $i$ एक डी-आयामी वेक्टर द्वारा दिया गया है ${\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})$ और नैकपैक में एक डी-आयामी क्षमता वेक्टर है $(W_{1},\ldots ,W_{D})$. लक्ष्य थैले में वस्तुओं के मूल्यों के योग को अधिकतम करना है ताकि प्रत्येक आयाम में वजन का योग हो $d$ बढ़ता नहीं है $W_{d}$.

बहु-आयामी नैकपैक कम्प्यूटेशनल रूप से नैपसैक की तुलना में कठिन है; यहां तक ​​के लिए $D=2$, समस्या में EPTAS तब तक नहीं है जब तक कि P$=$ई.जी. हालाँकि, एल्गोरिथ्म में विरल उदाहरणों को कुशलता से हल करने के लिए दिखाया गया है। एक सेट होने पर बहु-आयामी नैकपैक का एक उदाहरण विरल है $J=\{1,2,\ldots ,m\}$ के लिए $m<D$ ऐसा है कि हर थैला आइटम के लिए $i$, $\exists z>m$ ऐसा है कि $\forall j\in J\cup \{z\},\ w_{ij}\geq 0$ और $\forall y\notin J\cup \{z\},w_{iy}=0$. उदाहरण के लिए, रिले नोड्स के साथ वायरलेस नेटवर्क में पैकेट शेड्यूल करते समय ऐसी घटनाएं होती हैं।से एल्गोरिथममल्टीपल चॉइस वैरिएंट, मल्टीपल चॉइस मल्टी-डायमेंशनल नैपसैक के विरल उदाहरणों को भी हल करता है।

IHS (बढ़ती ऊंचाई शेल्फ़) एल्गोरिथम 2D नैकपैक (वर्गों को द्वि-आयामी इकाई आकार वर्ग में पैक करना) के लिए इष्टतम है: जब एक इष्टतम पैकिंग में अधिकतम पाँच वर्ग होते हैं।

एकाधिक बस्ता समस्या

यह भिन्नता बिन पैकिंग समस्या के समान है। यह बिन पैकिंग समस्या से भिन्न है जिसमें वस्तुओं का एक सबसेट चुना जा सकता है, जबकि बिन पैकिंग समस्या में, सभी वस्तुओं को कुछ डिब्बे में पैक करना पड़ता है। अवधारणा यह है कि कई थैले हैं। यह एक तुच्छ परिवर्तन की तरह लग सकता है, लेकिन यह प्रारंभिक नैकपैक की क्षमता को जोड़ने के बराबर नहीं है। इस भिन्नता का उपयोग ऑपरेशंस रिसर्च में कई लोडिंग और शेड्यूलिंग समस्याओं में किया जाता है और इसमें बहुपद-समय सन्निकटन योजना है।

द्विघाती नैपसैक समस्या

द्विघातीय नैपसैक समस्या द्विघाती और रेखीय क्षमता प्रतिबंधों के अधीन द्विघात उद्देश्य फलन को अधिकतम करती है। समस्या को 1980 में गैलो, हैमर और शिमोन द्वारा पेश किया गया था। हालाँकि, समस्या का पहला उपचार 1975 में विट्जगल में हुआ था।

सबसेट-योग समस्या

सबसेट योग समस्या निर्णय का एक विशेष मामला है और 0-1 समस्याएं हैं जहां प्रत्येक प्रकार की वस्तु, वजन मूल्य के बराबर होती है: $w_{i}=v_{i}$. क्रिप्टोग्राफी के क्षेत्र में, नैकपैक समस्या शब्द का प्रयोग अक्सर विशेष रूप से सबसेट योग समस्या को संदर्भित करने के लिए किया जाता है और इसे आमतौर पर कार्प की 21 एनपी-पूर्ण समस्याओं में से एक के रूप में जाना जाता है। उपसमुच्चय योग समस्या के सामान्यीकरण को बहु उपसमुच्चय सम समस्या कहते हैं, जिसमें समान क्षमता वाले अनेक डिब्बे मौजूद होते हैं। यह दिखाया गया है कि सामान्यीकरण में FPTAS नहीं है।

ज्यामितीय नैकपैक समस्या

ज्यामितीय नैपसैक समस्या में, विभिन्न मानों के साथ आयतों का एक समूह है, और एक आयताकार नैकपैक है। लक्ष्य सबसे बड़ा संभव मान नैकपैक में पैक करना है।

यह भी देखें

• बिन पैकिंग समस्या
• परिवर्तन करने की समस्या
• मिश्रित नीलामी
• संयुक्त अनुकूलन
• लगातार नैकपैक की समस्या
• स्टॉक की समस्या में कटौती
• बस्ता समस्याओं की सूची
• पैकिंग की समस्या

टिप्पणियाँ

संदर्भ

• Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP9, pg.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer. doi:10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. MR 2161720. S2CID 28836720.
• Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer implementations. Wiley-Interscience. ISBN 978-0-471-92420-3. MR 1086874.

बाहरी संबंध

• Lecture slides on the knapsack problem
• PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem, with code taking advantage of the dominance relations in an hybrid algorithm, benchmarks and downloadable copies of some papers.
• Home page of David Pisinger with downloadable copies of some papers on the publication list (including "Where are the hard knapsack problems?")
• Knapsack Problem solutions in many languages at Rosetta Code
• Dynamic Programming algorithm to 0/1 Knapsack problem
• Knapsack Problem solver (online)
• Solving 0-1-KNAPSACK with Genetic Algorithms in Ruby Archived 23 May 2011 at the Wayback Machine
• Codes for Quadratic Knapsack Problem Archived 14 February 2015 at the Wayback Machine

• Optimizing Three-Dimensional Bin Packing
• Knapsack Integer Programming Solution in Python Gekko (optimization software)