Giả sử chúng ta có số tiền như vậy, và chúng ta phải tìm số lượng tối thiểu các tờ tiền có mệnh giá khác nhau, tổng số tiền đã cho. Bắt đầu từ các tờ tiền có mệnh giá cao nhất, cố gắng tìm nhiều tờ tiền nhất có thể với số tiền nhất định. Ở đây giả định là chúng ta có vô hạn {2000, 500, 200, 100, 50, 20, 10, 5, 2, 1}. Vì vậy, nếu số tiền được nói là 800, thì các ghi chú sẽ là 500, 200, 100.
Ở đây chúng tôi sẽ sử dụng phương pháp tham lam để giải quyết vấn đề này.
Ví dụ
#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);
} Đầu ra
Total amount is: 1072 Note count: 500 : 2 50 : 1 20 : 1 2 : 1