Tham lam (Greedy)
Tham lam (greedy) là chiến lược "cứ chọn cái tốt nhất trước mắt rồi đi tiếp, không hối tiếc". Đơn giản và nhanh, nhưng không phải lúc nào cũng đúng. Bài này dạy bạn hai chìa khoá để biết khi nào tham lam cho đáp án tối ưu và khi nào nó dẫn bạn vào ngõ cụt.
1. Trực quan: người leo núi trong sương mù
Hãy tưởng tượng bạn leo núi giữa sương mù dày, chỉ nhìn được vài bước quanh chân. Chiến lược tham lam là: mỗi bước, bước về phía dốc lên cao nhất ngay cạnh bạn. Đơn giản, không cần bản đồ.
đỉnh thật (cao nhất)
╱╲ ← bạn KHÔNG tới được
______╱ ╲___
╱ ▲ ╲
╱ bạn kẹt ╲
╱ ở đỉnh nhỏ ╲
Nếu địa hình "đẹp" (chỉ có một đỉnh), bước lên dốc nhất luôn đưa bạn tới đỉnh thật. Nhưng nếu có đỉnh nhỏ phụ (local maximum), tham lam sẽ kẹt ở đó và tưởng đã xong. Đó chính là linh hồn của greedy: nhanh nhưng thiển cận.
2. Hai điều kiện để tham lam ĐÚNG
Một bài toán chịu giải đúng bằng greedy khi có cả hai tính chất:
| Tính chất | Nghĩa là | Ví dụ trực giác |
|---|---|---|
| Lựa chọn tham lam (greedy choice) | Chọn tốt nhất cục bộ ở mỗi bước dẫn tới lời giải tối ưu toàn cục | Luôn lấy đồng xu lớn nhất có thể |
| Cấu trúc con tối ưu (optimal substructure) | Sau khi chọn, bài toán còn lại cũng được giải tối ưu bằng cùng cách | Đổi phần tiền còn lại vẫn theo quy tắc cũ |
Nếu thiếu một trong hai, greedy có thể trật. Cách kiểm tra chắc chắn nhất là chứng minh (thường bằng lập luận "đổi chỗ" — exchange argument), nhưng với người mới: hãy thử phản ví dụ.
3. Ví dụ 1: Đổi tiền — khi đúng, khi sai
Bài toán: trả số tiền n bằng ít đồng xu nhất. Greedy: cứ lấy đồng lớn nhất không vượt n.
- Với bộ xu 1, 5, 10, 25 (kiểu USD): greedy luôn tối ưu. Trả 30 → 25 + 5 (2 đồng). Đúng.
- Với bộ xu 1, 3, 4: greedy sai! Trả 6 → greedy lấy 4 + 1 + 1 = 3 đồng, nhưng 3 + 3 = 2 đồng mới tối ưu.
Bài học: greedy phụ thuộc bộ dữ liệu. Cùng một thuật toán, đổi bộ xu là sai ngay.
4. Ví dụ 2: Chọn lịch hoạt động (activity selection)
Có n hoạt động, mỗi cái có giờ bắt đầu và kết thúc. Bạn muốn tham gia nhiều nhất mà không
trùng giờ. Đây là bài greedy kinh điển và đúng đắn.
Mẹo vàng: luôn chọn hoạt động kết thúc sớm nhất trong số còn hợp lệ. Vì kết thúc sớm chừa lại nhiều thời gian nhất cho các hoạt động sau — đó chính là tính lựa chọn tham lam.
Thoi gian: 1 2 3 4 5 6 7 8 9
A (1-3): [===]
B (2-5): [=====]
C (4-7): [=====]
D (6-9): [=====]
Chon ket thuc som: A(het 3) -> C(het 7) -> ... = 2-3 hoat dong
Vì sao "kết thúc sớm nhất" đúng? Lập luận đổi chỗ: nếu lời giải tối ưu nào đó không chọn hoạt động kết thúc sớm nhất, ta luôn thay phần tử đầu của nó bằng hoạt động kết thúc sớm nhất mà không làm giảm số lượng — nên greedy ít nhất tốt ngang tối ưu.
5. Phân tích: nhanh, nhưng phải chứng minh
| Khía cạnh | Greedy |
|---|---|
| Tốc độ | Thường O(n log n) (do phải sắp xếp) hoặc O(n) |
| Bộ nhớ | Thường O(1) ngoài đầu vào |
| Rủi ro | Có thể sai nếu thiếu tính lựa chọn tham lam |
Bẫy thường gặp:
- Tưởng nhanh là đúng. Greedy chạy ra số ngay, nhưng số đó chưa chắc tối ưu.
- Quên sắp xếp đúng tiêu chí. Activity selection sai nếu sắp theo giờ bắt đầu thay vì kết thúc.
- Không thử phản ví dụ. Trước khi tin greedy, hãy tìm một bộ nhỏ làm nó trật.
Khi greedy sai, thường ta phải dùng quy hoạch động (xét mọi lựa chọn, nhớ lại kết quả con) — đó là chủ đề tiếp theo của hành trình.
6. Mẫu nhận diện: "khi nào nghĩ tới greedy"
- Bài hỏi "ít nhất / nhiều nhất / tối đa / tối thiểu" và có vẻ chọn dần từng bước được.
- Có một tiêu chí sắp xếp tự nhiên (theo giờ kết thúc, theo giá trị/khối lượng, theo deadline).
- Sắp xong r ồi quét một lượt là ra. Nếu thấy phải thử nhiều phương án và nhớ lại → có thể không phải greedy mà là quy hoạch động.
7. 🎮 Trò chơi: Greedy đúng hay sai?
8. Quiz kiểm tra nhanh
9. Hoàn thành
…☑️ Tiếp theo: 3.5.2 — Quay lui (backtracking) — khi greedy thiển cận, ta thử rồi hoàn tác.