Tham lam — Greedy
Tham lam là tư tưởng giải bài tối ưu bằng cách ở mỗi bước luôn chọn phương án "tốt nhất" tại thời điểm đó, không xét tới ảnh hưởng về sau. Cái hay là với nhiều bài, chuỗi các lựa chọn tốt-tại-chỗ lại cho ra kết quả tối ưu toàn cục.
Điều khó và cũng quan trọng nhất không nằm ở việc viết code, mà ở chỗ chứng minh được quy luật tham lam thực sự đúng — vì không phải bài tối ưu nào cũng giải tham lam được. Áp nhầm thì lời giải vẫn chạy nhanh nhưng cho kết quả sai.
Cách chứng minh kinh điển là lập luận hoán đổi (exchange argument): giả sử tồn tại một lời giải tối ưu khác với lựa chọn tham lam, rồi chỉ ra ta luôn "hoán đổi" được về phía lựa chọn tham lam mà kết quả không tệ đi. Khi mọi khác biệt đều đổi về được, greedy cũng tối ưu. Trong phỏng vấn, nói được lập luận này quan trọng hơn chính đoạn code.
Tham lam như đi đường mà mỗi ngã rẽ luôn chọn hướng có vẻ tốt nhất ngay lúc đó, không tính xa.
Cái hay là với nhiều bài, chuỗi lựa chọn tốt-tại-chỗ lại cho ra kết quả tối ưu toàn cục — nhưng phải chứng minh được điều đó, nếu không sẽ chọn hớ.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Tham lam
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| tốt nhất tại chỗ | Quyết định ngay, không xét lại sau |
| một lần quét | Giữ vài biến trạng thái thay vì bảng dp |
| max/min toàn cục | Chứng minh lựa chọn tham lam dẫn tới tối ưu |
Khi nào dùng
4 tình huống điển hình cần nghĩ đến chủ đề này
Mỗi bước có một lựa chọn rõ ràng là "tốt nhất tại chỗ"
Lựa chọn tại chỗ không cần xét lại ở bước sau (không backtrack)
Chứng minh được lựa chọn tham lam dẫn tới kết quả tối ưu toàn cục
Bài tối ưu hoá nhưng không có bài toán con chồng lặp như quy hoạch động
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Local optimal KHÔNG đảm bảo global optimal: dùng DP (vd 0/1 Knapsack — fractional thì greedy được, 0/1 thì không)
Cần liệt kê tất cả nghiệm khả dĩ: greedy chỉ trả 1 — dùng Backtracking
Bài có subproblem chồng (overlapping): khả năng cao DP đúng hơn
Hình minh hoạ
Sơ đồ thể hiện cách giải của chủ đề này.
Đổi 36 với xu [25, 10, 5, 1]: mỗi bước chọn đồng lớn nhất ≤ số còn lại (25 → 10 → 1). Tối ưu cục bộ cho ra tối ưu toàn cục với hệ tiền chuẩn.
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function greedyPattern(nums: number[]): R {
let best = initState()
for (const x of nums) {
// Chọn tốt nhất tại chỗ, cập nhật trạng thái chạy
best = chooseLocalBest(best, x)
}
return best
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Mỗi bước chọn cực trị tại chỗ, không xét lại lựa chọn cũ
Khác quy hoạch động: tham lam không lưu bảng kết quả bài con, chỉ giữ trạng thái chạy
Phải kiểm chứng tính đúng — không phải bài tối ưu nào cũng tham lam được
Công cụ chứng minh: lập luận hoán đổi (exchange argument) — đổi nghiệm tối ưu về phía lựa chọn tham lam mà không tệ đi
Lỗi thường gặp
Áp tham lam cho bài cần xét toàn cục → ra kết quả sai
Không chứng minh lựa chọn tham lam đúng, chỉ "cảm thấy hợp lý"
Nhầm với quy hoạch động và lưu cả bảng dp dư thừa
Độ phức tạp
Thường O(n) hoặc O(n log n) nếu cần sắp xếp trướcBài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay