Câu hỏi 8
Từ nguồn cung cấp không giới hạn các đồng xu $1$-cent, $10$-cent và $25$-cent, Silas muốn tìm một bộ sưu tập các đồng xu có tổng giá trị là $N$ cent, trong đó $N$ là một số nguyên dương. Anh ta sử dụng cái gọi là *thuật toán tham lam*, liên tục chọn đồng xu có giá trị lớn nhất không khiến giá trị bộ sưu tập của anh ta vượt quá $N.$ Ví dụ: để nhận được $42$ xu, Silas sẽ chọn đồng xu $25$-cent, sau đó là đồng xu $10$-cent, sau đó là $7$ $1$ xu xu. Tuy nhiên, bộ sưu tập $9$ xu này sử dụng nhiều xu hơn mức cần thiết để có được tổng cộng $42$ xu; thật vậy, việc chọn đồng xu $4$ $10$-cent và $2$ $1$-cent sẽ đạt được tổng giá trị tương tự chỉ với $6$ xu.
Nói chung, thuật toán tham lam thành công với một $N$ nhất định nếu không có bộ sưu tập nào khác gồm $1$-cent, $10$-cent và $25$-cent có tổng giá trị là $N$ xu sử dụng ít xu hơn so với bộ sưu tập được đưa ra bởi thuật toán tham lam. Tìm số giá trị của $N$ giữa $1$ và $1000$ để thuật toán tham lam thành công.
Nói chung, thuật toán tham lam thành công với một $N$ nhất định nếu không có bộ sưu tập nào khác gồm $1$-cent, $10$-cent và $25$-cent có tổng giá trị là $N$ xu sử dụng ít xu hơn so với bộ sưu tập được đưa ra bởi thuật toán tham lam. Tìm số giá trị của $N$ giữa $1$ và $1000$ để thuật toán tham lam thành công.