एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

Coin change

💡
Coin change समस्या सबसे लोकप्रिय Dynamic Programming (डायनेमिक प्रोग्रामिंग) समस्याओं में से एक है। यह Greedy (ग्रीडी) और Dynamic Programming अप्रोच के बीच का अंतर बखूबी दर्शाती है और यह भी दिखाती है कि कैसे ग्रीडी अप्रोच पर भरोसा करके हम कभी-कभी सबऑप्टिमल (कमतर) रिज़ल्ट पर पहुँच जाते हैं, जबकि असली समाधान पूरी समस्या का समाधान निकालने से मिलता है।
मान लीजिए कि हमारे पास एक मुद्रा प्रणाली है, जिसमें n सिक्के हैं और प्रत्येक सिक्के का मान है (सभी मान धनात्मक)। हमारा उद्देश्य है कि हम किसी भी तरह से x के कुल योग को प्राप्त करें, और इसके लिए जितने कम से कम सिक्के लगाने पड़ें, उतने कम सिक्कों का इस्तेमाल करें।
उदाहरण के लिए, अगर सिक्कों के मान हों और हमें 11 प्राप्त करना हो, तो सबसे अच्छा तरीका होगा 1 + 5 + 5 ⇒ कुल 3 सिक्के।

इनपुट

इनपुट की पहली पंक्ति में दो पूर्णांक n (1 ≤ n ≤ 100) और x (1 ≤ x ≤ ) दिए गए होते हैं।
अगली पंक्ति में n स्पेस-सेपरेटेड पूर्णांक (1 ≤ ≤ ) होते हैं।

आउटपुट

कार्यक्रम को कम-से-कम सिक्कों की वह संख्या प्रिंट करनी चाहिए, जो x प्राप्त करने के लिए आवश्यक है। यदि x को बनाना संभव न हो, तो प्रोग्राम को -1 प्रिंट करना चाहिए।

उदाहरण

इनपुट
आउटपुट
3 11 1 5 7
3
3 12 1 5 7
2

व्याख्या

  1. 11 → 1 + 5 + 5
  1. 12 → 5 + 7
 

ट्यूटोरियल

ध्यान दें कि सबसे बड़े सिक्के को बार-बार लेकर आगे बढ़ने वाली ग्रीडी रणनीति हमेशा काम नहीं करती। पहला उदाहरण इसे साफ़ तौर पर दिखाता है। यदि हम 11 बनाने के लिए पहले सबसे बड़ा सिक्का ले लेते हैं (जो कि 7 है), तो हमें 11 - 7 = 4 और चाहिए। इसके लिए हमें 4 सिक्कों का इस्तेमाल करना होगा (चार बार 1), जिससे कुल 5 सिक्के लगेंगे। जबकि वास्तविक उत्तर केवल 3 है (5 + 5 + 1)।
आइए एक स्टेट (राज्य) d[i] रखें, जो यह बताएगा कि योग i को प्राप्त करने के लिए न्यूनतम सिक्कों की संख्या कितनी है। यदि हम सही तरह से d को इनिशियलाइज़ करें और फिर x तक सभी मानों को अपडेट करें, तो अंतिम उत्तर d[x] ही होगा (मतलब x प्राप्त करने के लिए न्यूनतम सिक्कों की संख्या)।
शुरुआत में हम d के सभी मानों को अनंत (∞) मान ले सकते हैं (यानि वह योग प्राप्त करना अभी संभव नहीं है), लेकिन d[0] को 0 रखें, क्योंकि 0 को प्राप्त करने के लिए हमें 0 सिक्के चाहिए:
c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] is 0 and d[1...x] inclusive is infinity
इसके बाद, हर संख्या 1...x के लिए हम यह पता करेंगे कि उसे बनाने के लिए कितने न्यूनतम सिक्के चाहिए। यदि हमारे पास कोई संख्या num है, तो हम सभी अलग-अलग सिक्कों की जाँच करके यह देखते हैं कि क्या हम num को num - $$c_i$$ से आगे बढ़कर बना सकते हैं। यदि ऐसा करने से हमारा जवाब बेहतर (कम) होता है, तो हम d[num] को अपडेट कर देंगे। इसलिए, प्रत्येक num के लिए 1...x तक हम सारे सिक्के आज़माते हैं:
for num in range(1, x + 1):       # 1 से x तक सभी संख्याओं पर जाएँ
    for ci in c:                  # सभी सिक्कों से d[num] को बेहतर करने की कोशिश करें
        if num - ci >= 0:         # अगर num को ci सिक्के की मदद से बनाया जा सकता है
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])
d[num] = min(d[num], d[num - ci] + 1) ही इस समस्या के हल की मुख्य धारणा है। हर इटरशन में, हम यह देखने की कोशिश करते हैं कि क्या num - $$c_i$$ की स्थिति से होते हुए num तक पहुँचना कम सिक्कों में मुमकिन है, और अगर ऐसा है, तो हम एक सिक्का और जोड़कर वह संख्या बना लेते हैं।
जब 1...x की सभी संख्याएँ और सभी सिक्के प्रोसेस हो जाएँगे, तो अंत में d[x] ही हमारा उत्तर होगा।
अब इस एल्गोरिद्म को दिए गए इनपुट पर चलाकर देखें:
c = [1, 5, 7] और x = 11
  1. d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
  1. num = 1 (1 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 2 (2 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 3 (3 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒ d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 4 (4 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[4] = d[3] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ num - ci < 0 ci = 7 ⇒ num - ci < 0
  1. num = 5 (5 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[5] = d[4] + 1 = 5 ⇒ d = [0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ d[5] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞] ci = 7 ⇒ num - ci < 0
  1. num = 6 (6 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ num - ci < 0
  1. num = 7 (7 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
  1. num = 8 (8 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ does not update
  1. num = 9 (9 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞] ci = 5 ⇒ does not update ci = 7 ⇒ does not update
  1. num = 10 (10 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[10] = d[9] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, ∞] ci = 5 ⇒ d[10] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, ∞] ci = 7 ⇒ does not update
  1. num = 11 (11 का योग पाने के लिए न्यूनतम सिक्कों की संख्या सुधारने की कोशिश) ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3] ci = 5 ⇒ does not update ci = 7 ⇒ does not update
  1. print(d[11]) ⇒ 3 प्रिंट करेगा
 

Constraints

Time limit: 2.5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue