একটি টাকার পরিমাণ দেওয়া আছে। আমাদের ন্যূনতম সংখ্যক নোট (currency notes) বের করতে হবে যাদের মোট যোগফল দেওয়া পরিমাণের সমান হবে। সর্বোচ্চ ডিনোমিনেশন (denomination) বা মানের নোট থেকে শুরু করে যতটুকু সম্ভব নোট নেওয়া যাবে। এখানে অনুমান করা হয় {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1} অসীম পরিমাণে আছে। উদাহরণস্বরূপ, পরিমাণ ৮০০ হলে নোটগুলো হবে ৫০০, ২০০, ১০০।
এখানে লোভী পদ্ধতি (greedy approach) ব্যবহার করে সমাধান করা হয়।
উদাহরণ
#include<iostream> using namespace std; void countNotes(int amount) { int notes[10] = { 2000, 500, 200, 100, 50, 20, 10, 5, 2, 1 }; int noteFreq[10] = { 0 }; for (int i = 0; i < 10; i++) { if (amount >= notes[i]) { noteFreq[i] = amount / notes[i]; amount = amount - noteFreq[i] * notes[i]; } } cout << "Note count:" << endl; for (int i = 0; i < 9; i++) { if (noteFreq[i] != 0) { cout << notes[i] << " : " << noteFreq[i] << endl; } } } int main() { int amount = 1072; cout << "Total amount is: " << amount << endl; countNotes(amount); }আউটপুট
Total amount is: 1072 Note count: 500 : 2 50 : 1 20 : 1 2 : 1
