ন্যূনতম মুদ্রা পরিবর্তন সমস্যা

এখানে মুদ্রা C(c1, c2, ……Cn) এর একটি তালিকা দেওয়া আছে এবং একটি মান Vও দেওয়া আছে। এখন সমস্যা হল 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