একটি প্রদত্ত মান তৈরি করে এমন কয়েনের ন্যূনতম সংখ্যা

এখানে মুদ্রা C(c1, c2, ……Cn) এর একটি তালিকা দেওয়া আছে এবং একটি মান Vও দেওয়া আছে। এখন সমস্যা হল V.

দ্রষ্টব্য: অনুমান করুন সি এর অসীম সংখ্যক মুদ্রা রয়েছে।

এই সমস্যায়, আমরা বিবেচনা করব বিভিন্ন কয়েনের একটি সেট C{1, 2, 5, 10} দেওয়া হয়েছে, প্রতিটি ধরনের কয়েনের অসীম সংখ্যা রয়েছে। অনুরোধ করা মান পরিবর্তন করতে আমরা যেকোনো ধরনের কয়েনের ন্যূনতম সংখ্যা নেওয়ার চেষ্টা করব। উদাহরণ হিসেবে, মান 22-এর জন্য:আমরা ন্যূনতম হিসেবে {10, 10, 2}, 3 কয়েন বেছে নেব।

ইনপুট এবং আউটপুট

Input:
The required value. Say 48
Output:
Minimum required coins. Here the output is 7.
48 = 10 + 10 + 10 + 10 + 5 + 2 + 1

অ্যালগরিদম

minCoins(coinList, n, value)

ইনপুট: বিভিন্ন মুদ্রার তালিকা, মুদ্রার সংখ্যা, প্রদত্ত মান।

আউটপুট: প্রদত্ত মান পেতে ন্যূনতম সংখ্যক কয়েন।

Begin
   if value = 0, then
      return 0
   define coins array of size value + 1, fill with ∞
   coins[0] := 0

   for i := 1 to value, do
      for j := 0 to n, do
         if coinList[j] <= i, then
            tempCoins := coins[i-coinList[j]]
         if tempCoins ≠ ∞ and (tempCoins + 1) < coins[i], then
            coins[i] := tempCoins + 1
      done
   done

   return coins[value]
End

উদাহরণ

#include<iostream>
using namespace std;

int minCoins(int coinList[], int n, int value) {
   int coins[value+1];       //store minimum coins for value i

   if(value == 0)
      return 0;              //for value 0, it needs 0 coin

   coins[0] = 0;

   for (int i=1; i<=value; i++)
      coins[i] = INT_MAX;            //initially all values are infinity except 0 value

   for (int i=1; i<=value; i++) {      //for all values 1 to value, find minimum values
      for (int j=0; j<n; j++)
         if (coinList[j] <= i) {
            int tempCoins = coins[i-coinList[j]];
         if (tempCoins != INT_MAX && tempCoins + 1 < coins[i])
            coins[i] = tempCoins + 1;
      }
   }
   return coins[value];       //number of coins for value
}

int main() {
   int coins[] = {1, 2, 5, 10};
   int n = 4, value;
   cout << "Enter Value: "; cin >> value;
   cout << "Minimum "<<minCoins(coins, n, value)<<" coins required.";
   return 0;
}

আউটপুট

Enter Value: 48
Minimum 7 coins required.