मैं एल्गोरिदम खोजता हूं, जो मुझे एक समस्या की प्राप्ति में मदद करेगा! समस्या इस प्रकार है:

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

उदाहरण के लिए, एक इनपुट सूची के लिए

[(-1, 3), (2, 4), (0, 5), (-4, -1)]

वांछित आउटपुट है

[(0, 5), (-4, -1)]

लंबाई के योग के साथ (5 - 0) + ((-1) - (-4)) = 5 + 3 = 8

1
deniska369 18 अक्टूबर 2016, 14:26
1
'अधिकतम मूल्य' क्या है? आप किस मूल्य को अधिकतम करना चाहते हैं?
 – 
CiaPan
18 अक्टूबर 2016, 14:29
1
कितनी राशि? उदाहरण में 'योग' क्या है [(1,2), (4,6)]: क्या यह 3=[2-1]+[6-4] या 5=[6-1]...?
 – 
CiaPan
18 अक्टूबर 2016, 14:37
1
श्रेणियों की कुल लंबाई, संक्षेप में।
 – 
Karoly Horvath
18 अक्टूबर 2016, 14:48
1
इस मामले में यह काफी अस्पष्ट था, क्योंकि अंतराल का एक सामान्य अंत होता है, इसलिए अंतराल की लंबाई का योग उनकी कुल अवधि के बराबर होता है। इसलिए मैंने एक और उदाहरण के बारे में पूछा, एक छेद के साथ।
 – 
CiaPan
18 अक्टूबर 2016, 14:53
1
ठीक है, तो यदि आपका मतलब [(1,2), (4,6)] -> [2-1]+[6-4] = 3 है, तो आपका उदाहरण परिणाम क्यों है [(-1, 3), ( -4, -1)] 7 के योग के साथ [(0, 5), (-4, -1)] के योग के साथ 8...?!
 – 
CiaPan
18 अक्टूबर 2016, 14:56

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 अंतरालों की संख्या है।

2
Abhishek Bansal 18 अक्टूबर 2016, 17:05