Tổng quan
Kỹ thuật tham lam xây dựng lời giải bằng cách liên tục chọn phương án trông tốt nhất ngay lúc này. Với bài toán đổi tiền, nghĩa là: mỗi bước lấy đồng xu lớn nhất còn vừa với số tiền còn lại, rồi lặp lại.
Tham lam nhanh và đơn giản, nhưng đáp án chỉ tối ưu với hệ tiền 'chuẩn tắc' (như các loại tiền tệ thông thường). Với hệ khác nó bị chứng minh là dưới tối ưu — với các đồng {1, 3, 4} để tạo 6, tham lam chọn 4+1+1 (ba đồng) trong khi tối ưu thực là 3+3 (hai đồng).
Tham lam (Đổi tiền) hoạt động thế nào?
- Sắp các mệnh giá theo thứ tự giảm dần để đồng lớn nhất đứng đầu.
- Lấy càng nhiều đồng lớn nhất hiện tại càng tốt sao cho vừa với số tiền còn lại.
- Trừ các đồng đã lấy khỏi số tiền còn lại và chuyển sang đồng nhỏ hơn kế tiếp.
- Dừng khi số tiền còn lại về không, hoặc báo thất bại nếu không đồng nào vừa.
Khi nào nên dùng?
- Đổi tiền với hệ chuẩn tắc (ví dụ 1, 5, 10, 25) nơi tham lam được chứng minh là tối ưu.
- Các bài toán có tính chất chọn tham lam và cấu trúc con tối ưu (mã Huffman, lập lịch khoảng, cây khung nhỏ nhất).
- Chuyển sang quy hoạch động cho hệ tiền tùy ý, nơi tham lam có thể cho số đồng sai.
Phân tích độ phức tạp
Đổi tiền tham lam sắp các mệnh giá trong O(n log n) rồi quét tuyến tính một lần, nên chạy trong O(n log n) (O(n) nếu các đồng đã được sắp) và O(1) bộ nhớ phụ. Cái giá của nó là nguy cơ cho đáp án không tối ưu trên hệ không chuẩn tắc — lời nhắc kinh điển rằng nhanh không đồng nghĩa với đúng.
Câu hỏi thường gặp
Khi nào đổi tiền tham lam thất bại?
Trên các hệ không chuẩn tắc. Với các đồng {1, 3, 4} tạo 6, tham lam lấy 4 rồi 1+1 thành ba đồng, nhưng 3+3 chỉ dùng hai. Bất cứ khi nào một đồng lớn hơn cản một tổ hợp tốt hơn của các đồng nhỏ, tham lam là dưới tối ưu.
Làm sao đảm bảo số đồng xu ít nhất?
Dùng quy hoạch động: dp[amount] = 1 + min theo các đồng c của dp[amount − c]. Nó chạy trong O(amount × n) và tối ưu với mọi hệ tiền, khác với tham lam.