সি/সি++-এ গ্রিডি অ্যালগরিদম দিয়ে ন্যূনতম কয়েন/নোট বের করা

গ্রিডি অ্যালগরিদম (Greedy Algorithm) হলো একটি অ্যালগরিদম যা প্রতিটি অংশের জন্য স্থানীয়ভাবে অপ্টিমাল সমাধান (locally optimal solution) খুঁজে বের করে গ্লোবালি অপ্টিমাল সমাধান পাওয়ার চেষ্টা করে।

এই সমস্যাতে, দেওয়া một টাকার পরিমাণ (sum) তৈরির জন্য ন্যূনতম কয়েন বা নোটের সংখ্যা বের করতে হবে। বৈধ কয়েন/নোটের মান (denominations): { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 }।

উদাহরণ ১:

Input: 1231
Output: 7
Explanation: ৫০০ টাকার ২ টি নোট, ১০০ টাকার ২ টি নোট, ২০ টাকার ১ টি নোট, ১০ টাকার ১ টি নোট, ১ টাকার ১ টি কয়েন = ২+২+১+১+১ = ৭

উদাহরণ ২:

Input: 2150
Output: 3
Explanation: ২০০০ টাকার ১ টি নোট, ১০০ টাকার ১ টি নোট, ৫০ টাকার ১ টি নোট।

গ্রিডি অ্যালগরিদম ব্যবহার করে সমাধান: সর্বোচ্চ মানের ডিনোমিনেশন বের করুন যা sum-এ ফিট হয়। সেটি sum-থেকে বিয়োগ করুন এবং sum ০ না হওয়া পর্যন্ত এটি दुहरান।
অ্যালগরিদম
Input: sum, Initialise coins = 0
Step 1: সর্বোচ্চ ডিনোমিনেশন বের করুন যা sum-এ ফিট হয় (sum-এর চেয়ে ছোট বা সমান)।
Step 2: সেটি coins-এ যোগ করুন এবং sum-থেকে বিয়োগ করুন।
Step 3: Step 2 दुহরান যতক্ষণ না sum ০ হয়।
Step 4: coins-এ থাকা প্রতিটি মান প্রিন্ট করুন।
সি++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;

int notes[] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 };
int n = sizeof(notes) / sizeof(notes[0]);

void minchange(int sum) {
    vector coins;
    for (int i = n - 1; i >= 0; i--) {
        while (sum >= notes[i]) {
            sum -= notes[i];
            coins.push_back(notes[i]);
        }
    }
    for (int i = 0; i < coins.size(); i++)
        cout << coins[i] << "\t";
}

int main() {
    int n = 3253;
    cout << "The minimum number of coins/notes that sum up " << n << " is \t ";
    minchange(n);
    return 0;
}
আউটপুট
The minimum number of coins/notes that sum up 3253 is 2000 500 500 200 50 2 1