न्यूनतम सिक्का परिवर्तन समस्या

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

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

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

उदाहरण के लिए, मान 22 के लिए - हम {10, 10, 2} चुनेंगे, न्यूनतम 3 सिक्कों के रूप में।

इस एल्गोरिदम की समय जटिलता O(V) है, जहां V मान है।

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

इनपुट: एक मान, मान लें 47 आउटपुट: मान दर्ज करें: 47 सिक्के हैं: 10, 10, 10, 10, 5, 2

एल्गोरिदम

findMinCoin(value)

इनपुट - परिवर्तन करने के लिए मान

आउटपुट - सिक्कों का सेट

Begin 
  coins set with value {1, 2, 5, 10} 
  for all coins i as higher value to lower value do 
    while value >= coins[i] do 
      value := value – coins[i] 
      add coins[i], in the coin list 
    done 
  done 
  print all entries in the coin list. 
End

उदाहरण

#include<iostream> #include<list> #define COINS 4 using namespace std; float coins[COINS] = {1, 2, 5, 10}; void findMinCoin(int cost) { list coinList; for(int i = COINS-1; i>=0; i--) { while(cost >= coins[i]) { cost -= coins[i]; coinList.push_back(coins[i]); //add coin in the list } } list::iterator it; for(it = coinList.begin(); it != coinList.end(); it++) { cout << *it << ", "; } } main() { int val; cout << "Enter value: "; cin >> val; cout << "Coins are: "; findMinCoin(val); cout << endl; }

आउटपुट

Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2