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

परिचय

टिप्पणियों

क्लेश समस्या

0-1 नैकपैक

द नैकपैक समस्या एक समस्या है, जब वस्तुओं का एक सेट दिया जाता है, प्रत्येक में एक वजन, एक मूल्य और ठीक 1 प्रति है , जो एक संग्रह में शामिल करने के लिए किस आइटम (ओं) को निर्धारित करता है ताकि कुल वजन दिए गए से कम या बराबर हो। सीमा और कुल मूल्य जितना संभव हो उतना बड़ा है।

C ++ उदाहरण:

कार्यान्वयन :

int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
    int dp[C+1];                               
    for (int i = 1; i <= C; ++i){
        dp[i] = -100000000;                   
    }
    dp[0] = 0;
    for (int i = 0; i < N; ++i){
        for (int j = C; j >= weight[i]; --j){
            dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
    return dp[C];
}

परीक्षण :

3 5
5 2
2 1
3 2

आउटपुट :

3

इसका मतलब है कि अधिकतम मूल्य 3 प्राप्त किया जा सकता है, जिसे चुनकर (2,1) और (3,2) प्राप्त किया जाता है।

अनबाउंड नैकपैक

अनबाउंड नैकपैक समस्या एक ऐसी समस्या है, जो वस्तुओं के एक सेट को दी जाती है, जिनमें से प्रत्येक का वजन, एक मूल्य और अनंत प्रतियां हैं , प्रत्येक आइटम की संख्या को एक संग्रह में शामिल करने के लिए निर्धारित करते हैं ताकि कुल वजन किसी सीमा से कम या बराबर हो और कुल मूल्य जितना संभव हो उतना बड़ा है।

पायथन (2.7.11) उदाहरण:

कार्यान्वयन :

def unbounded_knapsack(w, v, c): # weight, value and capactiy
    m = [0]
    for r in range(1, c+1):
        val = m[r-1]
        for i, wi in enumerate(w):
            if wi > r:
                continue
            val = max(val, v[i] + m[r-wi])
        m.append(val)
    return m[c] # return the maximum value can be achieved

उस कार्यान्वयन की जटिलता O(nC) , जो n वस्तुओं की संख्या है।

परीक्षण :

w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]

print unbounded_knapsack(w, v, 13)

आउटपुट :

20

इसका मतलब है कि अधिकतम मूल्य 20 प्राप्त किया जा सकता है, जिसे चुनकर (5, 8), (5, 8) और (3, 4) प्राप्त किया जाता है।

भारित नौकरी निर्धारण एल्गोरिथम

भारित नौकरी निर्धारण एल्गोरिथम को भारित गतिविधि चयन एल्गोरिदम के रूप में भी चिह्नित किया जा सकता है।

समस्या यह है कि, कुछ नौकरियों को उनके प्रारंभ समय और समाप्ति समय के साथ दिया जाता है, और जब आप नौकरी समाप्त करते हैं तो एक लाभ, आप अधिकतम दो लाभ क्या दे सकते हैं जो समानांतर रूप से निष्पादित नहीं किए जा सकते हैं?

यह एक लालची एल्गोरिथ्म का उपयोग करते हुए गतिविधि चयन जैसा दिखता है, लेकिन इसमें एक अतिरिक्त ट्विस्ट है। अर्थात्, समाप्त नौकरियों की संख्या को अधिकतम करने के बजाय, हम अधिकतम लाभ कमाने पर ध्यान केंद्रित करते हैं। प्रदर्शन की संख्या यहाँ काम नहीं करती है।

आइए एक उदाहरण देखें:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    A    |    B    |    C    |    D    |    E    |    F    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (2,5)  |  (6,7)  |  (7,9)  |  (1,3)  |  (5,8)  |  (4,6)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    6    |    4    |    2    |    5    |    11   |    5    |
+-------------------------+---------+---------+---------+---------+---------+---------+

नौकरियों को एक नाम, उनकी शुरुआत और समय और लाभ के साथ निरूपित किया जाता है। कुछ पुनरावृत्तियों के बाद, हम यह पता लगा सकते हैं कि क्या हम जॉब-ए और जॉब-ई का प्रदर्शन करते हैं, हम 17 का अधिकतम लाभ प्राप्त कर सकते हैं। अब एक एल्गोरिथ्म का उपयोग करके यह कैसे पता करें?

पहली बात जो हम करते हैं वह गैर-घटते क्रम में उनके परिष्करण समय के अनुसार नौकरियों को क्रमबद्ध करना है। हम ऐसा क्यों करते हैं? ऐसा इसलिए है क्योंकि यदि हम एक ऐसी नौकरी का चयन करते हैं जिसे समाप्त करने में कम समय लगता है, तो हम अन्य नौकरियों को चुनने के लिए सबसे अधिक समय छोड़ देते हैं। हमारे पास है:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

हमारे पास अतिरिक्त अस्थायी सरणी Acc_Prof का आकार n (यहाँ, n नौकरियों की कुल संख्या को दर्शाता है)। इसमें नौकरियों के प्रदर्शन का अधिकतम संचित लाभ होगा। नहीं मिलता है? रुको और देखो। हम प्रत्येक कार्य के लाभ के साथ सरणी के मान को आरंभीकृत करेंगे। इसका मतलब है, Acc_Prof [i] पहले i-th नौकरी करने के लाभ को धारण करेगा।

+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

अब आइए i के साथ स्थिति 2 को निरूपित करें, और स्थिति 1 को j के साथ निरूपित किया जाएगा। हमारी रणनीति i-1 1 से पुनरावृति j करने होंगे और प्रत्येक यात्रा के बाद, हम, 1 से मैं भी वृद्धि होगी जब तक मैं n + 1 हो जाता है।

                               j        i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

यदि जॉब [i] और जॉब [j] ओवरलैप होता है, तो हम जांचते हैं, कि अगर जॉब का पूरा समय [j] जॉब [i] के स्टार्ट टाइम से ज्यादा है, तो ये दोनों जॉब्स एक साथ नहीं किए जा सकते। हालाँकि, यदि वे ओवरलैप नहीं करते हैं, तो हम जाँचेंगे कि Acc_Prof [j] + लाभ [i]> Acc_Prof [i] । अगर ऐसा है, तो हम Acc_Prof [i] = Acc_Prof [j] + Profit [i] को अपडेट करेंगे। अर्थात्:

if Job[j].finish_time <= Job[i].start_time
    if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
        Acc_Prof[i] = Acc_Prof[j] + Profit[i]
    endif
endif

यहाँ Acc_Prof [j] + Profit [i] इन दो नौकरियों को करने के संचित लाभ का प्रतिनिधित्व करता है। आइए इसे हमारे उदाहरण के लिए देखें:

यहाँ जॉब [j] जॉब के साथ ओवरलैप होता है [i] । इसलिए इन्हें एक साथ नहीं किया जा सकता है। चूँकि हमारा j i-1 के बराबर है, हम i से i + 1 का मान बढ़ाते हैं जो कि 3 है । और हम j = 1 बनाते हैं।

                               j                   i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

अब नौकरी [j] और नौकरी [i] ओवरलैप नहीं है। इन दोनों नौकरियों को उठाकर हम जितना लाभ कमा सकते हैं, वह है: Acc_Prof [j] + Profit [i] = 5 + 5 = 10 जो Acc_Prof [i] से अधिक है। इसलिए हम Acc_Prof [i] = 10 को अपडेट करते हैं । हम यह भी 1. द्वारा वेतन वृद्धि जे हम मिलता है,

                                         j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

यहाँ, नौकरी [j] नौकरी [i] के साथ ओवरलैप होती है और j भी i-1 के बराबर है। इसलिए हम i को 1 से बढ़ाते हैं, और j = 1 बनाते हैं। हमें मिला,

                               j                             i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

अब, नौकरी [j] और नौकरी [i] ओवरलैप नहीं करते हैं, हमें संचित लाभ 5 + 4 = 9 मिलता है , जो Acc_Prof [i] से अधिक है। हम Acc_Prof [i] = 9 और increment j को 1 से अपडेट करते हैं ।

                                         j                   i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    9    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

फिर से नौकरी [j] और नौकरी [i] ओवरलैप नहीं है। संचित लाभ है: 6 + 4 = 10 , जो Acc_Prof [i] से अधिक है। हम फिर से Acc_Prof [i] = 10 को अपडेट करते हैं । 1. द्वारा हम वेतन वृद्धि जे हम पाते हैं:

                                                   j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    10   |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

यदि हम इस प्रक्रिया को जारी रखते हैं, तो i का उपयोग करके पूरी तालिका के माध्यम से पुनरावृत्ति करने के बाद, हमारी तालिका अंततः दिखाई देगी:

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    14   |    17   |    8    |
+-------------------------+---------+---------+---------+---------+---------+---------+

_{* दस्तावेज़ को छोटा बनाने के लिए कुछ चरणों को छोड़ दिया गया है।}

यदि हम सरणी Acc_Prof के माध्यम से पुनरावृति करते हैं , तो हम अधिकतम लाभ 17 होने का पता लगा सकते हैं! छद्म कोड:

Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
    for j -> 1 to i-1
        if Job[j].finish_time <= Job[i].start_time
            if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
                Acc_Prof[i] = Acc_Prof[j] + Profit[i]
            endif
        endif
    endfor
endfor

maxProfit = 0
for i -> 1 to n
    if maxProfit < Acc_Prof[i]
        maxProfit = Acc_Prof[i]
return maxProfit

Acc_Prof सरणी को पॉप्युलेट करने की जटिलता O (n ² ) है। सरणी ट्रैवर्सल O (n) लेता है। तो इस एल्गोरिथ्म की कुल जटिलता O (n ² ) है।

अब, यदि हम यह जानना चाहते हैं कि अधिकतम लाभ प्राप्त करने के लिए कौन से काम किए गए थे, तो हमें सरणी को उल्टे क्रम में पार करने की आवश्यकता है और यदि Acc_Prof मैक्सप्रोफिट से मेल खाता है, तो हम एक स्टैक में नौकरी के नाम को आगे बढ़ाएंगे और लाभ का लाभ देंगे। अधिकतम नौकरी से वह नौकरी। हम ऐसा तब तक करेंगे जब तक हमारा मैक्सप्रोफिट> 0 या हम Acc_Prof सरणी के शुरुआती बिंदु तक नहीं पहुंच जाते। छद्म कोड की तरह दिखेगा:

Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
    if maxProfit is equal to Acc_Prof[i]
        S.push(Job[i].name
        maxProfit = maxProfit - Job[i].profit
    endif
endfor

इस प्रक्रिया की जटिलता है: O (n) ।

एक बात याद रखें, यदि कई कार्य शेड्यूल हैं जो हमें अधिकतम लाभ दे सकते हैं, तो हम इस प्रक्रिया के माध्यम से केवल एक नौकरी अनुसूची पा सकते हैं।

दूरी संपादित करें

समस्या कथन यह है कि यदि हमें दो स्ट्रिंग str1 और str2 दिए जाते हैं तो str1 पर कितने न्यूनतम संचालन किए जा सकते हैं कि यह str2 में परिवर्तित हो जाता है।

जावा में कार्यान्वयन

public class EditDistance {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    String str1 = "march";
    String str2 = "cart";
    
    EditDistance ed = new EditDistance();
    System.out.println(ed.getMinConversions(str1, str2));
}

public int getMinConversions(String str1, String str2){
    int dp[][] = new int[str1.length()+1][str2.length()+1];
    for(int i=0;i<=str1.length();i++){
        for(int j=0;j<=str2.length();j++){
            if(i==0)
                dp[i][j] = j;
            else if(j==0)
                dp[i][j] = i;
            else if(str1.charAt(i-1) == str2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else{
                dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
            }
        }
    }
    return dp[str1.length()][str2.length()];
}

}

उत्पादन

3

सबसे लंबा सामान्य परिणाम

यदि हम दो तारों के साथ दिए गए हैं, तो हमें उन दोनों में मौजूद सबसे लंबे सामान्य उप-अनुक्रम को खोजना होगा।

उदाहरण

इनपुट अनुक्रम "ABCDGH" और "AEDFHR" के लिए LCS लंबाई 3 का "ADH" है।

इनपुट अनुक्रम "AGGTAB" और "GXTXAYB" के लिए LCS लंबाई 4 का "GTAB" है।

जावा में कार्यान्वयन

public class LCS {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str1 = "AGGTAB";
        String str2 = "GXTXAYB";
        LCS obj = new LCS();
        System.out.println(obj.lcs(str1, str2, str1.length(), str2.length()));
        System.out.println(obj.lcs2(str1, str2));
    }
    
    //Recursive function
    public int lcs(String str1, String str2, int m, int n){
        if(m==0 || n==0)
            return 0;
        if(str1.charAt(m-1) == str2.charAt(n-1))
            return 1 + lcs(str1, str2, m-1, n-1);
        else
            return Math.max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
    }
    
    //Iterative function
    public int lcs2(String str1, String str2){
        int lcs[][] = new int[str1.length()+1][str2.length()+1];
        
        for(int i=0;i<=str1.length();i++){
            for(int j=0;j<=str2.length();j++){
                if(i==0 || j== 0){
                    lcs[i][j] = 0;
                }
                else if(str1.charAt(i-1) == str2.charAt(j-1)){
                    lcs[i][j] = 1 + lcs[i-1][j-1]; 
                }else{
                    lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
                }
            }
        }
        
        return lcs[str1.length()][str2.length()];
    }

}

उत्पादन

4

फाइबोनैचि संख्या

डायनेमिक प्रोग्रामिंग का उपयोग करके nth फाइबोनैचि संख्या को प्रिंट करने के लिए नीचे का दृष्टिकोण।

पुनरावर्ती वृक्ष

                         fib(5)   
                     /             \     
               fib(4)                fib(3)   
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \  
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

ओवरलैपिंग उप-समस्याओं

यहाँ फ़ाइब (0), फ़ाइब (1) और फ़ाइबर (3) ओवरलैपिंग उप-समस्याएं हैं। फ़िब (0) 3 बार दोहराया जा रहा है, फ़ाइबर (1) 5 बार दोहराया जा रहा है और फ़ाइबर (3) बार-बार 2 हो रहा है बार।

कार्यान्वयन

public int fib(int n){
        int f[] = new int[n+1];
        f[0]=0;f[1]=1;
        for(int i=2;i<=n;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f[n];
    }

समय जटिलता

पर)

सबसे लंबा सामान्य पदार्थ

2 स्ट्रिंग str1 और str2 को देखते हुए हमें उनके बीच सबसे लंबे कॉमन सबरिंग की लंबाई का पता लगाना होगा।

उदाहरण

इनपुट: X = "abcdxyz", y = "xyzabcd" आउटपुट: 4

सबसे लंबा सामान्य विकल्प "abcd" है और लंबाई 4 का है।

इनपुट: X = "zxabcdezy", y = "yzabcdezx" आउटपुट: 6

सबसे लम्बा सामान्य विकल्प है "एबडेज़" और लंबाई 6 है।

जावा में कार्यान्वयन

public int getLongestCommonSubstring(String str1,String str2){
        int arr[][] = new int[str2.length()+1][str1.length()+1];
        int max = Integer.MIN_VALUE;
        for(int i=1;i<=str2.length();i++){
            for(int j=1;j<=str1.length();j++){
                if(str1.charAt(j-1) == str2.charAt(i-1)){
                    arr[i][j] = arr[i-1][j-1]+1;
                    if(arr[i][j]>max)
                        max = arr[i][j];
                }
                else
                    arr[i][j] = 0;
            }
        }
        return max;
    }

समय जटिलता

हे (एम * एन)