Knapsack समस्या पर एक बदलाव: जावा में विभाजन समान सबसेट सम समस्या को कैसे हल करें

अपडेट: डायनामिक प्रोग्रामिंग सॉल्यूशन की स्पेस जटिलता को मेरे फॉलो-अप आर्टिकल में यहाँ पर अनुकूलित करने के बारे में पढ़ें।

पहले, मैंने डायनेमिक प्रोग्रामिंग के साथ नैकसैक समस्या (केपी) को हल करने के बारे में लिखा था। आप इसके बारे में यहां पढ़ सकते हैं।

आज मैं केपी की भिन्नता पर चर्चा करना चाहता हूं: विभाजन समान उप-योग समस्या। मैंने पहली बार Leetcode पर इस समस्या को देखा - यही मुझे केपी के बारे में जानने और लिखने के लिए प्रेरित किया।

यह समस्या कथन (उदाहरण के बिना आंशिक रूप से पुन: प्रस्तुत) है:

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

पूर्ण समस्या बयान के लिए, बाधाओं और उदाहरणों के साथ, लेटकोड समस्या की जांच करें।

गतिशील प्रोग्रामिंग

केपी की तरह, हम गतिशील प्रोग्रामिंग का उपयोग करके इसे हल करेंगे। चूंकि यह केपी की भिन्नता है, इसलिए तर्क और कार्यप्रणाली काफी हद तक समान है।

समाधान

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

चरण 1: विषम सरणी योग के खिलाफ रखवाली

तुच्छ रूप से, यदि सरणी में सभी संख्या एक विषम राशि में जोड़ते हैं, तो हम झूठे वापस आ सकते हैं। हम केवल तभी आगे बढ़ते हैं जब सरणी एक सम योग में जुड़ जाती है।

चरण 2: तालिका बनाना

अगला, हम तालिका बनाते हैं।

तालिका पंक्तियों को माना जाने वाले सरणी तत्वों के समूह का प्रतिनिधित्व करता है, जबकि तालिका कॉलम उस राशि को इंगित करता है जिस राशि पर हम पहुंचना चाहते हैं। तालिका मान बस बूलियन मान हैं, यह दर्शाता है कि एक योग (स्तंभ) सरणी तत्वों (पंक्ति) के एक सेट के साथ आ सकता है।

लगातार, पंक्ति i सूचक 0 से (i-1) तक सरणी तत्वों के एक समूह का प्रतिनिधित्व करता है। 1 के इस ऑफसेट का कारण है क्योंकि पंक्ति 0 तत्वों के एक खाली सेट का प्रतिनिधित्व करता है। इसलिए, पंक्ति 1 पहले सरणी तत्व (सूचकांक 0) का प्रतिनिधित्व करती है, पंक्ति 2 पहले दो सरणी तत्वों (सूचक 0-1) का प्रतिनिधित्व करती है, और इसी तरह। कुल में, हम n + 1 पंक्तियों का निर्माण करते हैं, जिसमें 0 शामिल हैं।

हम केवल यह जानना चाहते हैं कि क्या हम सरणी के कुल योग का ठीक आधा योग कर सकते हैं। इसलिए हमें केवल कुल 0/2 + 1 कॉलम बनाने की आवश्यकता है, जिसमें 0 शामिल हैं।

चरण 3: तालिका को पूर्व-भरना

हम तुरंत अपनी तालिका - पंक्ति 0 और कॉलम 0 में आधार मामलों के लिए प्रविष्टियाँ भरना शुरू कर सकते हैं।

पहली पंक्ति में, प्रत्येक प्रविष्टि - पहली को छोड़कर - झूठी होनी चाहिए। याद रखें कि पहली पंक्ति एक खाली सेट का प्रतिनिधित्व करती है। स्वाभाविक रूप से, हम 0 को छोड़कर किसी भी लक्ष्य राशि - कॉलम संख्या - पर पहुंचने में असमर्थ हैं।

पहले कॉलम में, हर प्रविष्टि सही होनी चाहिए। हम हमेशा, तुच्छ रूप से, 0 के लक्ष्य राशि पर पहुंच सकते हैं, भले ही हमें जिन तत्वों के साथ काम करना है।

चरण 4: तालिका का निर्माण (समस्या की जड़)

पंक्ति i और स्तंभ j में तालिका में कुछ प्रविष्टि सत्य है (प्राप्य) यदि निम्नलिखित तीन शर्तों में से एक संतुष्ट हो:

  1. पंक्ति i-1 और कॉलम j में प्रविष्टि सत्य है। याद रखें कि पंक्ति संख्या क्या दर्शाती है। इसलिए, यदि हम वर्तमान में हमारे पास मौजूद तत्वों के सबसेट के साथ एक विशेष योग प्राप्त करने में सक्षम हैं, तो हम तत्वों के अपने वर्तमान सेट के साथ उस राशि को भी प्राप्त कर सकते हैं - बस अतिरिक्त तत्वों का उपयोग नहीं करके। यह तुच्छ है। आइए इस कॉल को prevRowIsTrue करें।
  2. वर्तमान तत्व वह योग है जिसे हम प्राप्त करना चाहते हैं। यह भी तुच्छ रूप से सत्य है। चलिए इसे'ExactMatch 'कहते हैं।
  3. यदि उपरोक्त दो शर्तें संतुष्ट नहीं हैं, तो हमारे पास अपना लक्ष्य प्राप्त करने का एक शेष तरीका है। यहां, हम वर्तमान तत्व का उपयोग करते हैं - पिछली पंक्ति में तत्वों के सेट की तुलना में हमारी वर्तमान पंक्ति में तत्वों के सेट में अतिरिक्त तत्व - और जांचें कि हम लक्ष्य राशि के शेष को प्राप्त करने में सक्षम हैं। आइए इस पर कॉल करें ।ArriveAtSum

चलिए अनपैक होने की स्थिति 3. हम केवल वर्तमान तत्व का उपयोग कर सकते हैं यदि यह हमारे लक्ष्य योग से कम है। यदि वे समान हैं, तो शर्त 2 संतुष्ट होगी। यदि यह बड़ा है, तो हम इसका उपयोग नहीं कर सकते हैं। इसलिए, पहला कदम यह सुनिश्चित करना है कि वर्तमान तत्व <लक्ष्य राशि।

हमारे वर्तमान तत्व का उपयोग करने के बाद, हम शेष लक्ष्य राशि के साथ छोड़ दिए जाते हैं। हम तब जांचते हैं कि क्या ऊपर की पंक्ति में संबंधित प्रविष्टि की जाँच करके प्राप्य है।

नियमित केपी के रूप में, हम नीचे-ऊपर से उत्तरोत्तर अपनी तालिका बनाना चाहते हैं। हम आधार मामलों से शुरू करते हैं, जब तक कि हम अपने अंतिम समाधान पर नहीं पहुंच जाते।

चरण 5: उत्तर लौटाते हुए

हम केवल रिटर्न मैट [nums.length] [TotalSum / 2] लौटाते हैं।

कार्य कोड

पढ़ने के लिए धन्यवाद!