Câu hỏi 122
Từ một nguồn không giới hạn các đồng xu 1 xu, 10 xu và 25 xu, Silas muốn tìm một bộ đồng xu có tổng giá trị $N$ xu, trong đó $N$ là một số nguyên dương. Anh dùng cái gọi là thuật toán tham lam, lần lượt chọn đồng xu có giá trị lớn nhất mà không làm tổng giá trị của bộ xu vượt quá $N$. Ví dụ, để có 42 xu, Silas sẽ chọn một đồng 25 xu, rồi một đồng 10 xu, rồi 7 đồng 1 xu. Tuy nhiên, bộ 9 đồng xu này dùng nhiều đồng xu hơn mức cần thiết để có tổng 42 xu; thật vậy, chọn 4 đồng 10 xu và 2 đồng 1 xu cũng đạt cùng tổng giá trị mà chỉ dùng 6 đồng xu.
Tổng quát, thuật toán tham lam *thành công* với một giá trị $N$ nếu không có bộ đồng xu 1 xu, 10 xu và 25 xu nào khác có tổng giá trị $N$ xu mà dùng ít đồng xu hơn hẳn so với bộ xu do thuật toán tham lam đưa ra. Tìm số giá trị của $N$ từ 1 đến 1000 (tính cả hai đầu) mà thuật toán tham lam thành công.
Tổng quát, thuật toán tham lam *thành công* với một giá trị $N$ nếu không có bộ đồng xu 1 xu, 10 xu và 25 xu nào khác có tổng giá trị $N$ xu mà dùng ít đồng xu hơn hẳn so với bộ xu do thuật toán tham lam đưa ra. Tìm số giá trị của $N$ từ 1 đến 1000 (tính cả hai đầu) mà thuật toán tham lam thành công.