नकारात्मक संख्याओं के साथ सब्सक्राइबर योग - जावा, एल्गोरिदम, गतिशील प्रोग्रामिंग, सबसेट-योग

इसलिए मेरे पास एन पॉजिटिव पूर्णांकों का एक सेट C है(c_1, ..., c_n)। कार्य सी के दो सबसेट ए और बी खोजने के लिए है, जहां ए में केवल सकारात्मक संख्याएं होती हैं और बी में सी में संख्याओं के केवल नकारात्मक होते हैं। दो सबसेट ए और बी का योग फिर संख्या डी तक होना चाहिए हमेशा सकारात्मक है)। मुझे यह पता लगाने की जरूरत है कि क्या दो ऐसे उपसमुच्चय हैं और यदि हां, तो उनमें कौन सी संख्या है।

For example: {3, 5, 6, 13, 24} // d = 12 => solution: true: {5, 13} {-6}

मुझे पता है कि यह सबसेट राशि का बदलाव हैसमस्या और मैंने "एक समान समस्या के लिए कुछ समाधान देखे (ऋणात्मक संख्याओं के साथ सबसेट) लेकिन मुझे गतिशील प्रोग्रामिंग का उपयोग करके समस्या को हल करने की आवश्यकता है। अधिकांश समाधान मैंने" पुनरावृत्ति के साथ देखा, डीपी के साथ नहीं।

मुझे लगता है कि मुझे 3 डी बुलियन टेबल S (i, j, k) की आवश्यकता हैआकार (n * n * d)। लेकिन S (i, j, k) कब सही है और कब गलत? क्योंकि मुझे हमेशा k नंबर का उपयोग करते हुए राशि की गणना करने के लिए सभी संभावित तरीकों की जांच करने की आवश्यकता होती है जहां वे सकारात्मक और नकारात्मक दोनों हो सकते हैं (उदाहरण: 4 नंबर के लिए {1,2,3,4} 2 ^ 4 तरीके हैं उनमें: 1 + 2 + 3 + 4, 1 - 2 + 3 + 4, 1 - 2 - 3 + 4, ..., -1 + 2 - 3 - 4, 1 - 2 - 3 - 4)

क्या मेरी सोच सही है या मैं पहले से ही कुछ गलत कर रहा हूं?

उत्तर:

एक दृष्टिकोण मानक डायनामिक प्रोग्रामिंग सबसेट योग एल्गोरिदम का उपयोग करने के लिए एक सेट पर है (c_1, c_2, ..., c_n, -c_1, -c_2, ..., - c_n)।

यह एक सबसेट पाएगा जो s को d (या साबित करता है कि कोई भी मौजूद नहीं है)।

सबसेट में A को सभी पॉजिटिव नंबर पर सेट करें, और B को सभी नेगेटिव नंबर पर।

आप ए और बी दोनों में दिखाई देने वाली किसी भी संख्या को निकालने की इच्छा कर सकते हैं (जैसे यदि आपके पास ए में 3 और बी में -3 ​​है तो आप राशि को बदले बिना दोनों को निकाल सकते हैं)।