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

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

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

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

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

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

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

Input:
A value, say 47
Output:
Enter value: 47
Coins are: 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 thecoin 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<int> 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<int>::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