Thuật toán tham lam (Greedy)

Thuật toán tham lam chọn phương án tốt nhất tại mỗi bước để đạt kết quả tối ưu toàn cục.

Yêu cầu

Một máy ATM có các tờ tiền: 500, 200, 100, 50, 20, 10. Nhập số tiền n, in ra số tờ tiền ít nhất để đổi được n. Nếu không thể đổi, in "-1".

Ví dụ

Input: 750 Output: 4 (1 to 500 + 1 to 200 + 1 to 50)

Input: 30 Output: 3 (1 to 20 + 1 to 10)