Thuật toán tham lam (Greedy Algorithm): ý tưởng, phản ví dụ, code C++, Python

Thuật toán tham lam là gì?

Khi đứng trước một bài toán đòi hỏi phải đưa ra một chuỗi quyết định để đạt kết quả lớn nhất hoặc nhỏ nhất, có hai hướng tiếp cận rất khác nhau:

• Hướng vét cạn / quay lui / quy hoạch động: Thử nhiều phương án, cân nhắc xem nếu bước này chọn A thì các bước sau được gì, nếu chọn B thì các bước sau được gì, rồi mới chốt phương án có tổng tốt nhất.
• Hướng tham lam (Greedy): Không nhìn xa, không thử đi thử lại. Tại mỗi bước, cứ thấy lựa chọn nào hợp lệ và tốt nhất ngay lúc đó thì lấy luôn, rồi bước tiếp sang phần còn lại mà không bao giờ hối hận.

Chính vì không phải quay lui hay lưu bảng trạng thái lớn, thuật toán tham lam thường chạy cực nhanh — phần lớn thời gian chỉ nằm ở bước sắp xếp mảng O(n log n) ban đầu, sau đó duyệt một vòng O(n) là xong.

Ví dụ kinh điển: Bài toán chọn công việc không chồng lấp (Activity Selection)

Đề bài: Trong ngày có n = 6 sự kiện, sự kiện thứ i bắt đầu lúc bat_dau[i] và kết thúc lúc ket_thuc[i]: [(2, 5), (1, 3), (8, 10), (3, 6), (5, 7), (6, 8)]. Bạn chỉ có thể tham gia một sự kiện tại một thời điểm (nếu sự kiện trước kết thúc ở mốc t thì bạn có thể tham gia ngay sự kiện tiếp theo bắt đầu từ mốc ≥ t). Hỏi bạn có thể tham gia tối đa bao nhiêu sự kiện?

Khi mới đọc đề, người học thường nghĩ ra 3 kiểu "tham lam" khác nhau:

1. Ý tưởng 1 — Chọn việc bắt đầu sớm nhất trước? Sai! Nếu có một việc bắt đầu rất sớm từ 0 nhưng kéo dài suốt đến 10 ([0, 10]), chọn nó xong là bạn mất sạch cả ngày.
2. Ý tưởng 2 — Chọn việc diễn ra ngắn nhất trước? Cũng sai! Giả sử có 3 việc [1, 5], [4, 6] và [5, 9]. Việc [4, 6] ngắn nhất (chỉ dài 2 đơn vị), nhưng nếu chọn [4, 6] thì nó vướng vào cả hai việc kia nên bạn chỉ làm được 1 việc, trong khi chọn [1, 5] và [5, 9] thì làm được 2 việc.
3. Ý tưởng 3 (Đúng) — Luôn chọn việc KẾT THÚC SỚM NHẤT trong các việc có thể làm: Việc kết thúc càng sớm thì quỹ thời gian trống còn lại phía sau cho các việc khác càng lớn. Không có lựa chọn nào khác có thể giải phóng bạn sớm hơn thế!

Hãy xem từng bước sau khi sắp xếp 6 công việc theo thời điểm kết thúc tăng dần:

Code chọn công việc bằng C++ và Python

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Chọn số lượng công việc không chồng lấp nhiều nhất
int chonCongViec(vector<pair<int, int>> ds) {
    // Sắp xếp theo thời điểm kết thúc (second) tăng dần
    sort(ds.begin(), ds.end(), [](const auto& a, const auto& b) {
        if (a.second != b.second) return a.second < b.second;
        return a.first < b.first;
    });

    int dem = 0, mocKetThuc = -1;
    for (const auto& [batDau, ketThuc] : ds) {
        if (batDau >= mocKetThuc) {  // không bị chồng lấp với việc vừa chọn
            dem++;
            mocKetThuc = ketThuc;
        }
    }
    return dem;
}

int main() {
    vector<pair<int, int>> ds = {{2, 5}, {1, 3}, {8, 10}, {3, 6}, {5, 7}, {6, 8}};
    cout << chonCongViec(ds) << "\n";  // 4
    return 0;
}

def chon_cong_viec(ds):
    """Chọn số lượng công việc không chồng lấp nhiều nhất."""
    # Sắp xếp theo thời điểm kết thúc (phần tử thứ hai) tăng dần
    ds_sap_xep = sorted(ds, key=lambda x: (x[1], x[0]))
    dem = 0
    moc_ket_thuc = -1
    for bat_dau, ket_thuc in ds_sap_xep:
        if bat_dau >= moc_ket_thuc:
            dem += 1
            moc_ket_thuc = ket_thuc
    return dem


ds = [(2, 5), (1, 3), (8, 10), (3, 6), (5, 7), (6, 8)]
print(chon_cong_viec(ds))  # 4

Độ phức tạp của thuật toán gồm O(n log n) cho bước sắp xếp cộng với O(n) cho vòng lặp duyệt qua danh sách, tổng cộng là O(n log n) thời gian và O(1) bộ nhớ phụ.

Khi nào tham lam BỊ SAI? Phản ví dụ bài toán đổi tiền

Sai lầm lớn nhất của người mới là áp dụng tham lam một cách cảm tính mà không kiểm tra. Hãy xét bài toán Đổi tiền ít tờ nhất:

• Với hệ thống tiền tệ thông thường như {1, 2, 5, 10, 20, 50}, cách tham lam (luôn lấy tờ có mệnh giá lớn nhất không vượt quá số tiền còn lại) luôn cho kết quả đúng.
• Nhưng giả sử một quốc gia phát hành 3 loại xu có mệnh giá {1, 3, 4} và bạn cần đổi số tiền S = 6:
  • Cách tham lam: Nhìn thấy tờ 4 lớn nhất ≤ 6, lấy ngay một tờ 4. Còn lại 6 - 4 = 2, buộc phải lấy thêm hai tờ 1. Tổng cộng tốn 3 tờ (4 + 1 + 1).
  • Cách tối ưu thật sự: Chỉ cần lấy hai tờ mệnh giá 3 (3 + 3 = 6), tốn 2 tờ!

Vì việc "tham" lấy tờ 4 ngay bước đầu đã đẩy phần dư vào thế bí phải dùng toàn tờ 1, bài toán đổi tiền với bộ mệnh giá bất kỳ không có tính chất lựa chọn tham lam mà bắt buộc phải giải bằng quy hoạch động (Dynamic Programming):

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Đổi tiền theo kiểu tham lam: luôn lấy tờ mệnh giá lớn nhất có thể
int doiTienThamLam(int S, const vector<int>& menhGia) {
    int soTo = 0;
    for (int i = (int)menhGia.size() - 1; i >= 0; --i) {
        soTo += S / menhGia[i];
        S %= menhGia[i];
    }
    return soTo;
}

// Đổi tiền tối ưu thật sự (quy hoạch động)
int doiTienToiUu(int S, const vector<int>& menhGia) {
    vector<int> dp(S + 1, 1e9);
    dp[0] = 0;
    for (int x = 1; x <= S; ++x) {
        for (int c : menhGia) {
            if (x >= c) dp[x] = min(dp[x], dp[x - c] + 1);
        }
    }
    return dp[S];
}

int main() {
    vector<int> menhGia = {1, 3, 4};
    cout << doiTienThamLam(6, menhGia) << " " << doiTienToiUu(6, menhGia) << "\n";  // 3 2
    return 0;
}

def doi_tien_tham_lam(s, menh_gia):
    so_to = 0
    for c in reversed(menh_gia):
        so_to += s // c
        s %= c
    return so_to


def doi_tien_toi_uu(s, menh_gia):
    dp = [10**9] * (s + 1)
    dp[0] = 0
    for x in range(1, s + 1):
        for c in menh_gia:
            if x >= c and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return dp[s]


menh_gia = [1, 3, 4]
print(doi_tien_tham_lam(6, menh_gia), doi_tien_toi_uu(6, menh_gia))  # 3 2

Làm sao phân biệt bài Tham lam và bài Quy hoạch động?

Lỗi hay gặp khi giải bài tham lam

Luyện ngay trên Big-O Coding

Áp dụng tư duy sắp xếp và lựa chọn tham lam vào các bài tập dưới đây trên hệ thống Big-O Coding:

Câu hỏi thường gặp

Nguồn tham khảo

• MIT 6.006: Greedy Algorithms
• CSES Competitive Programmer's Handbook — Chapter 6: Greedy Algorithms
• USACO Guide: Introduction to Greedy Algorithms