Subset Sum और Partition

संख्याएँ और एक लक्ष्य दिए होने पर, क्या कोई उपसमुच्चय ठीक उसी लक्ष्य के बराबर योग दे सकता है? यह वह थैला-समस्या है जिसमें मूल्य और भार बराबर होते हैं।

यहाँ आप अधिकतम मान नहीं, बल्कि पहुँच-योग्यता देखते हैं। मान लीजिए dp[s] True है, जब कोई उपसमुच्चय ठीक s का योग देता है।

रिक्त उपसमुच्चय का योग शून्य होता है, इसलिए dp[0] की शुरुआत True से होती है। हर दूसरी राशि तब तक False रहती है, जब तक कोई संख्या उसके पहुँच योग्य होने को सिद्ध न कर दे।

हर संख्या के लिए s को पहुँच योग्य चिह्नित कीजिए, यदि s - num पहले से पहुँच योग्य था। एक संख्या कई राशियों को True में बदल सकती है।

हर संख्या का उपयोग अधिकतम एक बार होता है, इसलिए भीतरी लूप पीछे की ओर चलता है, ठीक 0/1 थैला-समस्या की तरह। आगे की ओर चलने पर संख्या का पुनः उपयोग होगा।

सभी संख्याओं को संसाधित करने के बाद dp[target] प्रश्न का उत्तर देता है। True का अर्थ है कि कोई मान्य उपसमुच्चय मौजूद है; False का अर्थ है कि यह असंभव है।

विभाजन समस्या पूछती है: क्या आप सारणी को समान योग वाले दो भागों में बाँट सकते हैं? यह सीधे उपसमुच्चय योग की समस्या में बदल जाती है।

यदि कुल योग विषम है, तो समान भाग असंभव हैं, इसलिए तुरंत नहीं का उत्तर दीजिए। अन्यथा लक्ष्य बस total // 2 है।

अब केवल यह पूछिए कि क्या कोई उपसमुच्चय total // 2 तक पहुँचता है। यदि एक भाग लक्ष्य तक पहुँच जाता है, तो शेष भाग अपने-आप मेल खाता हुआ दूसरा भाग बन जाता है।

लागत n गुणा लक्ष्य के क्रम की है, यानी छद्म-बहुपदीय सीमा। लक्ष्य छोटा हो तो यह तेज़ है, लेकिन योग बहुत बड़े हों तो धीमा।

उपसमुच्चय योग, विभाजन और 0/1 नैपसैक में एक ही आधारभूत विधि साझा होती है। लेने-या-छोड़ने वाला ढाँचा पहचानिए और उसी लूप का फिर से उपयोग कीजिए।

आपने बूलियन DP और पीछे की ओर चलने वाले लूप से उपसमुच्चय योग हल किया, फिर विभाजन को कुल योग // 2 तक पहुँचने में बदल दिया। वही आधारभूत विधि, नई सफलताएँ। ✅