Ở sảnh E1 khu HUTECH Thu Duc Compus được lắp mới một máy rút tiền tự động của ngân hàng HDBank. Trong máy có n loại tiền mệnh giá lần lượt là a_1, a_2, a_3, ... , a_n, mỗi mệnh giá có số lượng đủ nhiều cho sinh viên HUTECH rút.
Khi sinh viên có yêu cầu rút số tiền S, chương trình điều khiển sẽ xác định xem có thể trả được số tiền đúng bằng S không, nếu có, chương trình điều khiển sẽ chọn cách trả với số lượng tờ ít nhất.
Yêu cầu: Hãy tính số lượng tờ tiền ít nhất để trả số tiền s.