Thuật toán tham lam (Greedy) đưa ra lựa chọn tối ưu cục bộ ở mỗi bước với hy vọng đạt được tối ưu toàn cục.
Khi nào dùng Greedy?
Greedy hoạt động đúng khi bài toán có tính chất tham lam (greedy choice property) — tức là lựa chọn cục bộ tốt nhất tại mỗi bước luôn dẫn đến giải pháp tối ưu toàn cục.
Không phải bài toán nào cũng dùng được Greedy. Khi không chắc, hãy thử chứng minh hoặc dùng DP.
Quy trình giải bài Greedy
- Xác định tiêu chí lựa chọn tham lam.
- Chứng minh (hoặc trực giác) rằng lựa chọn này là tối ưu.
- Cài đặt (thường đơn giản sau khi xác định được tiêu chí).
Ví dụ 1: Bài toán đổi tiền
Bài toán: Đổi số tiền bằng ít đồng xu nhất. Mệnh giá: 1, 5, 10, 25.
Greedy: Luôn chọn đồng xu có mệnh giá lớn nhất có thể.
int coins[] = {25, 10, 5, 1};
int n; cin >> n;
int count = 0;
for (int c : coins) {
count += n / c;
n %= c;
}
cout << count;
Lưu ý: Greedy đúng với mệnh giá {1, 5, 10, 25} nhưng sai với mệnh giá tùy ý (cần dùng DP).
Ví dụ 2: Bài toán xếp lịch (Activity Selection)
Bài toán: Chọn số lượng tối đa các công việc không chồng chéo nhau. Mỗi công việc có thời gian bắt đầu và kết thúc .
Greedy: Sắp xếp theo thời gian kết thúc, luôn chọn công việc kết thúc sớm nhất mà không chồng với công việc đã chọn.
vector<pair<int,int>> jobs; // {end, start}
sort(jobs.begin(), jobs.end());
int count = 0, last_end = -1;
for (auto [e, s] : jobs) {
if (s >= last_end) {
count++;
last_end = e;
}
}
cout << count;
Ví dụ 3: Huffman Coding (nén dữ liệu)
Xây dựng mã Huffman bằng cách luôn gộp hai phần tử có tần suất thấp nhất — dùng min-heap.
priority_queue<int, vector<int>, greater<int>> pq(freq.begin(), freq.end());
int total_cost = 0;
while (pq.size() > 1) {
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
total_cost += a + b;
pq.push(a + b);
}
cout << total_cost;
Các dạng bài Greedy thường gặp
| Dạng bài | Tiêu chí tham lam |
|---|---|
| Xếp lịch | Chọn theo thời gian kết thúc sớm nhất |
| Đổi tiền (mệnh giá đặc biệt) | Chọn mệnh giá lớn nhất trước |
| Nén dữ liệu (Huffman) | Gộp hai phần tử nhỏ nhất |
| Kruskal (MST) | Chọn cạnh nhỏ nhất không tạo chu trình |
| Fractional Knapsack | Chọn theo tỷ lệ giá trị/trọng lượng |
Bình luận