dynamic-programming
सिक्का बदलने की समस्या

कुल प्राप्त करने के तरीकों की संख्या

विभिन्न संप्रदायों और कुल के सिक्कों को देखते हुए, कुल प्राप्त करने के लिए हम इन सिक्कों को कितने तरीकों से जोड़ सकते हैं? मान लें कि हमारे पास coins = {1, 2, 3} और total = 5 , हम कुल 5 तरीकों से प्राप्त कर सकते हैं:

• १ १ १ १ १ १
• 1 1 1 2
• १ १ ३
• १ २ २
• २ ३

समस्या समस्या से निकटता से जुड़ी है। फर्क सिर्फ इतना है कि हमारे पास सिक्कों की असीमित आपूर्ति है। हम इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग करने जा रहे हैं।

हम एक 2 डी सरणी डीपी [एन] [कुल + 1] का उपयोग करेंगे जहां एन हमारे पास सिक्कों के विभिन्न मूल्यवर्गों की संख्या है। हमारे उदाहरण के लिए, हमें dp [3] [6] की आवश्यकता होगी। यहाँ dp [i] [j] उन तरीकों की संख्या को निरूपित करेगा जिनसे हम j प्राप्त कर सकते हैं यदि हमारे पास सिक्कों [0] से लेकर सिक्कों [i] तक के सिक्के हैं । उदाहरण के लिए dp [1] [2] अगर हमारे पास कितने सिक्के हैं [०] और सिक्के [१] , तो हम २ बना सकते हैं। चलो शुरू करें:

Dp [0] [0] के लिए , हम खुद से पूछ रहे हैं कि क्या हमारे पास सिक्के का केवल 1 संप्रदाय था, यानी सिक्के [0] = 1 , कितने तरीकों से हम 0 प्राप्त कर सकते हैं? जवाब 1 तरीका है, जो कि अगर हम किसी भी सिक्के को नहीं लेते हैं। चल रहा है, dp [0] [1] प्रतिनिधित्व करेगा यदि हमारे पास केवल सिक्के थे [0] , कितने तरीकों से हम १ प्राप्त कर सकते हैं? उत्तर फिर से 1 है । उसी तरह, dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] 1 होगा। हमारे सरणी की तरह दिखेगा:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

Dp [1] [0] के लिए , हम अपने आप से पूछ रहे हैं कि क्या हमारे पास 2 मूल्यवर्ग के सिक्के थे, यानी अगर हमारे पास सिक्के थे [0] = 1 और सिक्के [1] = 2 , तो हम कितने तरीकों से 0 बना सकते हैं? उत्तर 1 है , जो बिना सिक्के के है। Dp [1] [1] के लिए , क्योंकि सिक्के [1] = २ हमारे वर्तमान कुल से अधिक है, २ कुल प्राप्त करने में योगदान नहीं करेगा। इसलिए हम 2 को छोड़ देंगे और सिक्कों की संख्या की गणना करेंगे, जिससे हम सिक्कों का उपयोग कर सकते हैं [0] । लेकिन यह मान पहले से ही dp [0] [1] में संग्रहीत है! तो हम ऊपर से मान लेंगे। हमारा पहला सूत्र:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

Dp [1] [2] के लिए , कितने तरीकों से हम २ प्राप्त कर सकते हैं, अगर हमारे पास १ और २ के सिक्के हैं? हम 1 के मूल्यवर्ग के सिक्कों का उपयोग करके 2 बना सकते हैं, जिसे dp [0] [2] द्वारा दर्शाया गया है, फिर से हम 2 का 1 मूल्यवर्ग ले सकते हैं जो dp [1] [2-सिक्कों] [i] में संग्रहीत है, जहाँ मैं = 1 । क्यों? यदि हम अगले उदाहरण को देखें तो यह स्पष्ट होगा। Dp [1] [3] के लिए , कितने तरीकों से हम ३ प्राप्त कर सकते हैं, अगर हमारे पास १ और २ के सिक्के हैं? हम 1 रास्ता है, जो डी पी [0] [3] में संग्रहीत किया जाता में मज़हब 1 की 3 सिक्के का उपयोग कर बना सकते हैं। अब अगर हम 2 का 1 मूल्यवर्ग लेते हैं, तो हमें कुल प्राप्त करने के लिए 3 - 2 = 1 की आवश्यकता होगी। मूल्यवर्ग 1 और 2 के सिक्कों का उपयोग करके 1 प्राप्त करने के तरीकों की संख्या dp [1] [1] में संग्रहीत की जाती है, जिसे dp [i] [j-coin [i] , जहाँ i = 1 लिखा जाता है। यही कारण है कि हमने पिछले मूल्य को इस तरह से लिखा है। हमारा दूसरा और अंतिम सूत्र होगा:

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

पूरे dp सरणी को भरने के लिए यह दो आवश्यक सूत्र हैं। भरने के बाद सरणी इस तरह दिखाई देगी:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [५] में हमारा आवश्यक उत्तर होगा। एल्गोरिथ्म:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

इस एल्गोरिथ्म की समय जटिलता O(n * total) , जहां n हमारे पास सिक्कों के मूल्यवर्ग की संख्या है।

कुल पाने के लिए सिक्के की न्यूनतम संख्या

विभिन्न संप्रदायों और कुल के सिक्कों को देखते हुए, यदि हम न्यूनतम संख्या में सिक्कों का उपयोग करते हैं, तो हमें कुल कितने सिक्के मिलाने होंगे? मान लें कि हमारे पास coins = {1, 5, 6, 8} और total = 11 , हम 2 सिक्कों का उपयोग करके कुल प्राप्त कर सकते हैं जो {5, 6} । यह वास्तव में 11 पाने के लिए आवश्यक सिक्कों की न्यूनतम संख्या है। हम यह भी मानेंगे कि सिक्कों की असीमित आपूर्ति है। हम इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग करने जा रहे हैं।

हम एक 2 डी सरणी डीपी [एन] [कुल + 1] का उपयोग करेंगे जहां एन हमारे पास सिक्कों के विभिन्न मूल्यवर्गों की संख्या है। हमारे उदाहरण के लिए, हमें dp [4] [12] की आवश्यकता होगी। यहाँ डीपी [मैं] [जे] अगर हम सिक्के [0] ऊपर सिक्के करने के लिए [i] से सिक्के था j प्राप्त करने के लिए आवश्यक सिक्कों की न्यूनतम संख्या को निरूपित होगा। उदाहरण के लिए dp [1] [2] अगर हमारे पास सिक्के हैं [०] और सिक्के [१] , सिक्कों की न्यूनतम संख्या क्या है जिसका उपयोग हम २ बनाने के लिए कर सकते हैं। चलो शुरू करें:

सबसे पहले, 0 वें कॉलम के लिए, किसी भी सिक्के को नहीं ले कर 0 बना सकते हैं। इसलिए सभी 0 के मूल्यों वें स्तंभ 0 हो जाएगा। Dp [0] [1] के लिए , हम खुद से पूछ रहे हैं कि क्या हमारे पास सिक्के का केवल 1 संप्रदाय था, यानी सिक्के [0] = 1 , सिक्कों की न्यूनतम संख्या 1 पाने के लिए क्या आवश्यक है? उत्तर 1 है । Dp [0] [2] के लिए , यदि हमारे पास केवल 1 था, तो 2 पाने के लिए आवश्यक सिक्कों की न्यूनतम संख्या क्या है। उत्तर 2 है । इसी प्रकार dp [0] [३] = ३ , dp [०] [४] = ४ और इसी तरह। यहाँ एक बात का उल्लेख है, अगर हमारे पास 1 मूल्य का सिक्का नहीं था, तो कुछ ऐसे मामले हो सकते हैं, जहाँ कुल 1 सिक्के का उपयोग करके प्राप्त नहीं किया जा सकता है। सादगी के लिए हम अपने उदाहरण में 1 लेते हैं। पहली पुनरावृत्ति के बाद हमारी डीपी सरणी दिखेगी :

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Dp [1] [1] के लिए आगे बढ़ते हुए, हम खुद से पूछ रहे हैं कि क्या हमारे पास सिक्के थे [0] = 1 और सिक्के [1] = 5 , सिक्कों की न्यूनतम संख्या 1 पाने के लिए क्या आवश्यक है? चूंकि सिक्के [1] हमारे वर्तमान कुल से अधिक हैं, इसलिए यह हमारी गणना को प्रभावित नहीं करेगा। हमें सिक्कों को बाहर करना होगा [5] और सिक्कों का उपयोग करके 1 प्राप्त करना है [0] । यह मान dp [0] [1] में संग्रहित है। इसलिए हम ऊपर से मान लेते हैं। हमारा पहला सूत्र है:

if coins[i] > j
    dp[i][j] := dp[i-1][j]

जब तक हमारे कुल डीपी में 5 यह स्थिति सही हो जाएगा [1] [5], उस मामले के लिए, हम 5 को दो तरह से कर सकते हैं:

• हम सिक्कों के 5 मूल्यवर्ग लेते हैं [0] , जो dp [0] [5] (ऊपर से) पर संग्रहीत है।
• हम सिक्कों का 1 मूल्यवर्ग लेते हैं [1] और ( 5 - 5 ) = 0 सिक्कों का मूल्यवर्ग [0] ।

हम इन दोनों में से न्यूनतम चुनेंगे। तो dp [1] [५] = मिनट ( dp [०] [५] , १ + डीपी [१] [०] ) = १ । हमने सिक्कों के 0 संप्रदायों का उल्लेख क्यों किया [0] यहां हमारी अगली स्थिति स्पष्ट होगी।

Dp [1] [६] के लिए , हम दो तरीकों से ६ बना सकते हैं:

• हम सिक्कों के 6 मूल्यवर्ग लेते हैं [0] , जो शीर्ष पर संग्रहीत है।
• हम 5 का 1 मूल्यवर्ग ले सकते हैं, हमें कुल प्राप्त करने के लिए 6 - 5 = 1 की आवश्यकता होगी। मूल्यवर्ग 1 और 5 के सिक्कों का उपयोग करके 1 प्राप्त करने के तरीकों की न्यूनतम संख्या डीपी [1] [1] में संग्रहीत की जाती है, जिसे डीपी [i] [जे-सिक्कों [i] के रूप में लिखा जा सकता है, जहां मैं = 1 । यही कारण है कि हमने उस फैशन में पिछले मूल्य को लिखा था।

हम इन दो तरीकों में से न्यूनतम लेंगे। तो हमारा दूसरा सूत्र होगा:

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

इन दो सूत्रों का उपयोग करके हम पूरी तालिका भर सकते हैं। हमारा अंतिम परिणाम होगा:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

हमारा अपेक्षित परिणाम dp [3] [11] पर संग्रहीत किया जाएगा। प्रक्रिया होगी:

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

इस एल्गोरिथ्म की रनटाइम जटिलता है: O (n * कुल) जहां n सिक्कों के संप्रदायों की संख्या है।

सिक्कों को मुद्रित करने के लिए, हमें जांचने की आवश्यकता है:

• यदि मूल्य ऊपर से आया है, तो वर्तमान सिक्का शामिल नहीं है।
• यदि मान बाईं ओर से आया है, तो वर्तमान सिक्का शामिल है।

एल्गोरिदम होगा:

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

हमारे उदाहरण के लिए, दिशा होगी:

मान 6 , 5 होंगे ।