उपसमुच्चय योग समस्या: Difference between revisions

Latest revision as of 14:01, 28 July 2023

उपसमुच्चय योग समस्या (एसएसपी) कंप्यूटर विज्ञान में निर्णय समस्या है। इसके सबसे सामान्य सूत्रीकरण में, मल्टीसेट है इस प्रकार $S$ पूर्णांकों और लक्ष्य-योग का $T$ , और प्रश्न यह तय करना है कि क्या पूर्णांकों का कोई उपसमुच्चय स्पष्ट रूप $T$ से योग करता है .^[1] समस्या को np कठिन माना जाता है। इसके अतिरिक्त, इसके कुछ प्रतिबंधित संस्करण np-पूर्णता या np-पूर्ण भी हैं, उदाहरण के लिए:^[1]

वह वैरिएंट जिसमें सभी इनपुट धनात्मक हैं।
वह प्रकार जिसमें इनपुट धनात्मक या ऋणात्मक हो सकते हैं, और $T=0$ . उदाहरण के लिए, समुच्चय $\{-7,-3,-2,9000,5,8\}$ दिया गया है , उत्तर हाँ है क्योंकि उपसमुच्चय $\{-3,-2,5\}$ योग शून्य है.
वह वैरिएंट जिसमें सभी इनपुट धनात्मक हैं, और लक्ष्य योग सभी इनपुट के योग का पुर्णतः अर्ध है, अर्थात, $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ . एसएसपी के इस विशेष स्थिति को विभाजन समस्या के रूप में जाना जाता है।

एसएसपी को अनुकूलन समस्या के रूप में भी माना जा सकता है: उपसमुच्चय खोजे जिसका योग अधिकतम T है, और उसके अधीन, जितना संभव हो T के निकट होता है। यह np-हार्ड है, किन्तु कई एल्गोरिदम हैं जो इसे उचित रूप से जल्दी से हल कर सकते हैं।

एसएसपी नैपसैक समस्या और एकाधिक उपसमुच्चय योग समस्या का विशेष स्थिति है।

कम्प्यूटेशनल कठोरता

एसएसपी की रन-टाइम जटिलता दो मापदंडों पर निर्भर करती है:

n - इनपुट पूर्णांकों की संख्या. यदि n छोटी निश्चित संख्या है, तो समाधान के लिए विस्तृत खोज व्यावहारिक है।
L - समस्या की स्पष्टता, समस्या को बताने के लिए लगने वाले द्विअर्धरी समिष्टीय मानों की संख्या के रूप में बताई गई है। यदि L छोटी निश्चित संख्या है, तो गतिशील प्रोग्रामिंग एल्गोरिदम हैं जो इसे स्पष्ट रूप से हल कर सकते हैं।

जैसे-जैसे n और L दोनों बड़े होते जाते हैं, एसएसपी NP-हार्ड होता है। सबसे प्रसिद्ध एल्गोरिदम की जटिलता दो मापदंडों n और L में से छोटे में घातीय समय है। समस्या np-हार्ड है, तब भी जब सभी इनपुट पूर्णांक धनात्मक होते हैं (और लक्ष्य-योग T इनपुट का भाग है)। इसे 3सैट से प्रत्यक्ष कमी द्वारा सिद्ध किया जा सकता है।^[2] इसे 3-आयामी मिलान (3डीएम) से कमी करके भी सिद्ध किया जा सकता है:^[3]

हमें 3डीएम का उदाहरण दिया गया है, जहां शीर्ष समुच्चय W, X, Y हैं। प्रत्येक समुच्चय में n शीर्ष हैं। वहाँ m किनारे हैं, जहाँ प्रत्येक किनारे में W,₂(m+1)), जिससे L किनारों की संख्या का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की संख्या से बड़ा हो।
हम m धनात्मक पूर्णांकों के साथ एसएसपी का उदाहरण बनाते हैं। पूर्णांकों का वर्णन उनके द्विअर्धरी निरूपण द्वारा किया जाता है। प्रत्येक इनपुट पूर्णांक को 3nL बिट्स द्वारा दर्शाया जा सकता है, जिसे L बिट्स के 3n ज़ोन में विभाजित किया गया है। प्रत्येक क्षेत्र शीर्ष से मेल खाता है।
3डीएम उदाहरण में प्रत्येक किनारे (w,x,y) के लिए, एसएसपी उदाहरण में पूर्णांक होता है, जिसमें पुर्णतः तीन बिट्स 1 होते हैं: शीर्ष w, x, और y के क्षेत्रों में सबसे कम महत्वपूर्ण बिट्स . उदाहरण के लिए, यदि n=10 और L=3, और W=(0,...,9), X=(10,...,19), Y=(20,...,29), तो किनारे (0, 10, 20) को संख्या (2⁰+2³⁰+2⁶⁰) द्वारा दर्शाया गया है.
एसएसपी उदाहरण में लक्ष्य योग T को प्रत्येक क्षेत्र के सबसे कम-महत्वपूर्ण बिट में 1 के साथ पूर्णांक पर समुच्चय किया गया है, अर्थात (2)⁰+2¹+...+2^3n-1).
यदि 3डीएम उदाहरण में पूर्ण मिलान है, जिससे एसएसपी उदाहरण में संबंधित पूर्णांकों का योग पुर्णतः T प्राप्त करता है।
इसके विपरीत, यदि एसएसपी उदाहरण में पुर्णतः T योग के साथ उपसमुच्चय है, तो, चूंकि क्षेत्र पर्याप्त रूप से बड़े हैं जिससे क्षेत्र से दूसरे क्षेत्र में कोई समिष्टांतरण नही होता है, योग को 3डीएम उदाहरण में पूर्ण मिलान के अनुरूप होना चाहिए।

निम्नलिखित वेरिएंट को np-हार्ड के रूप में भी जाना जाता है:

इनपुट पूर्णांक धनात्मक और ऋणात्मक दोनों हो सकते हैं, और लक्ष्य-योग T = 0. इसे धनात्मक पूर्णांक वाले वैरिएंट से घटाकर सिद्ध किया जा सकता है। उस वैरिएंट को उपसमुच्चयसमपॉजिटिव से और वर्तमान वैरिएंट को उपसमुच्चय योग शून्य से निरूपित करें। उपसमुच्चयसमपॉजिटिव के उदाहरण (S, T) को देखते हुए,T मान के साथ तत्व जोड़कर उपसमुच्चय योग शून्य का उदाहरण बनाएं। उपसमुच्चयसमपॉजिटिव उदाहरण के समाधान को देखते हुए,T जोड़ने से उपसमुच्चय योग शून्य उदाहरण का समाधान प्राप्त होता है। इसके विपरीत, उपसमुच्चय योग शून्य उदाहरण के समाधान को देखते हुए, इसमें T होना चाहिए (चूंकि S में सभी पूर्णांक धनात्मक हैं), इसलिए शून्य का योग प्राप्त करने के लिए, इसमें +T के योग के साथ S का उपसमुच्चय भी होना चाहिए, जो उपसमुच्चयसमपॉजिटिव उदाहरण का समाधान है।
इनपुट पूर्णांक धनात्मक हैं, और T = योग(s)/2। इसे सामान्य प्रकार से कमी करके भी सिद्ध किया जा सकता है; विभाजन समस्या देखें.

अनुरूप गणना समस्या एसएसपी, जो लक्ष्य के योग के लिए उपसमुच्चय की संख्या की गणना करने के लिए कहती है, शार्प पी पूर्ण है।^[4]

घातीय समय एल्गोरिदम

n में समय घातांक में एसएसपी को हल करने के कई विधि हैं।^[5]

समावेश-बहिष्करण

सबसे सरल समाधान एल्गोरिदम n संख्याओं के सभी उपसमूहों के माध्यम से चक्र करना होगा और, उनमें से प्रत्येक के लिए, यह जांचना होगा कि उपसमुच्चय का योग सही संख्या में है या नहीं है। चलने का समय $O(2^{n}\cdot n)$ व्यवस्थित है , क्योंकि वहां $2^{n}$ हैं उपसमुच्चय और, प्रत्येक उपसमुच्चय की जाँच करने के लिए, हमें अधिकतम n तत्वों का योग करना होता है।

एल्गोरिथ्म को बाइनरी ट्री की प्रथम खोज द्वारा कार्यान्वित किया जा सकता है: ट्री में प्रत्येक स्तर इनपुट संख्या से मेल खाता है; बायीं शाखा समुच्चय से संख्या को बाहर करने से मेल खाती है, और दाहिनी शाखा संख्या को सम्मिलित करने से मेल खाती है (इसलिए नाम समावेशन-बहिष्करण)। आवश्यक मेमोरी $O(n)$ है . रन-टाइम को कई अनुमानों द्वारा उत्तम बनाया जा सकता है:^[5]

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

होरोविट्ज़ और साहनी

1974 में, होरोविट्ज़ और सरताज साहनी ^[6] तेज़ घातीय-समय एल्गोरिदम प्रकाशित किया था, जो समय $O(2^{n/2}\cdot (n/2))$ में चलता है , किन्तु बहुत अधिक $O(2^{n/2})$ समिष्ट की आवश्यकता है एल्गोरिथ्म इच्छानुसार सही से n तत्वों को दो समुच्चयो में विभाजित करता है $n/2$ प्रत्येक इन दो समुच्चयो में से प्रत्येक के लिए, यह सभी $2^{n/2}$ के योगों की सूची संग्रहीत करता है इसके तत्वों के संभावित उपसमुच्चय फिर इन दोनों सूचियों में से प्रत्येक को क्रमबद्ध किया जाता है। यहां तक कि सबसे तेज़ तुलना सॉर्टिंग एल्गोरिदम का उपयोग करते हुए, इस चरण के लिए मर्जसॉर्ट को समय लगेगा $O(2^{n/2}n)$ . चूँकि, इसके लिए रकम की क्रमबद्ध सूची दी गई है $k$ तत्वों, सूची को (की प्रारंभ के साथ दो क्रमबद्ध सूचियों $k+1$ तक विस्तारित किया जा सकता है) तत्व, और इन दो क्रमबद्ध सूचियों को समय $O(2^{k})$ में मर्ज किया जा सकता है . इस प्रकार, प्रत्येक सूची को समय पर क्रमबद्ध $O(2^{n/2})$ रूप में तैयार किया जा सकता है . दो क्रमबद्ध सूचियों को देखते हुए, एल्गोरिदम जांच कर सकता है कि पहले सरणी का तत्व और दूसरे सरणी का तत्व समय में T तक है या $O(2^{n/2})$ नहीं है . ऐसा करने के लिए, एल्गोरिदम पहले एरे से घटते क्रम में (सबसे बड़े तत्व से प्रारंभ) और दूसरे एरे से बढ़ते क्रम में (सबसे छोटे तत्व से प्रारंभ) निकलता है। जब भी पहले एरे में वर्तमान तत्व और दूसरे एरे में वर्तमान तत्व का योग T से अधिक होता है, तो एल्गोरिदम पहले एरे में अगले तत्व पर चला जाता है। यदि यह T से कम है, तो एल्गोरिदम दूसरे सरणी में अगले तत्व पर चला जाता है। यदि T के योग वाले दो तत्व पाए जाते हैं, तो यह रुक जाता है। (दो तत्वों के योग की उप-समस्या को दो-योग के रूप में जाना जाता है।^[7])

श्रोएप्पेल और शमीर

1981 में, रिचर्ड श्रोएप्पेल और शमीर ने एल्गोरिदम प्रस्तुत किया था ^[8] होरोविट्ज़ और सानही पर अर्धरित, जिसके $O(2^{n/2}\cdot (n/4))$ लिए समान रनटाइम की आवश्यकता होती है बहुत कम समिष्ट - $O(2^{n/4})$ . n/2 तत्वों के सभी उपसमूहों को पहले से बनाने और संग्रहीत करने के अतिरिक्त, वे तत्वों को n/4 तत्वों के 4 समुच्चयो में विभाजित करते हैं, और न्यूनतम समूह का उपयोग करके गतिशील रूप से n/2 तत्व जोड़े के उपसमुच्चय उत्पन्न करते हैं, जो उपरोक्त समय प्राप्त करता है और अंतरिक्ष की जटिलताएँ क्योंकि यह किया जा सकता है इस प्रकार $O(k^{2}\log(k))$ और समिष्ट $O(k)$ लंबाई k की 4 सूचियाँ दी गई हैं।

समिष्ट आवश्यकताओं के कारण, एचएस एल्गोरिदम लगभग 50 पूर्णांकों तक के लिए व्यावहारिक है, और एसएस एल्गोरिदम 100 पूर्णांकों तक के लिए व्यावहारिक है।^[5]

हाउग्रेव-ग्राहम और जौक्स

2010 में, हाउग्रेव-ग्राहम और जौक्स ^[9] संभाव्य एल्गोरिथ्म प्रस्तुत किया जो पिछले सभी एल्गोरिदम की तुलना में समय में तेजी से चलता है इस प्रकार $O(2^{.337n})$ समिष्ट का उपयोग करना $O(2^{.256n})$ . यह केवल निर्णय की समस्या को हल करता है, यह सिद्ध नहीं कर सकता कि किसी दिए गए योग का कोई समाधान नहीं है, और T के निकटतम उपसमुच्चय योग को वापस नहीं करता है।

हाउग्रेव-ग्राहम और जौक्स की तकनीकों को बाद में विस्तारित किया गया था ^[10] समय-जटिलता $O(2^{.291n})$ का उपयोग किया जाता है .

छद्म-बहुपद समय गतिशील प्रोग्रामिंग समाधान

गतिशील प्रोग्रामिंग का उपयोग करके एसएसपी को छद्म-बहुपद समय में हल किया जा सकता है। मान लीजिए कि हमारे पास उदाहरण में तत्वों का निम्नलिखित क्रम है:

x_{1},\ldots ,x_{N}

हम अवस्था को पूर्णांकों के युग्म (i, s) के रूप में परिभाषित करते हैं। यह स्तर इस बात का प्रतिनिधित्व करता है कि अरिक्त उपसमुच्चय $x_{1},\ldots ,x_{i}$ है जो $s$ बताता है .

प्रत्येक स्तर (i, s) के दो अगले स्तर हैं:

(i+1, s), जिसका अर्थ $x_{i+1}$ है उपसमूह में सम्मिलित नहीं है;
(i+1, s+ $x_{i+1}$ ), जिसका अर्थ $x_{i+1}$ है उपसमुच्चय में सम्मिलित है।

प्रारंभिक स्थिति (0, 0) से प्रारंभ करके, स्थिति (n, t) की खोज के लिए किसी भी ग्राफ़ खोज एल्गोरिदम (उदाहरण के लिए चौड़ाई-पहली खोज) का उपयोग करना संभव है। यदि स्थिति पाई जाती है, तो पीछे जाकर हम पुर्णतः T के योग के साथ उपसमुच्चय पा सकते हैं।

इस एल्गोरिदम का रन-टाइम स्तरों की संख्या में अधिकतम रैखिक है। स्तरों की संख्या विभिन्न संभावित योगों की संख्या से अधिकतम N गुना है। माना $A$ ऋणात्मक मानों का योग हो और $B$ धनात्मक मानों का योग; विभिन्न संभावित योगों की संख्या अधिकतम B-A है, इसलिए कुल रनटाइम $O(N(B-A))$ है . उदाहरण के लिए, यदि सभी इनपुट मान धनात्मक हैं और कुछ स्थिरांक C से बंधे हैं, तो B अधिकतम N C है, इसलिए आवश्यक समय $O(N^{2}C)$ है .

यह समाधान जटिलता सिद्धांत में बहुपद समय के रूप में नहीं गिना जाता है क्योंकि $B-A$ समस्या के आकार में बहुपद नहीं है, जो कि इसे दर्शाने के लिए उपयोग की जाने वाली बिट्स की संख्या है। यह एल्गोरिथम के मानों $A$ और $B$ में बहुपद है, जो बिट्स की संख्या में घातीय हैं। चूँकि, यूनरी में n कोड किया गया उपसमुच्चय योग P में है, तब से n कोडिंग का आकार B-A में रैखिक है। इसलिए, उपसमुच्चय योग केवल अशक्त np-पूर्ण है।

इस स्थिति के लिए कि प्रत्येक $x_{i}$ धनात्मक है और निश्चित स्थिरांक $C$ से घिरा है , 1999 में, पिसिंगर ने समय जटिलता वाला रैखिक समय एल्गोरिदम पाया $O(NC)$ (ध्यान दें कि यह समस्या के उस संस्करण के लिए है जहां लक्ष्य योग आवश्यक रूप से शून्य नहीं है, अन्यथा समस्या तुच्छ होगी)।^[11] 2015 में, कोइलियारिस और जू ने नियतिवादी पाया ${\tilde {O}}(T{\sqrt {N}})$ उपसमुच्चय योग समस्या के लिए एल्गोरिदम जहां $T$ वह योग है जिसे हमें खोजने की आवश्यकता है।^[12] 2017 में, ब्रिंगमैन ने यादृच्छिक पाया ${\tilde {O}}(T+N)$ समय एल्गोरिथ्म.^[13] 2014 में, कर्टिस और सांचेस ने सिमड मशीनों में अत्यधिक स्केलेबल सरल रिकर्सन पाया गया था $O(N(m-x_{\min })/p)$ समय और $O(N+m-x_{\min })$ समिष्ट, जहाँ $p$ प्रसंस्करण तत्वों की संख्या है, इस प्रकार $m=\min(s,\sum x_{i}-s)$ और $x_{\min }$ निम्नतम पूर्णांक है.^[14] यह अब तक ज्ञात सर्वोत्तम सैद्धांतिक समानांतर जटिलता है।

व्यावहारिक परिणामों की तुलना और एसएसपी के कठिन उदाहरणों के समाधान पर कर्टिस और सांचेस द्वारा चर्चा की गई है।^[15]

बहुपद समय सन्निकटन एल्गोरिदम

मान लीजिए कि सभी इनपुट धनात्मक हैं। एसएसपी के लिए सन्निकटन एल्गोरिदम का लक्ष्य अधिकतम T के योग और इष्टतम योग के कम से कम आर गुना के साथ एस का उपसमूह खोजना है, जहां आर (0,1) में संख्या है जिसे सन्निकटन अनुपात कहा जाता है।

सरल 1/2-अनुमान

निम्नलिखित अत्यंत सरल एल्गोरिदम का अनुमानित अनुपात 1/2 है:^[16]

इनपुट को घटते मूल्य के अर्धर पर क्रमबद्ध करें;
अगले सबसे बड़े इनपुट को उपसमुच्चय में रखें, जब तक वह वहां फिट बैठता है।

जब यह एल्गोरिदम समाप्त हो जाता है, तो या तो सभी इनपुट उपसमुच्चय में होते हैं (जो स्पष्ट रूप से इष्टतम है), या इनपुट है जो फिट नहीं होता है। ऐसा पहला इनपुट पिछले सभी इनपुट से छोटा है जो उपसमुच्चय में हैं और उपसमुच्चय में इनपुट का योग T/2 से अधिक है अन्यथा इनपुट भी T/2 से कम है और यह समुच्चय में फिट होता है। T/2 से अधिक ऐसी राशि स्पष्ट रूप से ऑप्ट/2 से अधिक है।

पूर्ण-बहुपद समय सन्निकटन योजना

निम्नलिखित एल्गोरिदम प्रत्येक $\epsilon >0$ के लिए प्राप्त करता है , $(1-\epsilon )$ का अनुमानित अनुपात . इसका रन टाइम $n$ और $1/\epsilon$ बहुपद है. याद रखें कि n इनपुट की संख्या है और T उपसमुच्चय योग की ऊपरी सीमा है।

initialize a list L to contain one element 0.

for each i from 1 to n do
    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
    sort Ui in ascending order
    make L empty 
    let y be the smallest element of Ui
    add y to L
    for each element z of Ui in increasing order do
        // Trim the list by eliminating numbers close to one another
        // and throw out elements greater than the target sum T.
        if y +  ε T/n < z ≤ T then
            y = z
            add z to L

return the largest element in L.

ध्यान दें कि ट्रिमिंग चरण (प्रत्येक लूप के लिए आंतरिक) के बिना, सूची L में सभी $2^{n}$ का योग सम्मिलित होगा इनपुट के उपसमुच्चय. ट्रिमिंग चरण दो काम करता है:

यह सुनिश्चित करता है कि L में शेष सभी राशियाँ T से नीचे हैं, इसलिए वे उप-योग समस्या का व्यवहार्य समाधान हैं।
यह सुनिश्चित करता है कि सूची L विरल है, अर्थात, प्रत्येक दो निरंतर आंशिक-योगों के बीच $\epsilon T/n$ का अंतर कम से कम है .

ये गुण मिलकर सूची की आश्वासन देते हैं $L$ से अधिक $n/\epsilon$ तत्व नहीं है; इसलिए रन-टाइम $n/\epsilon$ बहुपद है .

जब एल्गोरिदम समाप्त होता है, यदि इष्टतम $L$ योग होता है , फिर इसे वापस कर दिया जाता है और हमारा काम हो जाता है। अन्यथा, इसे पिछले ट्रिमिंग चरण में हटा दिया गया होता है। प्रत्येक ट्रिमिंग चरण अधिकतम योगात्मक त्रुटि $\epsilon T/n$ प्रस्तुत करता है , इसलिए $n$ चरण साथ अधिकतम की त्रुटि प्रस्तुत करते हैं . इसलिए, ${\text{OPT}}-\epsilon T$ लौटाया गया समाधान कम से कम है जो $(1-\epsilon ){\text{OPT}}$ कम से कम है .

उपरोक्त एल्गोरिदम उस स्थिति में एसएसपी का स्पष्ट समाधान प्रदान करता है जब इनपुट संख्या छोटी (और गैर-ऋणात्मक) होती है। यदि संख्याओं का कोई योग अधिक से अधिक $P$ बिट्स निर्दिष्ट किया जा सकता है, फिर समस्या को लगभग हल करना $\epsilon =2^{-P}$ है इसे पुर्णतः हल करने के समान है। फिर, अनुमानित उपसमुच्चय के लिए बहुपद समय एल्गोरिथ्म रनिंग टाइम बहुपद के साथ स्पष्ट एल्गोरिदम $n$ और $2^{P}$ बन जाता है (अर्थात, घातीय में $P$ ).

केलरर, मैनसिनी, पफ़रस्की और स्पेरान्ज़ा ^[17] और केलरर, पफ़रस्की और पिसिंगर ^[18] उपसमुच्चय राशि के लिए अन्य एफपीटीएएस-s प्रस्तुत करें।

यह भी देखें

नैपसेक समस्या - एसएसपी का सामान्यीकरण जिसमें प्रत्येक इनपुट आइटम का मूल्य और वजन दोनों होता है। लक्ष्य मूल्य को अधिकतम करना है जिससे कुल वजन सीमित हो जाता है।
एकाधिक उपसमुच्चय योग समस्या - एसएसपी का सामान्यीकरण जिसमें व्यक्ति को कई उपसमुच्चय चुनने चाहिए।
3योग
मर्कल-हेलमैन नैपसेक क्रिप्टोसिस्टम

संदर्भ

↑ ^1.0 ^1.1 Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिज़ाइन (2nd ed.). p. 491. ISBN 0-321-37291-3.
↑ Goodrich, Michael. "अधिक एनपी पूर्ण और एनपी कठिन समस्याएं" (PDF). Archived (PDF) from the original on 2022-10-09.
↑ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, Section 3.1 and problem SP1 in Appendix A.3.1.
↑ Filmus, Yuval (30 January 2016). Answer to: "Is there a known, fast algorithm for counting all subsets that sum to below a certain number?". Theoretical Computer Science Stack Exchange. Note that Filmus' citation in support of the claim (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison". Theoretical Computer Science. Elsevier. 410: 101-107. DOI 10.1016/j.tcs.2008.09.034) does not in fact prove the claim, instead directing readers to another citation (Papadimitriou, Christos (1994). Computational Complexity. Addison-Wesley: Reading, MA. Chapter 9. ISBN 0-201-53082-1 — via the Internet Archive), which does not explicitly prove the claim either. Papadimitriou's proof that SSP is NP-complete via reduction of 3SAT does, however, generalize to a reduction from #3SAT to #SSP.
↑ ^5.0 ^5.1 ^5.2 Richard E. Korf, Ethan L. Schreiber, and Michael D. Moffitt (2014). "इष्टतम अनुक्रमिक मल्टी-वे संख्या विभाजन" (PDF). Archived (PDF) from the original on 2022-10-09.{{cite web}}: CS1 maint: multiple names: authors list (link)
↑ Horowitz, Ellis; Sahni, Sartaj (1974). "नैपसैक समस्या के अनुप्रयोगों के साथ विभाजन की गणना करना" (PDF). Journal of the Association for Computing Machinery. 21 (2): 277–292. doi:10.1145/321812.321823. hdl:1813/5989. MR 0354006. S2CID 16866858. Archived (PDF) from the original on 2022-10-09.
↑ "दो-योग समस्या" (PDF). Archived (PDF) from the original on 2022-10-09.
↑ Schroeppel, Richard; Shamir, Adi (1981-08-01). "A $T = O (2 n /2)$ [[Category: Templates Vigyan Ready]], $S = O (2 n /4)$ [[Category: Templates Vigyan Ready]] algorithm for certain NP-complete problems". SIAM Journal on Computing. 10 (3): 456–464. doi:10.1137/0210033. ISSN 0097-5397. {{cite journal}}: URL–wikilink conflict (help)
↑ Howgrave-Graham, Nick; Joux, Antoine (2010). "New Generic Algorithms for Hard Knapsacks". In Gilbert, Henri (ed.). Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science (in English). Vol. 6110. Berlin, Heidelberg: Springer. pp. 235–256. doi:10.1007/978-3-642-13190-5_12. ISBN 978-3-642-13190-5.
↑ Becker, Anja; Joux, Antoine (2010). "Improved Generic Algorithms for Hard Knapsacks". In Gilbert, Henri (ed.). Advances in Cryptology – EUROCRYPT 2011. Lecture Notes in Computer Science (in English). Vol. 6632. Berlin, Heidelberg: Springer. pp. 364–385. doi:10.1007/978-3-642-20465-4_21. ISBN 978-3-642-20465-4.
↑ Pisinger, David (1999). "सीमित वजन के साथ बस्ता समस्याओं के लिए रैखिक समय एल्गोरिदम". Journal of Algorithms. 33 (1): 1–14. doi:10.1006/jagm.1999.1034. MR 1712690.
↑ Koiliaris, Konstantinos; Xu, Chao (2015-07-08). "सबसेट योग के लिए एक तेज़ छद्मबहुपद समय एल्गोरिदम". arXiv:1507.02318 [cs.DS].
↑ Bringmann, Karl (2017). "A near-linear pseudopolynomial time algorithm for subset sum". In Klein, Philip N. (ed.). Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). SIAM. pp. 1073–1084. arXiv:1610.04712. doi:10.1137/1.9781611974782.69.
↑ Curtis, V. V.; Sanches, C. A. A. (January 2016). "An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU". Concurrency and Computation: Practice and Experience. 28 (1): 95–113. doi:10.1002/cpe.3636. S2CID 20927927.
↑ Curtis, V. V.; Sanches, C. A. A. (July 2017). "जीपीयू पर सबसेट-सम समस्या के लिए एक कम-स्थान एल्गोरिथ्म". Computers & Operations Research. 83: 120–124. doi:10.1016/j.cor.2017.02.006.
↑ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "एकाधिक उपसमुच्चय योग समस्या". SIAM Journal on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. ISSN 1052-6234.
↑ Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Speranza, Maria Grazia (2003-03-01). "उपसमुच्चय-योग समस्या के लिए एक कुशल पूर्णतः बहुपद सन्निकटन योजना". Journal of Computer and System Sciences (in English). 66 (2): 349–370. doi:10.1016/S0022-0000(03)00006-0. ISSN 0022-0000.
↑ Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). बस्ते की समस्या. Springer. p. 97. ISBN 9783540402862.

अग्रिम पठन

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "35.5: The subset-sum problem". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A3.2: SP13, pg.223.
Lagarias, J. C.; Odlyzko, A. M. (1985-01-01). "Solving low-density subset sum problems". Journal of the ACM. 32 (1): 229–246. doi:10.1145/2455.2461. ISSN 0004-5411. S2CID 885632.
Martello, Silvano; Toth, Paolo (1990). "4 Subset-sum problem". Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. pp. 105–136. ISBN 0-471-92420-2. MR 1086874.

[kleinberg2006p491-1] 1.0 ^1.1 Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिज़ाइन (2nd ed.). p. 491. ISBN 0-321-37291-3.

[2] Goodrich, Michael. "अधिक एनपी पूर्ण और एनपी कठिन समस्याएं" (PDF). Archived (PDF) from the original on 2022-10-09.

[garey79-3] Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, Section 3.1 and problem SP1 in Appendix A.3.1.

[4] Filmus, Yuval (30 January 2016). Answer to: "Is there a known, fast algorithm for counting all subsets that sum to below a certain number?". Theoretical Computer Science Stack Exchange. Note that Filmus' citation in support of the claim (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison". Theoretical Computer Science. Elsevier. 410: 101-107. DOI 10.1016/j.tcs.2008.09.034) does not in fact prove the claim, instead directing readers to another citation (Papadimitriou, Christos (1994). Computational Complexity. Addison-Wesley: Reading, MA. Chapter 9. ISBN 0-201-53082-1 — via the Internet Archive), which does not explicitly prove the claim either. Papadimitriou's proof that SSP is NP-complete via reduction of 3SAT does, however, generalize to a reduction from #3SAT to #SSP.

[:0-5] 5.0 ^5.1 ^5.2 Richard E. Korf, Ethan L. Schreiber, and Michael D. Moffitt (2014). "इष्टतम अनुक्रमिक मल्टी-वे संख्या विभाजन" (PDF). Archived (PDF) from the original on 2022-10-09.{{cite web}}: CS1 maint: multiple names: authors list (link)

[6] Horowitz, Ellis; Sahni, Sartaj (1974). "नैपसैक समस्या के अनुप्रयोगों के साथ विभाजन की गणना करना" (PDF). Journal of the Association for Computing Machinery. 21 (2): 277–292. doi:10.1145/321812.321823. hdl:1813/5989. MR 0354006. S2CID 16866858. Archived (PDF) from the original on 2022-10-09.

[7] "दो-योग समस्या" (PDF). Archived (PDF) from the original on 2022-10-09.

[8] Schroeppel, Richard; Shamir, Adi (1981-08-01). "A $T = O (2 n /2)$ [[Category: Templates Vigyan Ready]], $S = O (2 n /4)$ [[Category: Templates Vigyan Ready]] algorithm for certain NP-complete problems". SIAM Journal on Computing. 10 (3): 456–464. doi:10.1137/0210033. ISSN 0097-5397. {{cite journal}}: URL–wikilink conflict (help)

[9] Howgrave-Graham, Nick; Joux, Antoine (2010). "New Generic Algorithms for Hard Knapsacks". In Gilbert, Henri (ed.). Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science (in English). Vol. 6110. Berlin, Heidelberg: Springer. pp. 235–256. doi:10.1007/978-3-642-13190-5_12. ISBN 978-3-642-13190-5.

[10] Becker, Anja; Joux, Antoine (2010). "Improved Generic Algorithms for Hard Knapsacks". In Gilbert, Henri (ed.). Advances in Cryptology – EUROCRYPT 2011. Lecture Notes in Computer Science (in English). Vol. 6632. Berlin, Heidelberg: Springer. pp. 364–385. doi:10.1007/978-3-642-20465-4_21. ISBN 978-3-642-20465-4.

[Pisinger09-11] Pisinger, David (1999). "सीमित वजन के साथ बस्ता समस्याओं के लिए रैखिक समय एल्गोरिदम". Journal of Algorithms. 33 (1): 1–14. doi:10.1006/jagm.1999.1034. MR 1712690.

[12] Koiliaris, Konstantinos; Xu, Chao (2015-07-08). "सबसेट योग के लिए एक तेज़ छद्मबहुपद समय एल्गोरिदम". arXiv:1507.02318 [cs.DS].

[13] Bringmann, Karl (2017). "A near-linear pseudopolynomial time algorithm for subset sum". In Klein, Philip N. (ed.). Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017). SIAM. pp. 1073–1084. arXiv:1610.04712. doi:10.1137/1.9781611974782.69.

[14] Curtis, V. V.; Sanches, C. A. A. (January 2016). "An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU". Concurrency and Computation: Practice and Experience. 28 (1): 95–113. doi:10.1002/cpe.3636. S2CID 20927927.

[15] Curtis, V. V.; Sanches, C. A. A. (July 2017). "जीपीयू पर सबसेट-सम समस्या के लिए एक कम-स्थान एल्गोरिथ्म". Computers & Operations Research. 83: 120–124. doi:10.1016/j.cor.2017.02.006.

[:1-16] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "एकाधिक उपसमुच्चय योग समस्या". SIAM Journal on Optimization. 11 (2): 308–319. doi:10.1137/S1052623498348481. ISSN 1052-6234.

[17] Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Speranza, Maria Grazia (2003-03-01). "उपसमुच्चय-योग समस्या के लिए एक कुशल पूर्णतः बहुपद सन्निकटन योजना". Journal of Computer and System Sciences (in English). 66 (2): 349–370. doi:10.1016/S0022-0000(03)00006-0. ISSN 0022-0000.

[knapsack-18] Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). बस्ते की समस्या. Springer. p. 97. ISBN 9783540402862.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

@@ Line 1: / Line 1: @@
 {{Short description|Decision problem in computer science}}
-उपसमुच्चय योग समस्या (एसएसपी) [[कंप्यूटर विज्ञान]] में एक [[निर्णय समस्या]] है। इसके सबसे सामान्य सूत्रीकरण में, एक [[मल्टीसेट]] है <math>S</math> पूर्णांकों और एक लक्ष्य-योग का <math>T</math>, और प्रश्न यह तय करना है कि क्या पूर्णांकों का कोई उपसमुच्चय सटीक रूप से योग करता है <math>T</math>.<ref name="kleinberg2006p491">{{cite book|last1=Kleinberg|first1=Jon|url=https://archive.org/details/algorithmdesign0000klei|title=एल्गोरिथम डिज़ाइन|last2=Tardos|first2=Éva|year=2006|isbn=0-321-37291-3|edition=2nd|page=[https://archive.org/details/algorithmdesign0000klei/page/491 491]|url-access=registration}}</ref> समस्या को [[ एनपी कठिन ]] माना जाता है। इसके अलावा, इसके कुछ प्रतिबंधित संस्करण एनपी-पूर्णता|एनपी-पूर्ण भी हैं, उदाहरण के लिए:<ref name="kleinberg2006p491" />
+उपसमुच्चय योग समस्या (एसएसपी) [[कंप्यूटर विज्ञान]] में [[निर्णय समस्या]] है। इसके सबसे सामान्य सूत्रीकरण में, [[मल्टीसेट]] है इस प्रकार <math>S</math> पूर्णांकों और लक्ष्य-योग का <math>T</math>, और प्रश्न यह तय करना है कि क्या पूर्णांकों का कोई उपसमुच्चय स्पष्ट रूप <math>T</math> से योग करता है .<ref name="kleinberg2006p491">{{cite book|last1=Kleinberg|first1=Jon|url=https://archive.org/details/algorithmdesign0000klei|title=एल्गोरिथम डिज़ाइन|last2=Tardos|first2=Éva|year=2006|isbn=0-321-37291-3|edition=2nd|page=[https://archive.org/details/algorithmdesign0000klei/page/491 491]|url-access=registration}}</ref> समस्या को [[ एनपी कठिन |np कठिन]] माना जाता है। इसके अतिरिक्त, इसके कुछ प्रतिबंधित संस्करण np-पूर्णता या np-पूर्ण भी हैं, उदाहरण के लिए:<ref name="kleinberg2006p491" />
-* वह वैरिएंट जिसमें सभी इनपुट सकारात्मक हैं।
+* वह वैरिएंट जिसमें सभी इनपुट धनात्मक हैं।
-* वह प्रकार जिसमें इनपुट सकारात्मक या नकारात्मक हो सकते हैं, और <math>T=0</math>. उदाहरण के लिए, सेट दिया गया है <math>\{-7, -3, -2, 9000, 5, 8\}</math>, उत्तर हाँ है क्योंकि उपसमुच्चय <math>\{-3, -2, 5\}</math> योग शून्य है.
+* वह प्रकार जिसमें इनपुट धनात्मक या ऋणात्मक हो सकते हैं, और <math>T=0</math>. उदाहरण के लिए, समुच्चय <math>\{-7, -3, -2, 9000, 5, 8\}</math> दिया गया है , उत्तर हाँ है क्योंकि उपसमुच्चय <math>\{-3, -2, 5\}</math> योग शून्य है.
-* वह वैरिएंट जिसमें सभी इनपुट सकारात्मक हैं, और लक्ष्य योग सभी इनपुट के योग का बिल्कुल आधा है, यानी, <math> T = \frac{1}{2}(a_1+\dots+a_n)</math> . एसएसपी के इस विशेष मामले को विभाजन समस्या के रूप में जाना जाता है।
+* वह वैरिएंट जिसमें सभी इनपुट धनात्मक हैं, और लक्ष्य योग सभी इनपुट के योग का पुर्णतः अर्ध है, अर्थात, <math> T = \frac{1}{2}(a_1+\dots+a_n)</math> . एसएसपी के इस विशेष स्थिति को विभाजन समस्या के रूप में जाना जाता है।
-एसएसपी को एक [[अनुकूलन समस्या]] के रूप में भी माना जा सकता है: एक उपसमुच्चय ढूंढें जिसका योग अधिकतम टी है, और उसके अधीन, जितना संभव हो टी के करीब। यह एनपी-हार्ड है, लेकिन कई एल्गोरिदम हैं जो इसे उचित रूप से जल्दी से हल कर सकते हैं अभ्यास।
+एसएसपी को [[अनुकूलन समस्या]] के रूप में भी माना जा सकता है: उपसमुच्चय खोजे जिसका योग अधिकतम T है, और उसके अधीन, जितना संभव हो T के निकट होता है। यह np-हार्ड है, किन्तु कई एल्गोरिदम हैं जो इसे उचित रूप से जल्दी से हल कर सकते हैं।
-एसएसपी नैपसैक समस्या और [[एकाधिक उपसमुच्चय योग]] समस्या का एक विशेष मामला है।
+एसएसपी नैपसैक समस्या और [[एकाधिक उपसमुच्चय योग]] समस्या का विशेष स्थिति है।
-== कम्प्यूटेशनल कठोरता ==
+== कम्प्यूटेशनल कठोरता                                                                                                                                                                                                                                                                                          ==
-SSP की [[रन-टाइम जटिलता]] दो मापदंडों पर निर्भर करती है:
+एसएसपी की [[रन-टाइम जटिलता]] दो मापदंडों पर निर्भर करती है:
-* {{nobold|''n''}} - इनपुट पूर्णांकों की संख्या. यदि n एक छोटी निश्चित संख्या है, तो समाधान के लिए एक विस्तृत खोज व्यावहारिक है।
+* {{nobold|''n''}} - इनपुट पूर्णांकों की संख्या. यदि n छोटी निश्चित संख्या है, तो समाधान के लिए विस्तृत खोज व्यावहारिक है।
-* {{nobold|''L''}} - समस्या की सटीकता, समस्या को बताने के लिए लगने वाले द्विआधारी स्थानीय मानों की संख्या के रूप में बताई गई है। यदि L एक छोटी निश्चित संख्या है, तो [[गतिशील प्रोग्रामिंग]] एल्गोरिदम हैं जो इसे सटीक रूप से हल कर सकते हैं।
+* {{nobold|''L''}} - समस्या की स्पष्टता, समस्या को बताने के लिए लगने वाले द्विअर्धरी समिष्टीय मानों की संख्या के रूप में बताई गई है। यदि L छोटी निश्चित संख्या है, तो [[गतिशील प्रोग्रामिंग]] एल्गोरिदम हैं जो इसे स्पष्ट रूप से हल कर सकते हैं।
-जैसे-जैसे n और L दोनों बड़े होते जाते हैं, SSP NP-हार्ड होता है। सबसे प्रसिद्ध एल्गोरिदम की जटिलता दो मापदंडों n और L में से छोटे में [[घातीय समय]] है। समस्या एनपी-हार्ड है, तब भी जब सभी इनपुट पूर्णांक सकारात्मक होते हैं (और लक्ष्य-योग टी इनपुट का एक हिस्सा है)। इसे [[3SAT]] से प्रत्यक्ष कमी द्वारा सिद्ध किया जा सकता है।<ref>{{Cite web |last=Goodrich |first=Michael |title=अधिक एनपी पूर्ण और एनपी कठिन समस्याएं|url=https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-date=2022-10-09 |url-status=live}}</ref> इसे [[3-आयामी मिलान]] (3DM) से कमी करके भी सिद्ध किया जा सकता है:<ref name="garey79">{{Garey-Johnson}}, Section&nbsp;3.1 and problem&nbsp;SP1 in Appendix&nbsp;A.3.1.</ref>
+जैसे-जैसे n और L दोनों बड़े होते जाते हैं, एसएसपी NP-हार्ड होता है। सबसे प्रसिद्ध एल्गोरिदम की जटिलता दो मापदंडों n और L में से छोटे में [[घातीय समय]] है। समस्या np-हार्ड है, तब भी जब सभी इनपुट पूर्णांक धनात्मक होते हैं (और लक्ष्य-योग T इनपुट का भाग है)। इसे [[3SAT|3सैट]] से प्रत्यक्ष कमी द्वारा सिद्ध किया जा सकता है।<ref>{{Cite web |last=Goodrich |first=Michael |title=अधिक एनपी पूर्ण और एनपी कठिन समस्याएं|url=https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.ics.uci.edu/~goodrich/teach/cs162/notes/pnp3.pdf |archive-date=2022-10-09 |url-status=live}}</ref> इसे [[3-आयामी मिलान]] (3डीएम) से कमी करके भी सिद्ध किया जा सकता है:<ref name="garey79">{{Garey-Johnson}}, Section&nbsp;3.1 and problem&nbsp;SP1 in Appendix&nbsp;A.3.1.</ref>
-* हमें 3DM का एक उदाहरण दिया गया है, जहां शीर्ष सेट W, X, Y हैं। प्रत्येक सेट में n शीर्ष हैं। वहाँ m किनारे हैं, जहाँ प्रत्येक किनारे में W,<sub>2</sub>(एम+1)), ताकि एल किनारों की संख्या का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की संख्या से बड़ा हो।
+* हमें 3डीएम का उदाहरण दिया गया है, जहां शीर्ष समुच्चय W, X, Y हैं। प्रत्येक समुच्चय में n शीर्ष हैं। वहाँ m किनारे हैं, जहाँ प्रत्येक किनारे में W,<sub>2</sub>(m+1)), जिससे L किनारों की संख्या का प्रतिनिधित्व करने के लिए आवश्यक बिट्स की संख्या से बड़ा हो।
-* हम m धनात्मक पूर्णांकों के साथ SSP का एक उदाहरण बनाते हैं। पूर्णांकों का वर्णन उनके द्विआधारी निरूपण द्वारा किया जाता है। प्रत्येक इनपुट पूर्णांक को 3nL बिट्स द्वारा दर्शाया जा सकता है, जिसे L बिट्स के 3n ज़ोन में विभाजित किया गया है। प्रत्येक क्षेत्र एक शीर्ष से मेल खाता है।
+* हम m धनात्मक पूर्णांकों के साथ एसएसपी का उदाहरण बनाते हैं। पूर्णांकों का वर्णन उनके द्विअर्धरी निरूपण द्वारा किया जाता है। प्रत्येक इनपुट पूर्णांक को 3nL बिट्स द्वारा दर्शाया जा सकता है, जिसे L बिट्स के 3n ज़ोन में विभाजित किया गया है। प्रत्येक क्षेत्र शीर्ष से मेल खाता है।
-* 3DM उदाहरण में प्रत्येक किनारे (w,x,y) के लिए, SSP उदाहरण में एक पूर्णांक होता है, जिसमें बिल्कुल तीन बिट्स 1 होते हैं: शीर्ष w, x, और y के क्षेत्रों में सबसे कम महत्वपूर्ण बिट्स . उदाहरण के लिए, यदि n=10 और L=3, और W=(0,...,9), X=(10,...,19), Y=(20,...,29), तो किनारे (0, 10, 20) को संख्या (2) द्वारा दर्शाया गया है<sup>0</sup>+2<sup>30</sup>+2<sup>60</sup>).
+* 3डीएम उदाहरण में प्रत्येक किनारे (w,x,y) के लिए, एसएसपी उदाहरण में पूर्णांक होता है, जिसमें पुर्णतः तीन बिट्स 1 होते हैं: शीर्ष w, x, और y के क्षेत्रों में सबसे कम महत्वपूर्ण बिट्स . उदाहरण के लिए, यदि n=10 और L=3, और W=(0,...,9), X=(10,...,19), Y=(20,...,29), तो किनारे (0, 10, 20) को संख्या (2<sup>0</sup>+2<sup>30</sup>+2<sup>60</sup>) द्वारा दर्शाया गया है.
-* एसएसपी उदाहरण में लक्ष्य योग टी को प्रत्येक क्षेत्र के सबसे कम-महत्वपूर्ण बिट में 1 के साथ पूर्णांक पर सेट किया गया है, यानी (2)<sup>0</sup>+2<sup>1</sup>+...+2<sup>3एन-1</sup>).
+* एसएसपी उदाहरण में लक्ष्य योग T को प्रत्येक क्षेत्र के सबसे कम-महत्वपूर्ण बिट में 1 के साथ पूर्णांक पर समुच्चय किया गया है, अर्थात (2)<sup>0</sup>+2<sup>1</sup>+...+2<sup>3n-1</sup>).
-* यदि 3DM उदाहरण में पूर्ण मिलान है, तो SSP उदाहरण में संबंधित पूर्णांकों का योग बिल्कुल T प्राप्त करता है।
+* यदि 3डीएम उदाहरण में पूर्ण मिलान है, जिससे एसएसपी उदाहरण में संबंधित पूर्णांकों का योग पुर्णतः T प्राप्त करता है।
-* इसके विपरीत, यदि SSP उदाहरण में बिल्कुल T योग के साथ एक उपसमुच्चय है, तो, चूंकि क्षेत्र पर्याप्त रूप से बड़े हैं ताकि एक क्षेत्र से दूसरे क्षेत्र में कोई स्थानांतरण न हो, योग को 3DM उदाहरण में पूर्ण मिलान के अनुरूप होना चाहिए।
+* इसके विपरीत, यदि एसएसपी उदाहरण में पुर्णतः T योग के साथ उपसमुच्चय है, तो, चूंकि क्षेत्र पर्याप्त रूप से बड़े हैं जिससे क्षेत्र से दूसरे क्षेत्र में कोई समिष्टांतरण नही होता है, योग को 3डीएम उदाहरण में पूर्ण मिलान के अनुरूप होना चाहिए।
-निम्नलिखित वेरिएंट को एनपी-हार्ड के रूप में भी जाना जाता है:
+निम्नलिखित वेरिएंट को np-हार्ड के रूप में भी जाना जाता है:
-* इनपुट पूर्णांक धनात्मक और ऋणात्मक दोनों हो सकते हैं, और लक्ष्य-योग T = 0. इसे धनात्मक पूर्णांक वाले वैरिएंट से घटाकर सिद्ध किया जा सकता है। उस वैरिएंट को SubsetSumPositive से और वर्तमान वैरिएंट को SubsetSumZero से निरूपित करें। SubsetSumPositive के एक उदाहरण (S, T) को देखते हुए, −T मान के साथ एक तत्व जोड़कर SubsetSumZero का एक उदाहरण बनाएं। SubsetSumPositive उदाहरण के समाधान को देखते हुए, −T जोड़ने से SubsetSumZero उदाहरण का समाधान प्राप्त होता है। इसके विपरीत, SubsetSumZero उदाहरण के समाधान को देखते हुए, इसमें −T होना चाहिए (चूंकि S में सभी पूर्णांक सकारात्मक हैं), इसलिए शून्य का योग प्राप्त करने के लिए, इसमें +T के योग के साथ S का एक उपसमुच्चय भी होना चाहिए, जो SubsetSumPositive उदाहरण का एक समाधान है।
+* इनपुट पूर्णांक धनात्मक और ऋणात्मक दोनों हो सकते हैं, और लक्ष्य-योग T = 0. इसे धनात्मक पूर्णांक वाले वैरिएंट से घटाकर सिद्ध किया जा सकता है। उस वैरिएंट को उपसमुच्चयसमपॉजिटिव से और वर्तमान वैरिएंट को उपसमुच्चय योग शून्य से निरूपित करें। उपसमुच्चयसमपॉजिटिव के उदाहरण (S, T) को देखते हुए,T मान के साथ तत्व जोड़कर उपसमुच्चय योग शून्य का उदाहरण बनाएं। उपसमुच्चयसमपॉजिटिव उदाहरण के समाधान को देखते हुए,T जोड़ने से उपसमुच्चय योग शून्य उदाहरण का समाधान प्राप्त होता है। इसके विपरीत, उपसमुच्चय योग शून्य उदाहरण के समाधान को देखते हुए, इसमें T होना चाहिए (चूंकि S में सभी पूर्णांक धनात्मक हैं), इसलिए शून्य का योग प्राप्त करने के लिए, इसमें +T के योग के साथ S का उपसमुच्चय भी होना चाहिए, जो उपसमुच्चयसमपॉजिटिव उदाहरण का समाधान है।
-*इनपुट पूर्णांक सकारात्मक हैं, और टी = योग(एस)/2। इसे सामान्य प्रकार से कमी करके भी सिद्ध किया जा सकता है; विभाजन समस्या देखें.
+*इनपुट पूर्णांक धनात्मक हैं, और T = योग(s)/2। इसे सामान्य प्रकार से कमी करके भी सिद्ध किया जा सकता है; विभाजन समस्या देखें.
-अनुरूप गणना समस्या #एसएसपी, जो लक्ष्य के योग के लिए उपसमुच्चय की संख्या की गणना करने के लिए कहती है, शार्प पी पूर्ण|#पी-पूर्ण है।<ref>[[Yuval Filmus|Filmus, Yuval]] (30 January 2016).  [https://cs.stackexchange.com/a/52466 Answer] to: "[https://cs.stackexchange.com/q/52453 Is there a known, fast algorithm for counting all subsets that sum to below a certain number?]".  ''Theoretical Computer Science [[Stack Exchange]].''  Note that Filmus' citation in support of the claim (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison".  ''Theoretical Computer Science''.  Elsevier.  '''410''': 101-107.  DOI&nbsp;[http://dx.doi.org/10.1016/j.tcs.2008.09.034 10.1016/j.tcs.2008.09.034]) does not in fact prove the claim, instead directing readers to another citation ([[Christos Papadimitriou|Papadimitriou, Christos]] (1994). [https://archive.org/details/computationalcom0000papa/ ''Computational Complexity''].  Addison-Wesley: Reading, MA.  Chapter&nbsp;9.  {{ISBN|0-201-53082-1}}&nbsp;&mdash; via the [[Internet Archive]]), which does not explicitly prove the claim either.  Papadimitriou's proof that SSP is NP-complete via reduction of [[3SAT]] does, however, generalize to a reduction from [[Sharp-SAT|#3SAT]] to #SSP.</ref>
-== घातीय समय एल्गोरिदम ==
-एन में समय घातांक में एसएसपी को हल करने के कई तरीके हैं।<ref name=":0">{{Cite web|last=Richard E. Korf, Ethan L. Schreiber, and Michael D. Moffitt|date=2014|title=इष्टतम अनुक्रमिक मल्टी-वे संख्या विभाजन|url=https://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Korf_etal.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Korf_etal.pdf |archive-date=2022-10-09 |url-status=live}}</ref>
+अनुरूप गणना समस्या एसएसपी, जो लक्ष्य के योग के लिए उपसमुच्चय की संख्या की गणना करने के लिए कहती है, शार्प पी पूर्ण है।<ref>[[Yuval Filmus|Filmus, Yuval]] (30 January 2016).  [https://cs.stackexchange.com/a/52466 Answer] to: "[https://cs.stackexchange.com/q/52453 Is there a known, fast algorithm for counting all subsets that sum to below a certain number?]".  ''Theoretical Computer Science [[Stack Exchange]].''  Note that Filmus' citation in support of the claim (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison".  ''Theoretical Computer Science''.  Elsevier.  '''410''': 101-107.  DOI&nbsp;[http://dx.doi.org/10.1016/j.tcs.2008.09.034 10.1016/j.tcs.2008.09.034]) does not in fact prove the claim, instead directing readers to another citation ([[Christos Papadimitriou|Papadimitriou, Christos]] (1994). [https://archive.org/details/computationalcom0000papa/ ''Computational Complexity''].  Addison-Wesley: Reading, MA.  Chapter&nbsp;9.  {{ISBN|0-201-53082-1}}&nbsp;&mdash; via the [[Internet Archive]]), which does not explicitly prove the claim either.  Papadimitriou's proof that SSP is NP-complete via reduction of [[3SAT]] does, however, generalize to a reduction from [[Sharp-SAT|#3SAT]] to #SSP.</ref>
+== घातीय समय एल्गोरिदम                                                                                                                                                                                               ==
+n में समय घातांक में एसएसपी को हल करने के कई विधि हैं।<ref name=":0">{{Cite web|last=Richard E. Korf, Ethan L. Schreiber, and Michael D. Moffitt|date=2014|title=इष्टतम अनुक्रमिक मल्टी-वे संख्या विभाजन|url=https://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Korf_etal.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www.cs.uic.edu/pub/Isaim2014/WebPreferences/ISAIM2014_Korf_etal.pdf |archive-date=2022-10-09 |url-status=live}}</ref>
 === समावेश-बहिष्करण ===
-सबसे सरल समाधान|भोला एल्गोरिदम एन संख्याओं के सभी उपसमूहों के माध्यम से चक्र करना होगा और, उनमें से प्रत्येक के लिए, यह जांचना होगा कि उपसमुच्चय का योग सही संख्या में है या नहीं। चलने का समय व्यवस्थित है <math>O(2^n \cdot n)</math>, क्योंकि वहां हैं <math>2^n</math> उपसमुच्चय और, प्रत्येक उपसमुच्चय की जाँच करने के लिए, हमें अधिकतम n तत्वों का योग करना होगा।
+सबसे सरल समाधान एल्गोरिदम n संख्याओं के सभी उपसमूहों के माध्यम से चक्र करना होगा और, उनमें से प्रत्येक के लिए, यह जांचना होगा कि उपसमुच्चय का योग सही संख्या में है या नहीं है। चलने का समय <math>O(2^n \cdot n)</math> व्यवस्थित है , क्योंकि वहां <math>2^n</math> हैं उपसमुच्चय और, प्रत्येक उपसमुच्चय की जाँच करने के लिए, हमें अधिकतम n तत्वों का योग करना होता है।
-एल्गोरिथ्म को बाइनरी ट्री की [[गहराई-पहली खोज]] द्वारा कार्यान्वित किया जा सकता है: ट्री में प्रत्येक स्तर एक इनपुट संख्या से मेल खाता है; बायीं शाखा सेट से संख्या को बाहर करने से मेल खाती है, और दाहिनी शाखा संख्या को शामिल करने से मेल खाती है (इसलिए नाम समावेशन-बहिष्करण)। आवश्यक स्मृति है <math>O(n)</math>. रन-टाइम को कई अनुमानों द्वारा बेहतर बनाया जा सकता है:<ref name=":0" />
+एल्गोरिथ्म को बाइनरी ट्री की [[गहराई-पहली खोज|प्रथम खोज]] द्वारा कार्यान्वित किया जा सकता है: ट्री में प्रत्येक स्तर इनपुट संख्या से मेल खाता है; बायीं शाखा समुच्चय से संख्या को बाहर करने से मेल खाती है, और दाहिनी शाखा संख्या को सम्मिलित करने से मेल खाती है (इसलिए नाम समावेशन-बहिष्करण)। आवश्यक मेमोरी <math>O(n)</math> है . रन-टाइम को कई अनुमानों द्वारा उत्तम बनाया जा सकता है:<ref name=":0" />
 * इनपुट संख्याओं को घटते क्रम में संसाधित करें।
-* यदि किसी दिए गए नोड में शामिल पूर्णांक अब तक पाए गए सर्वोत्तम उपसमुच्चय के योग से अधिक है, तो नोड को काट दिया जाता है।
+* यदि किसी दिए गए नोड में सम्मिलित पूर्णांक अब तक पाए गए सर्वोत्तम उपसमुच्चय के योग से अधिक है, तो नोड को काट दिया जाता है।
-* यदि किसी दिए गए नोड में शामिल पूर्णांक, साथ ही शेष सभी पूर्णांक, अब तक पाए गए सर्वोत्तम उपसमुच्चय के योग से कम हैं, तो नोड को काट दिया जाता है।
+* यदि किसी दिए गए नोड में सम्मिलित पूर्णांक, साथ ही शेष सभी पूर्णांक, अब तक पाए गए सर्वोत्तम उपसमुच्चय के योग से कम हैं, तो नोड को काट दिया जाता है।
 === होरोविट्ज़ और साहनी ===
-में, होरोविट्ज़ और [[सरताज साहनी]]<ref>{{cite journal|last1=Horowitz|first1=Ellis|title=नैपसैक समस्या के अनुप्रयोगों के साथ विभाजन की गणना करना|url=https://ecommons.cornell.edu/bitstream/1813/5989/1/72-134.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://ecommons.cornell.edu/bitstream/1813/5989/1/72-134.pdf |archive-date=2022-10-09 |url-status=live|journal=[[Journal of the Association for Computing Machinery]]|volume=21|issue=2|pages=277–292|year=1974|doi=10.1145/321812.321823|mr=0354006|last2=Sahni|first2=Sartaj|author2-link=Sartaj Sahni|hdl=1813/5989|s2cid=16866858|hdl-access=free}}</ref> एक तेज़ घातीय-समय एल्गोरिदम प्रकाशित किया, जो समय में चलता है <math>O( 2^{n/2}\cdot (n/2))</math>, लेकिन बहुत अधिक स्थान की आवश्यकता है - <math>O( 2^{n/2})</math>. एल्गोरिथ्म मनमाने ढंग से n तत्वों को दो सेटों में विभाजित करता है <math>n/2</math> प्रत्येक। इन दो सेटों में से प्रत्येक के लिए, यह सभी के योगों की एक सूची संग्रहीत करता है <math>2^{n/2}</math> इसके तत्वों के संभावित उपसमुच्चय। फिर इन दोनों सूचियों में से प्रत्येक को क्रमबद्ध किया जाता है। यहां तक कि सबसे तेज़ तुलना सॉर्टिंग एल्गोरिदम का उपयोग करते हुए, इस चरण के लिए मर्जसॉर्ट को समय लगेगा <math>O(2^{n/2}n)</math>. हालाँकि, इसके लिए रकम की एक क्रमबद्ध सूची दी गई है <math>k</math> तत्वों, सूची को (की शुरूआत के साथ दो क्रमबद्ध सूचियों तक विस्तारित किया जा सकता है<math>k+1</math>)वां तत्व, और इन दो क्रमबद्ध सूचियों को समय में मर्ज किया जा सकता है <math>O(2^k)</math>. इस प्रकार, प्रत्येक सूची को समय पर क्रमबद्ध रूप में तैयार किया जा सकता है <math>O(2^{n/2})</math>. दो क्रमबद्ध सूचियों को देखते हुए, एल्गोरिदम जांच कर सकता है कि पहले सरणी का एक तत्व और दूसरे सरणी का एक तत्व समय में टी तक है या नहीं <math>O(2^{n/2})</math>. ऐसा करने के लिए, एल्गोरिदम पहले एरे से घटते क्रम में (सबसे बड़े तत्व से शुरू) और दूसरे एरे से बढ़ते क्रम में (सबसे छोटे तत्व से शुरू) गुजरता है। जब भी पहले एरे में वर्तमान तत्व और दूसरे एरे में वर्तमान तत्व का योग टी से अधिक होता है, तो एल्गोरिदम पहले एरे में अगले तत्व पर चला जाता है। यदि यह टी से कम है, तो एल्गोरिदम दूसरे सरणी में अगले तत्व पर चला जाता है। यदि T के योग वाले दो तत्व पाए जाते हैं, तो यह रुक जाता है। (दो तत्वों के योग की उप-समस्या को दो-योग के रूप में जाना जाता है।<ref>{{Cite web |title=दो-योग समस्या|url=https://www3.cs.uic.edu/pub/CS211/LabsS18/Two-Sum.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www3.cs.uic.edu/pub/CS211/LabsS18/Two-Sum.pdf |archive-date=2022-10-09 |url-status=live}}</ref>)
+में, होरोविट्ज़ और [[सरताज साहनी]] <ref>{{cite journal|last1=Horowitz|first1=Ellis|title=नैपसैक समस्या के अनुप्रयोगों के साथ विभाजन की गणना करना|url=https://ecommons.cornell.edu/bitstream/1813/5989/1/72-134.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://ecommons.cornell.edu/bitstream/1813/5989/1/72-134.pdf |archive-date=2022-10-09 |url-status=live|journal=[[Journal of the Association for Computing Machinery]]|volume=21|issue=2|pages=277–292|year=1974|doi=10.1145/321812.321823|mr=0354006|last2=Sahni|first2=Sartaj|author2-link=Sartaj Sahni|hdl=1813/5989|s2cid=16866858|hdl-access=free}}</ref> तेज़ घातीय-समय एल्गोरिदम प्रकाशित किया था, जो समय <math>O( 2^{n/2}\cdot (n/2))</math> में चलता है , किन्तु बहुत अधिक <math>O( 2^{n/2})</math> समिष्ट की आवश्यकता है एल्गोरिथ्म इच्छानुसार सही से n तत्वों को दो समुच्चयो में विभाजित करता है <math>n/2</math> प्रत्येक इन दो समुच्चयो में से प्रत्येक के लिए, यह सभी <math>2^{n/2}</math> के योगों की सूची संग्रहीत करता है इसके तत्वों के संभावित उपसमुच्चय फिर इन दोनों सूचियों में से प्रत्येक को क्रमबद्ध किया जाता है। यहां तक कि सबसे तेज़ तुलना सॉर्टिंग एल्गोरिदम का उपयोग करते हुए, इस चरण के लिए मर्जसॉर्ट को समय लगेगा <math>O(2^{n/2}n)</math>. चूँकि, इसके लिए रकम की क्रमबद्ध सूची दी गई है <math>k</math> तत्वों, सूची को (की प्रारंभ के साथ दो क्रमबद्ध सूचियों <math>k+1</math> तक विस्तारित किया जा सकता है) तत्व, और इन दो क्रमबद्ध सूचियों को समय <math>O(2^k)</math> में मर्ज किया जा सकता है . इस प्रकार, प्रत्येक सूची को समय पर क्रमबद्ध <math>O(2^{n/2})</math> रूप में तैयार किया जा सकता है . दो क्रमबद्ध सूचियों को देखते हुए, एल्गोरिदम जांच कर सकता है कि पहले सरणी का तत्व और दूसरे सरणी का तत्व समय में T तक है या <math>O(2^{n/2})</math> नहीं है . ऐसा करने के लिए, एल्गोरिदम पहले एरे से घटते क्रम में (सबसे बड़े तत्व से प्रारंभ) और दूसरे एरे से बढ़ते क्रम में (सबसे छोटे तत्व से प्रारंभ) निकलता है। जब भी पहले एरे में वर्तमान तत्व और दूसरे एरे में वर्तमान तत्व का योग T से अधिक होता है, तो एल्गोरिदम पहले एरे में अगले तत्व पर चला जाता है। यदि यह T से कम है, तो एल्गोरिदम दूसरे सरणी में अगले तत्व पर चला जाता है। यदि T के योग वाले दो तत्व पाए जाते हैं, तो यह रुक जाता है। (दो तत्वों के योग की उप-समस्या को दो-योग के रूप में जाना जाता है।<ref>{{Cite web |title=दो-योग समस्या|url=https://www3.cs.uic.edu/pub/CS211/LabsS18/Two-Sum.pdf |archive-url=https://ghostarchive.org/archive/20221009/https://www3.cs.uic.edu/pub/CS211/LabsS18/Two-Sum.pdf |archive-date=2022-10-09 |url-status=live}}</ref>)
 === श्रोएप्पेल और शमीर ===
-में, [[रिचर्ड श्रोएप]]्पेल और [[आदि शमीर]] ने एक एल्गोरिदम प्रस्तुत किया<ref>{{Cite journal|last1=Schroeppel|first1=Richard|last2=Shamir|first2=Adi|date=1981-08-01|title=A {{math|''T'' {{=}} ''O''(2<sup>''n''/2</sup>)}}, {{math|''S'' {{=}} ''O''(2<sup>''n''/4</sup>)}} algorithm for certain NP-complete problems|url=https://epubs.siam.org/doi/abs/10.1137/0210033|journal=SIAM Journal on Computing|volume=10|issue=3|pages=456–464|doi=10.1137/0210033|issn=0097-5397}}</ref> होरोविट्ज़ और सानही पर आधारित, जिसके लिए समान रनटाइम की आवश्यकता होती है - <math>O( 2^{n/2}\cdot (n/4))</math>, बहुत कम जगह - <math>O(2^{n/4})</math>. n/2 तत्वों के सभी उपसमूहों को पहले से बनाने और संग्रहीत करने के बजाय, वे तत्वों को n/4 तत्वों के 4 सेटों में विभाजित करते हैं, और [[न्यूनतम ढेर]] का उपयोग करके गतिशील रूप से n/2 तत्व जोड़े के सबसेट उत्पन्न करते हैं, जो उपरोक्त समय प्राप्त करता है और अंतरिक्ष की जटिलताएँ क्योंकि यह किया जा सकता है <math>O(k^{2}\log(k))</math> और स्थान <math>O(k)</math> लंबाई k की 4 सूचियाँ दी गई हैं।
+में, [[रिचर्ड श्रोएप|रिचर्ड श्रोएप्पेल]] और [[आदि शमीर|शमीर]] ने एल्गोरिदम प्रस्तुत किया था <ref>{{Cite journal|last1=Schroeppel|first1=Richard|last2=Shamir|first2=Adi|date=1981-08-01|title=A {{math|''T'' {{=}} ''O''(2<sup>''n''/2</sup>)}}, {{math|''S'' {{=}} ''O''(2<sup>''n''/4</sup>)}} algorithm for certain NP-complete problems|url=https://epubs.siam.org/doi/abs/10.1137/0210033|journal=SIAM Journal on Computing|volume=10|issue=3|pages=456–464|doi=10.1137/0210033|issn=0097-5397}}</ref> होरोविट्ज़ और सानही पर अर्धरित, जिसके <math>O( 2^{n/2}\cdot (n/4))</math> लिए समान रनटाइम की आवश्यकता होती है बहुत कम समिष्ट - <math>O(2^{n/4})</math>. n/2 तत्वों के सभी उपसमूहों को पहले से बनाने और संग्रहीत करने के अतिरिक्त, वे तत्वों को n/4 तत्वों के 4 समुच्चयो में विभाजित करते हैं, और [[न्यूनतम ढेर|न्यूनतम]] समूह का उपयोग करके गतिशील रूप से n/2 तत्व जोड़े के उपसमुच्चय उत्पन्न करते हैं, जो उपरोक्त समय प्राप्त करता है और अंतरिक्ष की जटिलताएँ क्योंकि यह किया जा सकता है इस प्रकार <math>O(k^{2}\log(k))</math> और समिष्ट <math>O(k)</math> लंबाई k की 4 सूचियाँ दी गई हैं।
-स्थान आवश्यकताओं के कारण, एचएस एल्गोरिदम लगभग 50 पूर्णांकों तक के लिए व्यावहारिक है, और एसएस एल्गोरिदम 100 पूर्णांकों तक के लिए व्यावहारिक है।<ref name=":0" />
+समिष्ट आवश्यकताओं के कारण, एचएस एल्गोरिदम लगभग 50 पूर्णांकों तक के लिए व्यावहारिक है, और एसएस एल्गोरिदम 100 पूर्णांकों तक के लिए व्यावहारिक है।<ref name=":0" />
 === हाउग्रेव-ग्राहम और जौक्स ===
-में, हाउग्रेव-ग्राहम और जौक्स<ref>{{Cite book|last1=Howgrave-Graham|first1=Nick|last2=Joux|first2=Antoine|title=Advances in Cryptology – EUROCRYPT 2010 |chapter=New Generic Algorithms for Hard Knapsacks |date=2010|editor-last=Gilbert|editor-first=Henri|series=Lecture Notes in Computer Science|volume=6110|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=235–256|doi=10.1007/978-3-642-13190-5_12|isbn=978-3-642-13190-5|doi-access=free}}</ref> एक [[संभाव्य एल्गोरिथ्म]] प्रस्तुत किया जो पिछले सभी एल्गोरिदम की तुलना में समय में तेजी से चलता है <math>O(2^{.337n})</math> स्थान का उपयोग करना <math>O(2^{.256n})</math>. यह केवल निर्णय की समस्या को हल करता है, यह साबित नहीं कर सकता कि किसी दिए गए योग का कोई समाधान नहीं है, और टी के निकटतम सबसेट योग को वापस नहीं करता है।
+में, हाउग्रेव-ग्राहम और जौक्स <ref>{{Cite book|last1=Howgrave-Graham|first1=Nick|last2=Joux|first2=Antoine|title=Advances in Cryptology – EUROCRYPT 2010 |chapter=New Generic Algorithms for Hard Knapsacks |date=2010|editor-last=Gilbert|editor-first=Henri|series=Lecture Notes in Computer Science|volume=6110|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=235–256|doi=10.1007/978-3-642-13190-5_12|isbn=978-3-642-13190-5|doi-access=free}}</ref> [[संभाव्य एल्गोरिथ्म]] प्रस्तुत किया जो पिछले सभी एल्गोरिदम की तुलना में समय में तेजी से चलता है इस प्रकार <math>O(2^{.337n})</math> समिष्ट का उपयोग करना <math>O(2^{.256n})</math>. यह केवल निर्णय की समस्या को हल करता है, यह सिद्ध नहीं कर सकता कि किसी दिए गए योग का कोई समाधान नहीं है, और T के निकटतम उपसमुच्चय योग को वापस नहीं करता है।
-हाउग्रेव-ग्राहम और जौक्स की तकनीकों को बाद में विस्तारित किया गया <ref>{{Cite book|last1=Becker|first1=Anja|last2=Joux|first2=Antoine|title=Advances in Cryptology – EUROCRYPT 2011 |chapter=Improved Generic Algorithms for Hard Knapsacks |date=2010|editor-last=Gilbert|editor-first=Henri|series=Lecture Notes in Computer Science|volume=6632|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=364–385|doi=10.1007/978-3-642-20465-4_21|isbn=978-3-642-20465-4|doi-access=free}}</ref> समय-जटिलता को लाना <math>O(2^{.291n})</math>.
+हाउग्रेव-ग्राहम और जौक्स की तकनीकों को बाद में विस्तारित किया गया था <ref>{{Cite book|last1=Becker|first1=Anja|last2=Joux|first2=Antoine|title=Advances in Cryptology – EUROCRYPT 2011 |chapter=Improved Generic Algorithms for Hard Knapsacks |date=2010|editor-last=Gilbert|editor-first=Henri|series=Lecture Notes in Computer Science|volume=6632|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=364–385|doi=10.1007/978-3-642-20465-4_21|isbn=978-3-642-20465-4|doi-access=free}}</ref> समय-जटिलता <math>O(2^{.291n})</math> का उपयोग किया जाता है .
-== छद्म-बहुपद समय गतिशील प्रोग्रामिंग समाधान ==
+== छद्म-बहुपद समय गतिशील प्रोग्रामिंग समाधान                                                                                                                                                     ==
-गतिशील प्रोग्रामिंग का उपयोग करके एसएसपी को छद्म-बहुपद समय में हल किया जा सकता है। मान लीजिए कि हमारे पास एक उदाहरण में तत्वों का निम्नलिखित क्रम है:
+गतिशील प्रोग्रामिंग का उपयोग करके एसएसपी को छद्म-बहुपद समय में हल किया जा सकता है। मान लीजिए कि हमारे पास उदाहरण में तत्वों का निम्नलिखित क्रम है:
 :<math>x_1,\ldots, x_N</math>
-हम एक अवस्था को पूर्णांकों के युग्म (i, s) के रूप में परिभाषित करते हैं। यह राज्य इस बात का प्रतिनिधित्व करता है कि
+हम अवस्था को पूर्णांकों के युग्म (i, s) के रूप में परिभाषित करते हैं। यह स्तर इस बात का प्रतिनिधित्व करता है कि अरिक्त उपसमुच्चय <math>x_1,\ldots, x_i</math> है जो {{mvar|s}} बताता है .
-: का एक अरिक्त उपसमुच्चय है <math>x_1,\ldots, x_i</math> जो बताता है {{mvar|s}}.
-प्रत्येक राज्य (i, s) के दो अगले राज्य हैं:
+प्रत्येक स्तर (i, s) के दो अगले स्तर हैं:
-* (i+1, s), जिसका अर्थ है <math>x_{i+1}</math> उपसमूह में शामिल नहीं है;
+* (i+1, s), जिसका अर्थ <math>x_{i+1}</math> है उपसमूह में सम्मिलित नहीं है;
-* (आई+1, एस+<math>x_{i+1}</math>), जिसका अर्थ है <math>x_{i+1}</math> उपसमुच्चय में सम्मिलित है।
+* (i+1, s+<math>x_{i+1}</math>), जिसका अर्थ <math>x_{i+1}</math> है उपसमुच्चय में सम्मिलित है।
-प्रारंभिक स्थिति (0, 0) से शुरू करके, स्थिति (एन, टी) की खोज के लिए किसी भी ग्राफ़ खोज एल्गोरिदम (उदाहरण के लिए चौड़ाई-पहली खोज) का उपयोग करना संभव है। यदि स्थिति पाई जाती है, तो पीछे जाकर हम बिल्कुल टी के योग के साथ एक उपसमुच्चय पा सकते हैं।
+प्रारंभिक स्थिति (0, 0) से प्रारंभ करके, स्थिति (n, t) की खोज के लिए किसी भी ग्राफ़ खोज एल्गोरिदम (उदाहरण के लिए चौड़ाई-पहली खोज) का उपयोग करना संभव है। यदि स्थिति पाई जाती है, तो पीछे जाकर हम पुर्णतः T के योग के साथ उपसमुच्चय पा सकते हैं।
-इस एल्गोरिदम का रन-टाइम राज्यों की संख्या में अधिकतम रैखिक है। राज्यों की संख्या विभिन्न संभावित योगों की संख्या से अधिकतम N गुना है। होने देना {{mvar|A}} ऋणात्मक मानों का योग हो और {{mvar|B}} सकारात्मक मानों का योग; विभिन्न संभावित योगों की संख्या अधिकतम B-A है, इसलिए कुल रनटाइम है <math>O(N(B-A))</math>. उदाहरण के लिए, यदि सभी इनपुट मान सकारात्मक हैं और कुछ स्थिरांक C से बंधे हैं, तो B अधिकतम N C है, इसलिए आवश्यक समय है <math>O(N^{2}C)</math>.
+इस एल्गोरिदम का रन-टाइम स्तरों की संख्या में अधिकतम रैखिक है। स्तरों की संख्या विभिन्न संभावित योगों की संख्या से अधिकतम N गुना है। माना {{mvar|A}} ऋणात्मक मानों का योग हो और {{mvar|B}} धनात्मक मानों का योग; विभिन्न संभावित योगों की संख्या अधिकतम B-A है, इसलिए कुल रनटाइम <math>O(N(B-A))</math> है . उदाहरण के लिए, यदि सभी इनपुट मान धनात्मक हैं और कुछ स्थिरांक C से बंधे हैं, तो B अधिकतम N C है, इसलिए आवश्यक समय <math>O(N^{2}C)</math> है .
-यह समाधान जटिलता सिद्धांत में बहुपद समय के रूप में नहीं गिना जाता है क्योंकि <math>B-A</math> समस्या के आकार में बहुपद नहीं है, जो कि इसे दर्शाने के लिए उपयोग की जाने वाली बिट्स की संख्या है। यह एल्गोरिथम के मानों में बहुपद है {{mvar|A}} और {{mvar|B}}, जो बिट्स की संख्या में घातीय हैं। हालाँकि, यूनरी में एन्कोड किया गया सबसेट योग P में है, तब से एन्कोडिंग का आकार B-A में रैखिक है। इसलिए, सबसेट योग केवल कमजोर एनपी-पूर्ण है।
+यह समाधान जटिलता सिद्धांत में बहुपद समय के रूप में नहीं गिना जाता है क्योंकि <math>B-A</math> समस्या के आकार में बहुपद नहीं है, जो कि इसे दर्शाने के लिए उपयोग की जाने वाली बिट्स की संख्या है। यह एल्गोरिथम के मानों {{mvar|A}} और {{mvar|B}} में बहुपद है, जो बिट्स की संख्या में घातीय हैं। चूँकि, यूनरी में n कोड किया गया उपसमुच्चय योग P में है, तब से n कोडिंग का आकार B-A में रैखिक है। इसलिए, उपसमुच्चय योग केवल अशक्त np-पूर्ण है।
-इस मामले के लिए कि प्रत्येक <math>x_i</math> सकारात्मक है और एक निश्चित स्थिरांक से घिरा है {{mvar|C}}, 1999 में, पिसिंगर ने समय जटिलता वाला एक रैखिक समय एल्गोरिदम पाया <math>O(NC)</math> (ध्यान दें कि यह समस्या के उस संस्करण के लिए है जहां लक्ष्य योग आवश्यक रूप से शून्य नहीं है, अन्यथा समस्या तुच्छ होगी)।<ref name="Pisinger09">{{cite journal | last = Pisinger | first = David | doi = 10.1006/jagm.1999.1034 | issue = 1 | journal = Journal of Algorithms | mr = 1712690 | pages = 1–14 | title = सीमित वजन के साथ बस्ता समस्याओं के लिए रैखिक समय एल्गोरिदम| volume = 33 | year = 1999}}</ref> 2015 में, कोइलियारिस और जू ने एक नियतिवादी पाया <math>\tilde{O}(T \sqrt N)</math> सबसेट योग समस्या के लिए एल्गोरिदम जहां {{mvar|T}} वह योग है जिसे हमें खोजने की आवश्यकता है।<ref>{{Cite arXiv|title = सबसेट योग के लिए एक तेज़ छद्मबहुपद समय एल्गोरिदम|eprint = 1507.02318 |date = 2015-07-08|first1 = Konstantinos|last1 = Koiliaris|first2 = Chao|last2 = Xu|class = cs.DS }}</ref> 2017 में, ब्रिंगमैन ने एक यादृच्छिक पाया <math>\tilde{O}(T+N)</math> समय एल्गोरिथ्म.<ref>{{cite conference | last = Bringmann | first = Karl | editor-last = Klein | editor-first = Philip N. | arxiv = 1610.04712 | contribution = A near-linear pseudopolynomial time algorithm for subset sum | doi = 10.1137/1.9781611974782.69 | pages = 1073–1084 | publisher = SIAM | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) | year = 2017}}</ref>
+इस स्थिति के लिए कि प्रत्येक <math>x_i</math> धनात्मक है और निश्चित स्थिरांक {{mvar|C}} से घिरा है , 1999 में, पिसिंगर ने समय जटिलता वाला रैखिक समय एल्गोरिदम पाया <math>O(NC)</math> (ध्यान दें कि यह समस्या के उस संस्करण के लिए है जहां लक्ष्य योग आवश्यक रूप से शून्य नहीं है, अन्यथा समस्या तुच्छ होगी)।<ref name="Pisinger09">{{cite journal | last = Pisinger | first = David | doi = 10.1006/jagm.1999.1034 | issue = 1 | journal = Journal of Algorithms | mr = 1712690 | pages = 1–14 | title = सीमित वजन के साथ बस्ता समस्याओं के लिए रैखिक समय एल्गोरिदम| volume = 33 | year = 1999}}</ref> 2015 में, कोइलियारिस और जू ने नियतिवादी पाया <math>\tilde{O}(T \sqrt N)</math> उपसमुच्चय योग समस्या के लिए एल्गोरिदम जहां {{mvar|T}} वह योग है जिसे हमें खोजने की आवश्यकता है।<ref>{{Cite arXiv|title = सबसेट योग के लिए एक तेज़ छद्मबहुपद समय एल्गोरिदम|eprint = 1507.02318 |date = 2015-07-08|first1 = Konstantinos|last1 = Koiliaris|first2 = Chao|last2 = Xu|class = cs.DS }}</ref> 2017 में, ब्रिंगमैन ने यादृच्छिक पाया <math>\tilde{O}(T+N)</math> समय एल्गोरिथ्म.<ref>{{cite conference | last = Bringmann | first = Karl | editor-last = Klein | editor-first = Philip N. | arxiv = 1610.04712 | contribution = A near-linear pseudopolynomial time algorithm for subset sum | doi = 10.1137/1.9781611974782.69 | pages = 1073–1084 | publisher = SIAM | title = Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) | year = 2017}}</ref> 2014 में, कर्टिस और सांचेस ने [[SIMD|सिमड]] मशीनों में अत्यधिक स्केलेबल सरल रिकर्सन पाया गया था <math>O(N(m-x_{\min})/p)</math> समय और <math>O(N+m-x_{\min})</math> समिष्ट, जहाँ {{mvar|p}} प्रसंस्करण तत्वों की संख्या है, इस प्रकार <math>m=\min(s, \sum x_i - s)</math> और <math>x_{\min}</math> निम्नतम पूर्णांक है.<ref>{{cite journal |last1=Curtis |first1=V. V. |last2=Sanches |first2=C. A. A. |title=An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU |journal=Concurrency and Computation: Practice and Experience |date=January 2016 |volume=28 |issue=1 |pages=95–113 |doi=10.1002/cpe.3636|s2cid=20927927 }}</ref> यह अब तक ज्ञात सर्वोत्तम सैद्धांतिक समानांतर जटिलता है।
-में, कर्टिस और सांचेस ने [[SIMD]] मशीनों में अत्यधिक स्केलेबल एक सरल रिकर्सन पाया <math>O(N(m-x_{\min})/p)</math> समय और <math>O(N+m-x_{\min})</math> स्थान, कहाँ {{mvar|p}} प्रसंस्करण तत्वों की संख्या है, <math>m=\min(s, \sum x_i - s)</math> और <math>x_{\min}</math> निम्नतम पूर्णांक है.<ref>{{cite journal |last1=Curtis |first1=V. V. |last2=Sanches |first2=C. A. A. |title=An efficient solution to the subset-sum problem on GPU: An efficient solution to the subset-sum problem on GPU |journal=Concurrency and Computation: Practice and Experience |date=January 2016 |volume=28 |issue=1 |pages=95–113 |doi=10.1002/cpe.3636|s2cid=20927927 }}</ref> यह अब तक ज्ञात सर्वोत्तम सैद्धांतिक समानांतर जटिलता है।
 व्यावहारिक परिणामों की तुलना और एसएसपी के कठिन उदाहरणों के समाधान पर कर्टिस और सांचेस द्वारा चर्चा की गई है।<ref>{{cite journal |last1=Curtis |first1=V. V. |last2=Sanches |first2=C. A. A. |title=जीपीयू पर सबसेट-सम समस्या के लिए एक कम-स्थान एल्गोरिथ्म|journal=Computers & Operations Research |date=July 2017 |volume=83 |pages=120–124 |doi=10.1016/j.cor.2017.02.006}}</ref>
+== बहुपद समय सन्निकटन एल्गोरिदम                                                                                                                                                                       ==
+मान लीजिए कि सभी इनपुट धनात्मक हैं। एसएसपी के लिए सन्निकटन एल्गोरिदम का लक्ष्य अधिकतम T के योग और इष्टतम योग के कम से कम आर गुना के साथ एस का उपसमूह खोजना है, जहां आर (0,1) में संख्या है जिसे सन्निकटन अनुपात कहा जाता है।
-== बहुपद समय सन्निकटन एल्गोरिदम ==
-{{More citations needed section|date=February 2021}}
-मान लीजिए कि सभी इनपुट सकारात्मक हैं। एसएसपी के लिए एक सन्निकटन एल्गोरिदम का लक्ष्य अधिकतम टी के योग और इष्टतम योग के कम से कम आर गुना के साथ एस का एक उपसमूह ढूंढना है, जहां आर (0,1) में एक संख्या है जिसे सन्निकटन अनुपात कहा जाता है।
 === सरल 1/2-अनुमान ===
 निम्नलिखित अत्यंत सरल एल्गोरिदम का अनुमानित अनुपात 1/2 है:<ref name=":1">{{Cite journal|last1=Caprara|first1=Alberto|last2=Kellerer|first2=Hans|last3=Pferschy|first3=Ulrich|date=2000-02-01|title=एकाधिक उपसमुच्चय योग समस्या|url=https://doi.org/10.1137/S1052623498348481|journal=SIAM Journal on Optimization|volume=11|issue=2|pages=308–319|doi=10.1137/S1052623498348481|issn=1052-6234}}</ref>
-* इनपुट को घटते मूल्य के आधार पर क्रमबद्ध करें;
+* इनपुट को घटते मूल्य के अर्धर पर क्रमबद्ध करें;
-* अगले सबसे बड़े इनपुट को सबसेट में रखें, जब तक वह वहां फिट बैठता है।
+* अगले सबसे बड़े इनपुट को उपसमुच्चय में रखें, जब तक वह वहां फिट बैठता है।
+जब यह एल्गोरिदम समाप्त हो जाता है, तो या तो सभी इनपुट उपसमुच्चय में होते हैं (जो स्पष्ट रूप से इष्टतम है), या इनपुट है जो फिट नहीं होता है। ऐसा पहला इनपुट पिछले सभी इनपुट से छोटा है जो उपसमुच्चय में हैं और उपसमुच्चय में इनपुट का योग T/2 से अधिक है अन्यथा इनपुट भी T/2 से कम है और यह समुच्चय में फिट होता है। T/2 से अधिक ऐसी राशि स्पष्ट रूप से ऑप्ट/2 से अधिक है।
-जब यह एल्गोरिदम समाप्त हो जाता है, तो या तो सभी इनपुट सबसेट में होते हैं (जो स्पष्ट रूप से इष्टतम है), या एक इनपुट है जो फिट नहीं होता है। ऐसा पहला इनपुट पिछले सभी इनपुट से छोटा है जो उपसमुच्चय में हैं और उपसमुच्चय में इनपुट का योग T/2 से अधिक है अन्यथा इनपुट भी T/2 से कम है और यह सेट में फिट होगा। T/2 से अधिक ऐसी राशि स्पष्ट रूप से OPT/2 से अधिक है।
+=== पूर्ण-बहुपद समय सन्निकटन योजना ===
+निम्नलिखित एल्गोरिदम प्रत्येक <math>\epsilon>0</math> के लिए प्राप्त करता है ,<math>(1-\epsilon)</math> का अनुमानित अनुपात . इसका रन टाइम {{mvar|n}} और <math>1/\epsilon</math> बहुपद है. याद रखें कि n इनपुट की संख्या है और T उपसमुच्चय योग की ऊपरी सीमा है।<syntaxhighlight lang="abl">
+initialize a list L to contain one element 0.
-=== पूर्ण-बहुपद समय सन्निकटन योजना{{Anchor|FPTAS}} ===
+for each i from 1 to n do
-निम्नलिखित एल्गोरिदम प्रत्येक के लिए प्राप्त करता है <math>\epsilon>0</math>, का एक अनुमानित अनुपात <math>(1-\epsilon)</math>. इसका रन टाइम बहुपद है {{mvar|n}} और <math>1/\epsilon</math>. याद रखें कि n इनपुट की संख्या है और T उपसमुच्चय योग की ऊपरी सीमा है।
+    let Ui be a list containing all elements y in L, and all sums xi + y for all y in L.
- एक तत्व 0 को शामिल करने के लिए सूची L को प्रारंभ करें।
+    sort Ui in ascending order
+    make L empty
- 'प्रत्येक के लिए' मैं 1 से n तक 'करता हूँ'
+    let y be the smallest element of Ui
-     चलो यू<sub>i</sub>एक सूची बनें जिसमें L में सभी तत्व y और सभी योग x हों<sub>i</sub>एल में सभी y के लिए + y।
+    add y to L
-     यू क्रमित करें<sub>i</sub>बढ़ते क्रम में
+    for each element z of Ui in increasing order do
-     L को खाली करें
+        // Trim the list by eliminating numbers close to one another
-     माना कि y, U का सबसे छोटा तत्व है<sub>i</sub>L में y जोड़ें
+        // and throw out elements greater than the target sum T.
-     यू के 'प्रत्येक' तत्व z के लिए<sub>i</sub>बढ़ते क्रम में 'करो'
+        if y +  ε T/n < z ≤ T then
-         <u>// एक दूसरे के करीब संख्याओं को हटाकर सूची को ट्रिम करें</u>
+            y = z
-         <u>// और लक्ष्य योग T से अधिक तत्वों को बाहर फेंक दें।</u>
+            add z to L
-         'यदि' y + ε T/n < z ≤ T 'तब'
-             y = z
-             L में z जोड़ें
- एल में सबसे बड़ा तत्व 'रिटर्न' करें।
-ध्यान दें कि ट्रिमिंग चरण (प्रत्येक लूप के लिए आंतरिक) के बिना, सूची एल में सभी का योग शामिल होगा <math>2^n</math> इनपुट के सबसेट. ट्रिमिंग चरण दो काम करता है:
+return the largest element in L.
+</syntaxhighlight>ध्यान दें कि ट्रिमिंग चरण (प्रत्येक लूप के लिए आंतरिक) के बिना, सूची L में सभी <math>2^n</math> का योग सम्मिलित होगा इनपुट के उपसमुच्चय. ट्रिमिंग चरण दो काम करता है:
 * यह सुनिश्चित करता है कि L में शेष सभी राशियाँ T से नीचे हैं, इसलिए वे उप-योग समस्या का व्यवहार्य समाधान हैं।
-* यह सुनिश्चित करता है कि सूची एल विरल है, यानी, प्रत्येक दो लगातार आंशिक-योगों के बीच का अंतर कम से कम है <math>\epsilon T/n</math>.
+* यह सुनिश्चित करता है कि सूची L विरल है, अर्थात, प्रत्येक दो निरंतर आंशिक-योगों के बीच <math>\epsilon T/n</math> का अंतर कम से कम है .
-ये गुण मिलकर सूची की गारंटी देते हैं {{mvar|L}} से अधिक नहीं है <math>n/\epsilon</math> तत्व; इसलिए रन-टाइम बहुपद है <math>n/\epsilon</math>.
+ये गुण मिलकर सूची की आश्वासन देते हैं {{mvar|L}} से अधिक <math>n/\epsilon</math> तत्व नहीं है; इसलिए रन-टाइम <math>n/\epsilon</math> बहुपद है .
-जब एल्गोरिदम समाप्त होता है, यदि इष्टतम योग होता है {{mvar|L}}, फिर इसे वापस कर दिया जाता है और हमारा काम हो जाता है। अन्यथा, इसे पिछले ट्रिमिंग चरण में हटा दिया गया होगा। प्रत्येक ट्रिमिंग चरण अधिकतम एक योगात्मक त्रुटि प्रस्तुत करता है <math>\epsilon T/n</math>,  इसलिए {{mvar|n}} चरण एक साथ अधिकतम की त्रुटि प्रस्तुत करते हैं <math>\epsilon T</math>. इसलिए, लौटाया गया समाधान कम से कम है <math>\text{OPT}-\epsilon T</math> जो कम से कम है <math>(1-\epsilon)\text{OPT}</math> .
+जब एल्गोरिदम समाप्त होता है, यदि इष्टतम {{mvar|L}} योग होता है , फिर इसे वापस कर दिया जाता है और हमारा काम हो जाता है। अन्यथा, इसे पिछले ट्रिमिंग चरण में हटा दिया गया होता है। प्रत्येक ट्रिमिंग चरण अधिकतम योगात्मक त्रुटि <math>\epsilon T/n</math> प्रस्तुत करता है , इसलिए {{mvar|n}} चरण साथ अधिकतम की त्रुटि प्रस्तुत करते हैं . इसलिए, <math>\text{OPT}-\epsilon T</math> लौटाया गया समाधान कम से कम है जो <math>(1-\epsilon)\text{OPT}</math> कम से कम है .
-उपरोक्त एल्गोरिदम उस स्थिति में एसएसपी का सटीक समाधान प्रदान करता है जब इनपुट संख्या छोटी (और गैर-नकारात्मक) होती है। यदि संख्याओं का कोई योग अधिक से अधिक निर्दिष्ट किया जा सकता है {{mvar|P}} बिट्स, फिर समस्या को लगभग हल करना <math>\epsilon = 2^{-P}</math> इसे बिल्कुल हल करने के बराबर है। फिर, अनुमानित उपसमुच्चय के लिए बहुपद समय एल्गोरिथ्म रनिंग टाइम बहुपद के साथ एक सटीक एल्गोरिदम बन जाता है {{mvar|n}} और <math>2^P</math> (अर्थात, घातीय में {{mvar|P}}).
+उपरोक्त एल्गोरिदम उस स्थिति में एसएसपी का स्पष्ट समाधान प्रदान करता है जब इनपुट संख्या छोटी (और गैर-ऋणात्मक) होती है। यदि संख्याओं का कोई योग अधिक से अधिक {{mvar|P}} बिट्स निर्दिष्ट किया जा सकता है, फिर समस्या को लगभग हल करना <math>\epsilon = 2^{-P}</math> है इसे पुर्णतः हल करने के समान है। फिर, अनुमानित उपसमुच्चय के लिए बहुपद समय एल्गोरिथ्म रनिंग टाइम बहुपद के साथ स्पष्ट एल्गोरिदम {{mvar|n}} और <math>2^P</math> बन जाता है (अर्थात, घातीय में {{mvar|P}}).
-केलरर, मैनसिनी, पफ़रस्की और स्पेरान्ज़ा<ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Mansini|first2=Renata|last3=Pferschy|first3=Ulrich|last4=Speranza|first4=Maria Grazia|date=2003-03-01|title=उपसमुच्चय-योग समस्या के लिए एक कुशल पूर्णतः बहुपद सन्निकटन योजना|journal=Journal of Computer and System Sciences|language=en|volume=66|issue=2|pages=349–370|doi=10.1016/S0022-0000(03)00006-0|issn=0022-0000|doi-access=free}}</ref> और केलरर, पफ़रस्की और पिसिंगर<ref name="knapsack">{{cite book|author1=Hans Kellerer|title=बस्ते की समस्या|url=https://books.google.com/books?id=u5DB7gck08YC&pg=PA97|page=97|year=2004|publisher=Springer|isbn=9783540402862|author2=Ulrich Pferschy|author3=David Pisinger}}</ref> उपसमुच्चय राशि के लिए अन्य FPTAS-s प्रस्तुत करें।
+केलरर, मैनसिनी, पफ़रस्की और स्पेरान्ज़ा <ref>{{Cite journal|last1=Kellerer|first1=Hans|last2=Mansini|first2=Renata|last3=Pferschy|first3=Ulrich|last4=Speranza|first4=Maria Grazia|date=2003-03-01|title=उपसमुच्चय-योग समस्या के लिए एक कुशल पूर्णतः बहुपद सन्निकटन योजना|journal=Journal of Computer and System Sciences|language=en|volume=66|issue=2|pages=349–370|doi=10.1016/S0022-0000(03)00006-0|issn=0022-0000|doi-access=free}}</ref> और केलरर, पफ़रस्की और पिसिंगर <ref name="knapsack">{{cite book|author1=Hans Kellerer|title=बस्ते की समस्या|url=https://books.google.com/books?id=u5DB7gck08YC&pg=PA97|page=97|year=2004|publisher=Springer|isbn=9783540402862|author2=Ulrich Pferschy|author3=David Pisinger}}</ref> उपसमुच्चय राशि के लिए अन्य एफपीटीएएस-s प्रस्तुत करें।
-== यह भी देखें ==
+== यह भी देखें                                                                                                                                    ==
-* नैपसेक समस्या - एसएसपी का एक सामान्यीकरण जिसमें प्रत्येक इनपुट आइटम का एक मूल्य और एक वजन दोनों होता है। लक्ष्य मूल्य को अधिकतम करना है ताकि कुल वजन सीमित हो जाए।
+* नैपसेक समस्या - एसएसपी का सामान्यीकरण जिसमें प्रत्येक इनपुट आइटम का मूल्य और वजन दोनों होता है। लक्ष्य मूल्य को अधिकतम करना है जिससे कुल वजन सीमित हो जाता है।
-*[[एकाधिक उपसमुच्चय योग समस्या]] - एसएसपी का एक सामान्यीकरण जिसमें व्यक्ति को कई उपसमुच्चय चुनने चाहिए।
+*[[एकाधिक उपसमुच्चय योग समस्या]] - एसएसपी का सामान्यीकरण जिसमें व्यक्ति को कई उपसमुच्चय चुनने चाहिए।
 *3योग
 * मर्कल-हेलमैन नैपसेक क्रिप्टोसिस्टम
-== संदर्भ ==
+== संदर्भ                                                                                                                                                                                     ==
 {{reflist}}
 ==अग्रिम पठन==
 * {{Introduction to Algorithms|2|chapter=35.5: The subset-sum problem}}
@@ Line 147: / Line 132: @@
 * {{cite book|last1=Martello|first1=Silvano|title=Knapsack problems: Algorithms and computer interpretations|last2=Toth|first2=Paolo|publisher=Wiley-Interscience|year=1990|isbn=0-471-92420-2|pages=[https://archive.org/details/knapsackproblems0000mart/page/105 105–136]|chapter=4 Subset-sum problem|mr=1086874|chapter-url=https://archive.org/details/knapsackproblems0000mart/page/105}}
-{{DEFAULTSORT:Subset Sum Problem}}[[Category: कमजोर एनपी-पूर्ण समस्याएं]] [[Category: गतिशील प्रोग्रामिंग]] [[Category: स्यूडोकोड उदाहरण सहित लेख]]
+{{DEFAULTSORT:Subset Sum Problem}}
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
-[[Category:Created On 08/07/2023]]
+[[Category:CS1 errors]]
+[[Category:CS1 maint]]
+[[Category:Created On 08/07/2023|Subset Sum Problem]]
+[[Category:Lua-based templates|Subset Sum Problem]]
+[[Category:Machine Translated Page|Subset Sum Problem]]
+[[Category:Pages with script errors|Subset Sum Problem]]
+[[Category:Templates Vigyan Ready|Subset Sum Problem]]
+[[Category:Templates that add a tracking category|Subset Sum Problem]]
+[[Category:Templates that generate short descriptions|Subset Sum Problem]]
+[[Category:Templates using TemplateData|Subset Sum Problem]]
+[[Category:कमजोर एनपी-पूर्ण समस्याएं|Subset Sum Problem]]
+[[Category:गतिशील प्रोग्रामिंग|Subset Sum Problem]]
+[[Category:स्यूडोकोड उदाहरण सहित लेख|Subset Sum Problem]]

Anonymous

Search

उपसमुच्चय योग समस्या: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 14:01, 28 July 2023

Contents

कम्प्यूटेशनल कठोरता