Wiki › Thuật toán › Tham lam (Greedy)

Tham lam (Greedy)

huunguyen Updated Tháng sáu 2, 2026

Thuật toán tham lam (greedy) xây dựng lời giải bằng cách tại mỗi bước chọn phương án tối ưu cục bộ (tốt nhất ngay lúc đó), không bao giờ quay lui xét lại. Khi bài toán có cấu trúc phù hợp, cách làm này cho ra tối ưu toàn cục với chi phí chỉ $O (N \log N)$ (thường là một lần sắp xếp) thay vì duyệt mọi tổ hợp $O (2^{N})$ như vét cạn hay $O (N^{2})$ như quy hoạch động.

Điểm mấu chốt: greedy rất dễ cài nhưng rất dễ sai. Một tiêu chí tham lam "có vẻ hợp lý" chưa chắc đúng. Bài viết này tập trung vào việc vì sao một chiến lược tham lam đúng, cách kiểm chứng nó, và những cái bẫy khiến bạn nhận Wrong Answer.

Ý tưởng / Trực giác

Một bài toán giải được bằng tham lam thường có hai tính chất:

Lựa chọn tham lam (greedy choice property): luôn tồn tại một lời giải tối ưu chứa lựa chọn tham lam ở bước đầu tiên. Nghĩa là quyết định "ăn chắc" bây giờ không làm mất cơ hội đạt tối ưu về sau.
Cấu trúc con tối ưu (optimal substructure): sau khi đã chọn xong bước đầu, phần còn lại lại là một bài toán cùng dạng nhỏ hơn, và lời giải tối ưu của nó ghép với lựa chọn ban đầu cho lời giải tối ưu toàn cục.

Lập luận tráo đổi (exchange argument)

Đây là kỹ thuật chứng minh tính đúng quan trọng nhất của greedy. Ý tưởng: giả sử có một lời giải tối ưu $O P T$ khác với lời giải tham lam $G$ . Ta chỉ ra rằng có thể tráo đổi một phần tử của $O P T$ để nó giống $G$ hơn mà không làm kết quả tệ đi. Lặp lại, ta biến $O P T$ thành $G$ mà chất lượng không giảm, suy ra $G$ cũng tối ưu.

Ví dụ kinh điển — chọn hoạt động (activity selection): cho các đoạn $[s_{i}, e_{i})$ , chọn nhiều đoạn nhất sao cho không đoạn nào chồng lên nhau. Tiêu chí đúng là luôn chọn đoạn kết thúc sớm nhất trong số các đoạn còn hợp lệ.

Vì sao? Gọi đoạn kết thúc sớm nhất là $a$ . Giả sử lời giải tối ưu không chứa $a$ mà bắt đầu bằng đoạn $b$ . Vì $a$ kết thúc không muộn hơn $b$ ( $e_{a} \leq e_{b}$ ), ta có thể thay $b$ bằng $a$ : $a$ chiếm ít "không gian thời gian" hơn nên không gây xung đột với các đoạn còn lại của lời giải tối ưu. Số đoạn không đổi, lời giải vẫn hợp lệ và vẫn tối ưu — nhưng giờ đã chứa $a$ . Đó chính là lựa chọn tham lam.

Trực giác: chọn đoạn kết thúc sớm nhất để chừa lại nhiều thời gian nhất cho các đoạn sau. Lưu ý sắp theo thời điểm kết thúc, không phải thời điểm bắt đầu hay độ dài — hai tiêu chí sau đều cho phản ví dụ.

Ví dụ chạy tay — Chọn hoạt động

Cho 5 đoạn (đánh số theo thứ tự nhập), tìm số đoạn không giao tối đa:

Đoạn:   A      B      C      D      E
[s,e):  [1,3)  [2,5)  [4,7)  [1,8)  [5,9)

Bước 1 — sắp theo thời điểm kết thúc $e$ tăng dần:

        A      B      C      E      D
[s,e):  [1,3)  [2,5)  [4,7)  [5,9)  [1,8)
   e =    3      5      7      9      8   (đã sắp: 3,5,7,8 -> E và D đổi chỗ)

Sắp đúng theo $e$ : A(3), B(5), C(7), D(8), E(9).

Bước 2 — duyệt, giữ biến last_end = thời điểm kết thúc của đoạn vừa chọn (khởi tạo $- \infty$ ). Chọn đoạn nếu $s \geq$ last_end.

trục thời gian:  1   2   3   4   5   6   7   8   9
A [1,3)        : ====]                              s=1 >= -inf  -> CHỌN, last_end=3   ✓
B [2,5)        :   =====]                            s=2 <  3     -> bỏ (giao A)
C [4,7)        :         ====]                       s=4 >= 3     -> CHỌN, last_end=7   ✓
D [1,8)        : ===========]                        s=1 <  7     -> bỏ (giao)
E [5,9)        :             ====]                   s=5 <  7     -> bỏ (giao C)

Kết quả: chọn được A và C, đáp số = 2. Quan sát: dù D dài và bao trùm nhiều, greedy bỏ qua vì nó "ngốn" cả trục thời gian, đúng như trực giác.

Cài đặt

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);   // {thoi_diem_ket_thuc, thoi_diem_bat_dau}
    for (int i = 0; i < n; i++) {
        int s, e;
        cin >> s >> e;
        a[i] = {e, s};            // đặt e lên trước để sort theo e
    }

    // Tiêu chí tham lam: sắp theo thời điểm KẾT THÚC tăng dần
    sort(a.begin(), a.end());

    int count = 0;
    long long last_end = LLONG_MIN;   // thời điểm kết thúc của đoạn đã chọn gần nhất
    for (auto [e, s] : a) {
        if (s >= last_end) {          // đoạn này bắt đầu sau khi đoạn trước kết thúc
            count++;
            last_end = e;             // cập nhật mốc
        }
    }
    cout << count << "\n";
    return 0;
}

Một ví dụ greedy khác dùng hàng đợi ưu tiên — mã Huffman (gộp hai tần số nhỏ nhất để cây có tổng độ dài đường đi nhỏ nhất):

priority_queue<long long, vector<long long>, greater<long long>> pq(freq.begin(), freq.end());
long long total_cost = 0;
while (pq.size() > 1) {
    long long x = pq.top(); pq.pop();   // hai phần tử nhỏ nhất hiện tại
    long long y = pq.top(); pq.pop();
    total_cost += x + y;                // chi phí gộp
    pq.push(x + y);                     // đẩy lại tổng để tiếp tục gộp
}
// total_cost là tổng độ dài có trọng số nhỏ nhất

Độ phức tạp

Thời gian: $O (N \log N)$ . Chi phí chi phối là một lần sắp xếp $O (N \log N)$ ; vòng duyệt chọn đoạn chỉ $O (N)$ vì mỗi đoạn xét đúng một lần. Với biến thể dùng hàng đợi ưu tiên (Huffman, chia phòng), mỗi phần tử vào/ra heap tốn $O (\log N)$ nên tổng vẫn $O (N \log N)$ .
Bộ nhớ: $O (N)$ để lưu mảng các đoạn (và heap nếu dùng). Không cần bảng phụ $O (N^{2})$ như quy hoạch động — đây chính là lợi thế lớn của greedy khi nó áp dụng được.

⚠️ Lỗi thường gặp

Chọn sai tiêu chí tham lam. Đây là lỗi nguy hiểm nhất vì code chạy ra kết quả "trông hợp lý" nhưng sai trên test khó. Với chọn hoạt động phải sắp theo thời điểm kết thúc; nếu sắp theo thời điểm bắt đầu hoặc độ dài sẽ sai. Luôn kiểm chứng bằng exchange argument hoặc tìm phản ví dụ nhỏ trước khi cài.
Tràn số (overflow). Khi cộng dồn chi phí (Huffman, tổng phần thưởng, tổng trọng số), tổng có thể vượt $2^{31}$ . Dùng long long cho biến tích lũy và cho last_end khi tọa độ tới $10^{9}$ . Triệu chứng: AC test nhỏ, WA test lớn.
Sai biên >= và >. "Hai đoạn chạm nhau tại một điểm" — có được xếp chung không? Đề bài bảo kết thúc trước khi cái sau bắt đầu (s >= last_end) khác với kết thúc không muộn hơn (s > last_end). Đọc kỹ "thực sự sớm hơn" để chọn đúng > hay >=; sai một dấu là WA.
Quên tham lam cần dữ liệu đã sắp xếp / có tính đơn điệu. Greedy thường yêu cầu một thứ tự cụ thể. Bỏ sort hoặc sắp sai khóa thì toàn bộ lập luận sụp đổ. Triệu chứng: kết quả phụ thuộc thứ tự nhập.
Áp greedy cho bài cần quy hoạch động. Bài toán cái túi 0/1 (knapsack) KHÔNG giải được bằng greedy theo tỉ lệ giá trị/khối lượng (chỉ bản phân số mới được). Khi không chứng minh được greedy choice property, hãy nghi ngờ và chuyển sang DP.
Trường hợp biên. Mảng rỗng ( $N = 0$ ), toàn bộ đoạn trùng nhau, hay giá trị âm (tọa độ, phần thưởng âm) thường lộ bug. Khởi tạo last_end = LLONG_MIN thay vì -1 để an toàn với tọa độ âm.

Biến thể / Mở rộng

Chia khoảng (interval partitioning): thay vì chọn ít đoạn, ta phân tất cả đoạn vào số "phòng/máy" ít nhất sao cho mỗi phòng không có hai đoạn giao nhau. Greedy: sắp theo thời điểm bắt đầu, dùng priority_queue lưu thời điểm kết thúc sớm nhất của các phòng đang mở; tái sử dụng phòng nếu được, ngược lại mở phòng mới. Số phòng = số đoạn chồng nhau cực đại.
Lập lịch theo hạn chót (deadline scheduling): cực tiểu/cực đại một đại lượng phụ thuộc thời điểm hoàn thành thường giải bằng exchange argument để suy ra khóa sắp xếp đúng (ví dụ sắp theo thời gian xử lý, hoặc theo hạn chót).
Liên hệ kỹ thuật khác: nhiều thuật toán đồ thị kinh điển là greedy — Kruskal/Prim (cây khung nhỏ nhất), Dijkstra (đường đi ngắn nhất). Khi greedy thất bại, thường phải dùng quy hoạch động.

Bài tập luyện

Bò qua đường (cowcross) — (Học việc) Sắp xếp đoạn rồi đếm đoạn "an toàn" không giao với đoạn nào khác; làm quen tư duy sắp xếp + xử lý giao nhau.
Công việc và Hạn chót (taskdeadline) — (Trung cấp) Lập lịch tối đa tổng phần thưởng $d_{i} - f_{i}$ ; bài chuẩn để luyện exchange argument tìm khóa sắp xếp đúng.
Phá Rừng (deforest) — (Trung cấp) Chặt nhiều cây nhất mà vẫn thỏa các ràng buộc đoạn; greedy kết hợp sắp xếp các yêu cầu theo biên phải.
Liên Hoan Phim II (moviefest2) — (Nâng cao) Mở rộng chọn hoạt động cho $k$ người xem song song; áp dụng đúng tiêu chí "kết thúc sớm nhất" trên nhiều dòng.
Bố trí Phòng Khách sạn (roomalloc) — (Nâng cao) Interval partitioning: dùng hàng đợi ưu tiên tìm số phòng tối thiểu và gán phòng cho từng khách.