मान लीजिए हमारे पास कोई राशि है, और हमें विभिन्न मूल्यवर्ग के नोटों की न्यूनतम संख्या ढूंढनी है, जो दी गई राशि का योग करते हैं। उच्चतम मूल्यवर्ग के नोटों से शुरू करें, दी गई राशि के लिए अधिकतम संभव नोट खोजने का प्रयास करें। यहां मान लिया गया है कि हमारे पास अनंत मात्रा में {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1} हैं। इसलिए यदि राशि 800 है, तो नोट 500, 200, 100 होंगे।
यहां हम इस समस्या को हल करने के लिए लालची दृष्टिकोण (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
