सिक्कों की न्यूनतम संख्या जो किसी दिए गए मूल्य को बनाते हैं

सिक्का C(c1, c2, ……Cn) की एक सूची है और एक मान V भी दिया गया है। अब समस्या यह है कि मौका वी बनाने के लिए सिक्कों की न्यूनतम संख्या का उपयोग किया जाए।

नोट: मान लें कि सिक्कों की अनंत संख्या है C.

इस समस्या में, हम विभिन्न सिक्कों के एक सेट पर विचार करेंगे C{1, 2, 5, 10} दिए गए हैं, प्रत्येक प्रकार के सिक्कों की अनंत संख्या है। अनुरोधित मूल्य में परिवर्तन करने के लिए हम किसी भी प्रकार के सिक्कों की न्यूनतम संख्या लेने का प्रयास करेंगे। उदाहरण के तौर पर, मान 22 के लिए:हम न्यूनतम के रूप में {10, 10, 2}, 3 सिक्के चुनेंगे।

इनपुट और आउटपुट

एल्गोरिदम

minCoins(coinList, n, value)

इनपुट: विभिन्न सिक्कों की सूची, सिक्कों की संख्या, दिए गए मूल्य।

आउटपुट: दिए गए मूल्य प्राप्त करने के लिए सिक्कों की न्यूनतम संख्या।

शुरू करें यदि मान =0 है, तो वापसी 0 आकार मान + 1 के सिक्कों की सरणी को परिभाषित करें, ∞ सिक्कों के साथ भरें [0]:=0 के लिए i:=1 मान के लिए, j के लिए करें:=0 से n, यदि करें सिक्का सूची [जे] <=मैं, फिर अस्थायी सिक्के:=सिक्के [i-coinList [जे]] अगर tempCoins और (tempCoins + 1) <सिक्के [i], तो सिक्के [i]:=tempCoins + 1 किया वापसी सिक्के[मूल्य]अंत

उदाहरण

#शामिल करेंनेमस्पेस std का उपयोग करना;int minCoins(intcoinList[], int n, int value) { intcoins[value+1]; // मूल्य के लिए न्यूनतम सिक्के स्टोर करें i यदि (मान ==0) रिटर्न 0; // मान 0 के लिए, इसे 0 सिक्के के सिक्के [0] =0 की आवश्यकता है; के लिए (int i=1; i<=value; i++) सिक्के [i] =INT_MAX; // प्रारंभ में सभी मान अनंत हैं (int i=1; i<=value; i++) के लिए 0 मान को छोड़कर {// सभी मानों के लिए 1 से मान, के लिए न्यूनतम मान खोजें (int j=0; j> मूल्य; cout <<"न्यूनतम "< 
आउटपुट
 
मान दर्ज करें:48 न्यूनतम 7 सिक्कों की आवश्यकता है।