लालची एल्गोरिदम (Greedy Algorithm) एक एल्गोरिदम है जिसका उपयोग दी गई समस्या के लिए इष्टतम समाधान ढूंढने के लिए किया जाता है। लालची एल्गोरिदम प्रत्येक भाग के लिए स्थानीय रूप से इष्टतम समाधान (समस्या के एक भाग के लिए इष्टतम समाधान) ढूंढकर काम करता है ताकि वैश्विक इष्टतम समाधान ढूंढा जा सके।
इस समस्या में, हम दिए गए योग को बनाने के लिए आवश्यक न्यूनतम सिक्कों/नोटों की संख्या ढूंढने के लिए लालची एल्गोरिदम का उपयोग करेंगे। इसके लिए हम सभी वैध सिक्कों या नोटों यानी {1, 2, 5, 10, 20, 50, 100, 200, 500, 2000} के मूल्यवर्ग पर विचार करेंगे। और हमें इन सिक्कों/नोटों की संख्या लौटानी होगी जिनकी आवश्यकता योग बनाने के लिए होगी।
आइए कुछ उदाहरण लेकर संदर्भ को बेहतर ढंग से समझते हैं:
उदाहरण 1 −
इनपुट: 1231 आउटपुट: 7
व्याख्या − हमें दो 500 रुपये के नोट, दो 100 रुपये के नोट, एक 20 रुपये का नोट, एक 10 रुपये का नोट और एक 1 रुपये का सिक्का चाहिए। जो कुल 2+2+1+1+1 = 7 होता है।
उदाहरण 2 −
इनपुट: 2150 आउटपुट: 3
व्याख्या − हमें एक 2000 रुपये का नोट, एक 100 रुपये का नोट और एक 50 रुपये का नोट चाहिए।
इस समस्या को लालची एल्गोरिदम का उपयोग करके हल करने के लिए, हम ढूंढेंगे कि कौन सा सबसे बड़ा मूल्यवर्ग उपयोग किया जा सकता है। फिर हम सबसे बड़े मूल्यवर्ग को योग से घटाएंगे और तब तक वही प्रक्रिया दोहराएंगे जब तक योग शून्य न हो जाए।
एल्गोरिदम
इनपुट: sum, सिक्के = 0 इनिशियलाइज़ करें चरण 1: सबसे बड़ा मूल्यवर्ग ढूंढें जिसका उपयोग किया जा सकता है यानी योग से छोटा। चरण 2: मूल्यवर्ग को सिक्कों में जोड़ें और इसे योग से घटाएं चरण 3: चरण 2 को तब तक दोहराएं जब तक योग 0 न हो जाए। चरण 4: सिक्कों में प्रत्येक मान प्रिंट करें।
उदाहरण
#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
