Đổi tiền bằng ít đồng xu nhất
Bạn có một danh sách mệnh giá đồng xu và không hạn chế số lượng mỗi loại. Câu hỏi đặt ra là
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, arrays.
Nội dung đề bài
Mô tả bài toán
Bạn có một danh sách mệnh giá đồng xu và không hạn chế số lượng mỗi loại. Câu hỏi đặt ra là dùng ít đồng xu nhất để đổi đúng một số tiền cho trước. Đây là ví dụ đầu tiên cho thấy quy hoạch động thắng được cách chọn tham lam lớn nhất trước.
Yêu cầu
Cho m loại đồng xu và số tiền t. Hãy tìm số đồng xu nhỏ nhất có tổng đúng bằng t. Nếu không có cách đổi nào thì in ra -1.
Quy ước nộp bài
Nộp tệp solution.cpp đọc dữ liệu từ stdin và ghi kết quả ra stdout. In đúng một số nguyên, không in thêm chữ hay dấu cách thừa.
Input
- Dòng thứ nhất: hai số nguyên m và t (1 <= m <= 20, 1 <= t <= 500).
- Dòng thứ hai: m số nguyên là mệnh giá các đồng xu (1 <= giá trị <= 500), cách nhau
bởi dấu cách. Mỗi mệnh giá được dùng bao nhiêu lần cũng được.
Output
- Một số nguyên trên một dòng: số đồng xu ít nhất, hoặc -1 nếu không đổi được.
Ràng buộc
- Mỗi loại đồng xu có vô số bản sao, không có ràng buộc "mỗi loại dùng tối đa một lần".
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
3 6
1 3 4
Output
2
Ví dụ 2
Input
3 11
1 3 4
Output
3
Giải thích
Ta đổi 6 bằng hai đồng 3 + 3 nên in ra:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
