Tìm số đồng xu tối thiểu để thanh toán tổng tiền trong C++

Cho N, đồng xu mệnh giá 1, 10, 25. Tìm số đồng xu tối thiểu để thanh toán đúng N. Ví dụ N=14 → 5 (1*10 + 4*1).

Tham lam: dùng đồng 25 nhiều nhất, sau đó 10, cuối cùng 1.

Ví dụ

#include<iostream> using namespace std; int countMinCoins(int n) {    if(n<10)       return n;    else if(n > 9 && n < 25){       int count = n/10;       count += n%10;       return count;    } else {       int count = n/25;       return count + countMinCoins(n%25);    } } int main() {    int n = 88;    cout << "Minimum number of coins required: " << countMinCoins(n); }

Kết quả

Minimum number of coins required: 7