Đổi tiền với số xu ít nhất
Đây là bài quy hoạch động đầu tiên mà ai cũng gặp: đổi một số tiền bằng ít xu nhất. Nếu
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: python-basics, python-list-basics, python-loop-basics.
Nội dung đề bài
Mô tả bài toán
Đây là bài quy hoạch động đầu tiên mà ai cũng gặp: đổi một số tiền bằng ít xu nhất. Nếu chọn xu to nhất trước, có bộ mệnh giá bị lừa ngay. Cách đúng là xây dần đáp án cho từng số tiền nhỏ hơn, vì số tiền v luôn được giải từ một số tiền nhỏ hơn cộng thêm một xu.
Yêu cầu
Viết hàm min_coins(coins, amount) trả về số xu ít nhất để tạo đúng amount, biết mỗi mệnh giá được dùng không giới hạn số lần. Nếu không cách nào tạo được đúng amount thì trả về -1. Với amount = 0 thì trả về 0 (không cần xu nào).
Công thức truy hồi (đã kiểm tra bằng tay): best[0] = 0, và với v từ 1 đến amount, best[v] = 1 + min(best[v - coin]) trên mọi coin <= v mà best[v - coin] tạo được.
Quy ước nộp bài
Nộp hàm min_coins trong solution.py. Hệ thống gọi hàm trực tiếp bằng hai tham số từ khoá coins và amount, rồi so giá trị trả về với kết quả đã cho; không đọc stdin và không in ra stdout.
Input
- coins: danh sách mệnh giá, mỗi mệnh giá là số nguyên dương.
- amount: số tiền mục tiêu, số nguyên không âm nhỏ hơn hoặc bằng 1000.
Output
Một số nguyên là số xu ít nhất, hoặc -1 nếu amount không tạo được.
Ràng buộc
- Số mệnh giá từ 1 đến 10; mệnh giá không trùng nhau.
- Mỗi mệnh giá dùng được nhiều lần, đây không phải bài "mỗi loại một lần".
- Bỏ chọn xu to nhất trước: với coins = [1, 3, 4] và amount = 6, cách tham lam cho
3 xu (4 + 1 + 1) trong khi đáp án đúng là 2 xu (3 + 3).
Ví dụ 1
Input
min_coins(coins=[1, 2, 5], amount=11)
Output
3
Ví dụ 2
Input
min_coins(coins=[2], amount=3)
Output
-1
Giải thích
Với coins = [1, 2, 5] và amount = 11: 5 + 5 + 1 nên hàm trả về 3. Không có cách nào dùng hai xu để tạo 11 vì 5 + 5 = 10 và 5 + 2 = 7.
Với coins = [3, 7] và amount = 5: mọi tổ hợp đều không bằng 5, hàm trả về -1.
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.
