मैं एल्गोरिदम खोजता हूं, जो मुझे एक समस्या की प्राप्ति में मदद करेगा! समस्या इस प्रकार है:
श्रेणियों की एक सूची है, मुझे गैर-अतिव्यापी श्रेणियों (जरूरी नहीं कि आसन्न) के सबसेट के साथ एक सूची बनाने की आवश्यकता है, जैसे कि उनकी लंबाई का योग अधिकतम संभव है।
उदाहरण के लिए, एक इनपुट सूची के लिए
[(-1, 3), (2, 4), (0, 5), (-4, -1)]
वांछित आउटपुट है
[(0, 5), (-4, -1)]
लंबाई के योग के साथ (5 - 0) + ((-1) - (-4)) = 5 + 3 = 8
1 उत्तर
यह अधिकतम भारित स्वतंत्र समुच्चय समस्या है जिसमें भार अंतराल की लंबाई के बराबर होता है।
इसे डायनेमिक प्रोग्रामिंग का उपयोग करके हल किया जा सकता है। अंतरालों को प्रारंभ समय के अनुसार क्रमबद्ध करने दें।
फिर परिभाषित करें DP[I_j] = अंतराल का अधिकतम भारित सेट जैसे कि I_j चुना जाता है और केवल I_j से पहले के अंतराल पर विचार किया जाता है। इसका अर्थ है कि I_j के साथ प्रतिच्छेद करने वाले अंतरालों पर विचार नहीं किया जाएगा।
DP[I_j] = MAX(DP[I_r]) + Wt(I_j)
जहां I_r, I_j से पहले आने वाले अंतराल हैं।
समय जटिलता O(n^2) है जहां n अंतरालों की संख्या है।
संबंधित सवाल
नए सवाल
algorithm
एक एल्गोरिथ्म अच्छी तरह से परिभाषित चरणों का एक क्रम है जो एक समस्या के सार समाधान को परिभाषित करता है। जब आपकी समस्या एल्गोरिथम डिज़ाइन से संबंधित हो तो इस टैग का उपयोग करें।