Tổng quan
Bài Đổi Tiền hỏi số đồng xu ít nhất cộng lại bằng một số tiền mục tiêu, cho trước một bộ mệnh giá với số lượng mỗi loại không hạn chế. Bảng quy hoạch động trả lời cho mọi số tiền từ 0 tới mục tiêu, dựng mỗi đáp án từ các đáp án nhỏ hơn đã giải.
Nó có chỗ trong danh mục này phần lớn vì thứ nó bác bỏ. Cứ đưa ra đồng lớn nhất còn vừa, lặp đi lặp lại, là cách trực giác và cũng là cách thu ngân thật vẫn làm — và nó sai với một số hệ tiền. Với các đồng 1, 3 và 4, đổi số 6 theo tham lam ra 4+1+1, ba đồng; cái bảng tìm ra 3+3, hai đồng. Tiền Việt và phần lớn tiền tệ hiện đại tình cờ là những hệ chuẩn tắc mà tham lam luôn đúng, và chính vì thế mà lỗi này rất dễ bị bỏ sót.
Đổi Tiền (QHĐ) hoạt động thế nào?
- Tạo một mảng kích thước số tiền + 1 và điền vô cực, trừ vị trí 0 bằng 0 — không cần đồng nào để đổi ra số không.
- Với mọi số tiền a từ 1 tới mục tiêu, lần lượt xét từng mệnh giá đồng xu.
- Nếu đồng xu không lớn hơn a, đáp án ứng viên là 1 cộng đáp án đã lưu cho a − mệnh giá.
- Giữ ứng viên nhỏ nhất trong tất cả các đồng và lưu vào vị trí a.
- Ô cuối chứa đáp án, hoặc vô cực nếu số tiền hoàn toàn không đổi được. Muốn liệt kê các đồng, hãy lưu mệnh giá tạo ra mỗi ô rồi lần ngược.
Khi nào nên dùng?
- Xử lý tiền mặt và trả tiền thối trong hệ thống bán hàng và máy bán tự động.
- Bất kỳ bài toán 'ít mảnh nhất để đạt một tổng' nào: tem, quả cân, kích thước gói tin, các khoản thanh toán rời rạc.
- Minh họa vì sao một heuristic tham lam cần được chứng minh chứ không phải tin theo trực giác, vì phản ví dụ chỉ dài hai dòng.
- Làm bậc thang tới biến thể đếm — có bao nhiêu cách khác nhau để đổi ra số tiền — dùng cùng cái bảng với hai vòng lặp đổi chỗ.
Phân tích độ phức tạp
Thời gian là O(m·A) với m mệnh giá và số tiền mục tiêu A: mỗi số tiền được ghé qua một lần và mỗi đồng xu đều được thử với nó. Bộ nhớ là O(A) cho bảng một chiều, cộng thêm O(A) nữa nếu lưu cả mệnh giá đã chọn để dựng lại đáp án. Giống knapsack, đây là bài giả đa thức — A là một giá trị chứ không phải độ dài đầu vào — nên một mục tiêu cỡ hàng tỉ là ngoài tầm với, bất kể có ít mệnh giá đến đâu.
Câu hỏi thường gặp
Chính xác thì phương pháp tham lam đúng khi nào?
Chỉ với các hệ tiền chuẩn tắc, và việc xác định một hệ cho trước có chuẩn tắc hay không lại là một bài toán riêng, không hiển nhiên. Quy tắc thực dụng: nếu không phải bạn tự chọn bộ mệnh giá, đừng cho rằng tham lam an toàn — cứ chạy bảng.
Làm sao phân biệt 'không thể đổi' với 'không cần đồng nào'?
Vị trí 0 thật sự bằng 0, còn mọi số tiền không đạt tới được vẫn giữ giá trị vô cực đánh dấu. Nếu điền khởi tạo bằng 0 thay vì vô cực, chương trình sẽ lặng lẽ báo thành công cho những số tiền không đổi được — một lỗi phổ biến ở lần cài đặt đầu tiên.
Nếu mỗi đồng chỉ được dùng một lần thì khác gì?
Nó trở thành bài knapsack 0/1. Cách sửa cũng chính là cách đó: duyệt số tiền theo chiều giảm để một đồng đã dùng ở số tiền nhỏ hơn không bị dùng lại trong cùng lượt của vật đó.