कॉइन चेंज समस्या

छुट्टा लौटाने वाला कैशियर पहले समाने वाला सबसे बड़ा सिक्का उठाता है, फिर अगला, और यूरो या डॉलर में इससे हमेशा सबसे कम सिक्के मिलते हैं। लेकिन सिक्कों को 1, 3 और 4 कर दें, तो यही आदत 6 को तीन सिक्कों से चुकाती है, जबकि दो काफ़ी होते। गतिशील प्रोग्रामिंग किन्हीं भी सिक्कों के लिए असली न्यूनतम खोज लेती है।

राशियों की एक पंक्ति, हर एक के साथ उसे बनाने वाले सबसे कम सिक्के, और उसके नीचे तीन अलग आकार के सिक्के
राशियों की एक पंक्ति, हर एक के साथ उसे बनाने वाले सबसे कम सिक्के, और उसके नीचे तीन अलग आकार के सिक्के

दो सवाल

कॉइन चेंज समस्या के दो रूप हैं। पहला पूछता है कि किसी सटीक राशि को बनाने के लिए सबसे कम कितने सिक्के चाहिए; इसे छुट्टा देने की समस्या भी कहते हैं। दूसरा पूछता है कि सिक्कों के कितने अलग-अलग संयोजन उसे बनाते हैं। दोनों में हर तरह का सिक्का जितनी बार चाहें इस्तेमाल किया जा सकता है, और दोनों को हर राशि का जवाब छोटी राशियों के जवाबों से बनाकर हल किया जाता है।

सबसे कम सिक्के, चरण-दर-चरण

0 से लक्ष्य तक की राशियों के लिए खानों की एक पंक्ति बनाएँ। राशि 0 के लिए 0 सिक्के लगते हैं; बाकी हर राशि अनंत से शुरू होती है। राशियों पर क्रम से चलें, और हर राशि के लिए हर समाने वाला सिक्का c आज़माएँ: राशि घटा c वाले खाने में एक सिक्का जोड़ने से एक उम्मीदवार मिलता है। सबसे छोटा रखें। हर खाना सिर्फ़ अपने बाईं ओर के खानों पर निर्भर है, जो पहले ही तय हो चुके हैं, इसलिए एक बार चलने में पूरी पंक्ति भर जाती है।

एक उदाहरण

सिक्के 1, 3 और 4 हों तो: राशि 1 के लिए 1 सिक्का, 2 के लिए 2, 3 के लिए 1 (एक 3) और 4 के लिए 1 लगता है। 5 के लिए 1 आज़माएँ (4 को 1 चाहिए, तो 2 सिक्के), 3 (2 को 2 चाहिए, तो 3 सिक्के) और 4 (1 को 1 चाहिए, तो 2 सिक्के): सबसे अच्छा 2 है। 6 के लिए 1 आज़माएँ (5 को 2 चाहिए, तो 3), 3 (3 को 1 चाहिए, तो 2) और 4 (2 को 2 चाहिए, तो 3): सबसे अच्छा 2 है, 3 + 3 से। ग्रीडी 4 + 1 + 1 देता।

तरीके गिनना

संयोजन गिनने के लिए, सिक्कों को एक-एक करके जोड़ें। सिर्फ़ पहले सिक्के से, हर राशि या तो एक तरीके से बनती है या बिल्कुल नहीं। जब कोई नया सिक्का c जुड़ता है, तो राशि a बनाने के तरीके होते हैं पुराने तरीके, यानी c के बिना, और साथ में a − c बनाने के वे तरीके जिनमें c फिर से इस्तेमाल किया जा सकता है, क्योंकि उनमें से हर एक में एक और c जोड़ने पर a बनाने का एक तरीका बन जाता है। सिक्के 1, 2 और 5 से 5 बनाने के 4 तरीके हैं: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 और 1 + 1 + 1 + 1 + 1।

ग्रीडी कब काफ़ी है

जिस सिक्का प्रणाली में ग्रीडी हमेशा सबसे कम सिक्के देता है, उसे कैनोनिकल कहा जाता है। ज़्यादातर आधुनिक मुद्राएँ इसी तरह बनाई गई हैं, और 1994 में डेविड पियर्सन ने एक जाँच बताई जो किसी सिक्का प्रणाली को इतने चरणों में परखती है जो सिक्कों की संख्या के साथ सिर्फ़ बहुपद रूप में बढ़ते हैं। पुराने ब्रिटिश सिक्के कैनोनिकल नहीं थे: ग्रीडी 48 पेंस को एक हाफ़ क्राउन, एक शिलिंग और एक सिक्सपेंस से चुकाता है, जबकि दो फ़्लोरिन काफ़ी होते।

ख़ुद आज़माएँ

ऐप खोलें, “टेबल” दृश्य पर जाएँ और “आगे” दबाएँ। “सबसे कम सिक्के” मोड में नारंगी खाना वह राशि है जिसकी गणना हो रही है, और नीला खाना वह छोटी राशि है जो सिक्के के बाद बचती है; नीचे वाली पंक्ति आख़िरी सिक्का रखती है, और अंत में सिक्के इसी के साथ-साथ पीछे की ओर पढ़े जाते हैं। “तरीकों की संख्या” पर जाएँ और देखें कि हर सिक्का जुड़ने पर गिनतियाँ पंक्ति-दर-पंक्ति कैसे बढ़ती हैं।

अक्सर पूछे जाने वाले प्रश्न

क्या कॉइन चेंज समस्या एक नैपसैक समस्या है?

उसकी करीबी रिश्तेदार है। सबसे कम सिक्कों वाला रूप एक अनबाउंडेड नैपसैक समस्या है, जिसमें हर सिक्का एक वस्तु है जिसका भार उसका अंकित मूल्य है, थैले को बिल्कुल पूरा भरना होता है, और लक्ष्य सबसे कम वस्तुएँ है।

समय जटिलता क्या है?

दोनों रूपों में, k तरह के सिक्कों और राशि A के लिए O(k·A)। सबसे कम सिक्कों की तालिका में A + 1 खाने होते हैं, और तरीकों की तालिका में (k + 1)·(A + 1), हालाँकि खानों को उसी जगह अपडेट किया जाए तो एक पंक्ति काफ़ी है।

सिक्कों को तय क्रम में क्यों गिनें?

अगर हर राशि हर सिक्का आज़माती, तो 1 + 2 और 2 + 1 दो तरीके गिने जाते। सिक्कों को एक-एक पंक्ति में जोड़ने का मतलब है कि कोई संयोजन हमेशा पहले आए सिक्कों से पहले बनता है, इसलिए हर एक ठीक एक बार गिना जाता है।

क्या तरीकों की संख्या के लिए सिक्के पीछे की ओर पढ़े जा सकते हैं?

एक अकेले जवाब के रूप में नहीं, क्योंकि तरीके बहुत सारे हैं। सबसे कम सिक्कों वाला रूप हर राशि का आख़िरी सिक्का रखता है, जो एक सबसे अच्छे संयोजन को फिर से बनाने के लिए काफ़ी है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

कॉइन चेंज आज़माएँ