ন্যূনতম কয়েন চেঞ্জ সমস্যা

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

নোট - ধরে নেওয়া হয়েছে প্রতিটি কয়েন C-এর অসংখ্য সংখ্যা আছে।

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

উদাহরণস্বরূপ, মান 22 এর জন্য - আমরা {10, 10, 2} বেছে নেব, অর্থাৎ ৩টি কয়েন ন্যূনতম।

এই অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(V), যেখানে V হলো মান।

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

ইনপুট: একটি মান, ধরা যাক 47 আউটপুট: Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2

অ্যালগরিদম

findMinCoin(value)

ইনপুট - চেঞ্জ করার মান

আউটপুট - কয়েনের সেট।

শুরু
  কয়েন সেট মান {1, 2, 5, 10} দিয়ে
  সব কয়েন i এর জন্য উচ্চতর মান থেকে নিম্নতর মানের দিকে করুন
    যতক্ষণ value >= coins[i] করুন
      value := value - coins[i]
      কয়েন লিস্টে coins[i] যোগ করুন
    শেষ
  শেষ
  কয়েন লিস্টের সব এন্ট্রি প্রিন্ট করুন।
শেষ

উদাহরণ

#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]); //লিস্টে কয়েন যোগ করুন } } 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