Thuật toán tham lam tìm số tiền tệ tối thiểu trong C++

Thuật toán tham lam (Greedy)

Tìm giải pháp tối ưu cục bộ ở mỗi bước để đạt tối ưu toàn cục. Bài toán: đổi tiền với số tờ/xu ít nhất.

Mệnh giá (Việt Nam)

{1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}

Ví dụ

1231 → 500×2 + 100×2 + 20 + 10 + 1 = 7 tờ/xu
2150 → 2000 + 100 + 50 = 3 tờ/xu

Thuật toán

Input: sum
coins = []
For i từ mệnh giá lớn nhất đến nhỏ:
    While sum >= menh_gia[i]:
        sum -= menh_gia[i]
        coins.push_back(menh_gia[i])
In coins

Mã nguồn C++

#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 v : coins) cout << v << "\t";
}

int main() {
    int n = 3253;
    cout << "Tiền tệ tối thiểu cho " << n << ": ";
    minchange(n);
    return 0;
}

Kết quả

2000 500 500 200 50 2 1