लालची एल्गोरिथम एक एल्गोरिथम है जिसका उपयोग दी गई समस्या के लिए एक इष्टतम समाधान खोजने के लिए किया जाता है। लालची एल्गोरिदम प्रत्येक भाग के स्थानीय रूप से इष्टतम समाधान (समस्या के एक हिस्से के लिए इष्टतम समाधान) ढूंढकर काम करता है, इसलिए दिखाएं कि वैश्विक इष्टतम समाधान मिल सकता है।
इस समस्या में, हम एक लालची एल्गोरिथम का उपयोग सिक्कों/नोटों की न्यूनतम संख्या को खोजने के लिए करेंगे जो दी गई राशि के लिए मेकअप कर सकते हैं। इसके लिए हम सभी वैध सिक्कों या नोटों यानी {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000} के मूल्यवर्ग को ध्यान में रखेंगे। और हमें इन सिक्कों/नोटों की संख्या वापस करने की आवश्यकता होगी, जिन्हें हमें योग करने की आवश्यकता होगी।
आइए संदर्भ को बेहतर ढंग से समझने के लिए कुछ उदाहरण लेते हैं -
उदाहरण 1 -
Input : 1231 Output : 7
स्पष्टीकरण - हमें 500 रुपये के दो नोट, 100 रुपये के दो नोट, 20 रुपये के एक नोट, 10 रुपये के एक नोट और 1 रुपये के एक सिक्के की आवश्यकता होगी। यानी 2+2+1+1+1 =7
उदाहरण 2 -
Input : 2150 Output : 3
व्याख्या - हमें 2000 रुपये के एक नोट, 100 रुपये के एक नोट और 50 रुपये के एक नोट की आवश्यकता होगी।
लालची एल्गोरिथम का उपयोग करके इस समस्या को हल करने के लिए, हम पाएंगे कि कौन सा सबसे बड़ा मूल्यवर्ग है जिसका उपयोग किया जा सकता है। फिर हम योग में से सबसे बड़े मूल्य को घटा देंगे और फिर से यही प्रक्रिया तब तक करेंगे जब तक कि योग शून्य न हो जाए।
एल्गोरिदम
Input: sum, Initialise the coins = 0 Step 1: Find the largest denomination that can be used i.e. smaller than sum. Step 2: Add denomination two coins and subtract it from the Sum Step 3: Repeat step 2 until the sum becomes 0. Step 4: Print each value in 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<int> 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