Skip to content

Bài 21: Greedy (Tham Lam) - Chọn Tốt Nhất Mỗi Bước!

Tác giả: FPTOJ Team
Nội dung tham khảo từ: VNOI Wiki - Thuật toán Tham lam

1. Chuyện gì đang xảy ra?

Bài toán: Đổi tiền

Bạn cần đổi 110 đồng bằng ít tờ tiền nhất. Các mệnh giá: 1, 5, 10, 50, 100.

Greedy: Mỗi bước chọn mệnh giá lớn nhất có thể!

  • 110 → lấy 1 tờ 100 → còn 10
  • 10 → lấy 1 tờ 10 → còn 0
  • Tổng: 2 tờ! ✅

2. Greedy là gì?

Greedy (Tham lam) = Mỗi bước chọn lựa chọn tốt nhất tại thời điểm đó, không quan tâm tương lai.

Khi nào Greedy đúng?

Greedy không phải lúc nào cũng đúng! Chỉ đúng khi bài toán có:

  1. Tính tham lam (Greedy Choice Property): Lựa chọn tốt nhất cục bộ → tốt nhất toàn cục
  2. Tính tối ưu con (Optimal Substructure): Bài toán lớn = bài toán con + lựa chọn

Ví dụ Greedy SAI

Đổi tiền với mệnh giá {1, 3, 4}, cần đổi 6:

  • Greedy: 4 + 1 + 1 = 3 tờ ← SAI!
  • Đúng: 3 + 3 = 2 tờ

→ Greedy không phải lúc nào cũng tối ưu! (Nhưng với hệ tiền tệ chuẩn {1, 5, 10, 50, 100} thì Greedy luôn đúng.)

Thử tương tác

3. Các bài toán Greedy kinh điển

3.1. Activity Selection (Chọn hoạt động)

Có N hoạt động, mỗi hoạt động có thời gian bắt đầu và kết thúc. Chọn nhiều hoạt động nhất sao cho không trùng thời gian.

Greedy: Sắp xếp các hoạt động theo thời gian kết thúc tăng dần. Lần lượt chọn hoạt động đầu tiên kết thúc sớm nhất, sau đó chọn hoạt động tiếp theo bắt đầu sau khi hoạt động trước đó kết thúc.

Minh họa trực quan: Trong ví dụ dưới đây, các hoạt động màu xanh lá được thuật toán chọn (không giao nhau và tối ưu số lượng), các hoạt động màu đỏ bị loại bỏ do bị trùng chéo thời gian:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// a, b ở đây là pair<start, end>; sort theo end tăng dần = chọn việc kết thúc sớm nhất trước
int maxActivities(vector<pair<int,int>>& activities) {
    // Bước 1: sort theo thời gian kết thúc (key ĐÚNG duy nhất cho bài này)
    sort(activities.begin(), activities.end(), 
         [](auto& a, auto& b) { return a.second < b.second; });

    int count = 0, lastEnd = -1; // count: số việc đã chọn; lastEnd: giờ kết thúc việc gần nhất
    for (auto& [start, end] : activities) {
        if (start >= lastEnd) { // bước kiểm tra: việc này bắt đầu sau khi việc trước xong?
            count++; // bước chọn: lấy việc kết thúc sớm nhất còn tương thích
            lastEnd = end; // bước cập nhật mốc thời gian
        }
        // ngược lại: bước loại — việc giao nhau với việc đã chọn nên bỏ qua
    }
    return count;
}

Trace từng bước chọn/loại (ví dụ rút gọn)

Lấy 5 hoạt động sau khi sort theo end: A1[1,4], A2[3,5], A4[5,7], A7[6,10], A10[12,16].

Bước Xét hoạt động start >= lastEnd? Hành động count lastEnd
0 — — khởi tạo 0 -1
1 A1[1,4] 1 >= -1 ✓ chọn A1 1 4
2 A2[3,5] 3 >= 4? Không loại (giao với A1) 1 4
3 A4[5,7] 5 >= 4 ✓ chọn A4 2 7
4 A7[6,10] 6 >= 7? Không loại (giao với A4) 2 7
5 A10[12,16] 12 >= 7 ✓ chọn A10 3 16

\(\Rightarrow\) chọn 3 hoạt động: A1, A4, A10. Mọi hoạt động bị loại đều giao với 1 hoạt động kết thúc sớm hơn đã chọn — đúng ý tưởng exchange argument ở §4.

3.2. Fractional Knapsack (Cái túi phân số)

Có N đồ vật, mỗi vật có trọng lượng w[i] và giá trị v[i]. Túi chứa được W. Được phép chia nhỏ đồ vật. Tìm giá trị lớn nhất.

Greedy: Sắp xếp theo tỷ lệ giá trị/trọng lượng giảm dần, lấy hết vật nào được trước.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
double fractionalKnapsack(vector<pair<double,double>>& items, double W) {
    // Bước 1: items[i] = {value, weight}; sort theo tỉ lệ value/weight giảm dần
    // → món "đáng giá từng kg" nhất đứng trước, lấy trước
    sort(items.begin(), items.end(), [](auto& a, auto& b) {
        return a.first / a.second > b.first / b.second;  // Tỷ lệ giảm dần
    });

    double totalValue = 0; // tổng giá trị đã lấy
    for (auto& [value, weight] : items) { // value = v[i], weight = w[i]
        if (W >= weight) { // bước lấy hết: túi còn đủ chỗ
            totalValue += value;
            W -= weight; // bước trừ sức chứa còn lại
        } else { // bước lấy lẻ: túi không đủ → xúc một phần tỉ lệ W/weight rồi dừng
            totalValue += value * (W / weight);
            break;
        }
    }
    return totalValue;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fractional_knapsack(items, W):
    # items = [(value, weight), ...]; sort theo value/weight giảm dần
    items.sort(key=lambda x: x[0] / x[1], reverse=True)  # bước 1: món đáng giá nhất trước
    total_value = 0  # tổng giá trị đã lấy
    for value, weight in items:
        if W >= weight:  # bước lấy hết: túi còn đủ chỗ
            total_value += value
            W -= weight  # bước trừ sức chứa
        else:  # bước lấy lẻ: xúc phần còn lại rồi dừng
            total_value += value * (W / weight)
            break
    return total_value

3.3. Job Sequencing (Xếp lịch công việc)

Mỗi công việc có deadline và lợi nhuận. Hoàn thành tối đa công việc trong deadline.

Greedy: Sắp xếp theo lợi nhuận giảm dần, chọn thời điểm trễ nhất trước deadline.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int jobSequencing(vector<pair<int,int>>& jobs) {
    // jobs[i] = {deadline, profit}: deadline = hạn chót, profit = tiền công
    // Bước 1: sort theo profit giảm dần → việc nhiều tiền xét trước
    sort(jobs.begin(), jobs.end(), [](auto& a, auto& b) {
        return a.second > b.second;  // Profit giảm dần
    });

    int maxDeadline = 0;
    for (auto& [d, p] : jobs)
        maxDeadline = max(maxDeadline, d); // bước tìm hạn chót xa nhất để cấp mảng slot

    vector<int> slot(maxDeadline + 1, -1);  // slot[t] = profit của job xếp tại giờ t (-1 = trống)
    int totalProfit = 0;

    for (auto& [deadline, profit] : jobs) {
        // Bước 2: tìm slot trống gần deadline nhất (xếp trễ nhất để nhường chỗ sớm cho job khác)
        for (int t = deadline; t >= 1; t--) {
            if (slot[t] == -1) { // bước chọn: giờ t còn trống
                slot[t] = profit; // bước xếp job vào giờ t
                totalProfit += profit;
                break;
            }
            // ngược lại: giờ t đã có job → lùi về t-1 thử tiếp
        }
    }
    return totalProfit;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def job_sequencing(jobs):
    # jobs[i] = (deadline, profit); sort profit giảm dần → việc nhiều tiền trước
    jobs.sort(key=lambda x: x[1], reverse=True)
    max_deadline = max(d for d, p in jobs)  # bước tìm hạn xa nhất
    slot = [-1] * (max_deadline + 1)  # slot[t] = profit xếp tại giờ t (-1 = trống)
    total_profit = 0
    for deadline, profit in jobs:
        # Bước 2: tìm giờ trống gần deadline nhất (xếp trễ nhất có thể)
        for t in range(deadline, 0, -1):
            if slot[t] == -1:  # bước chọn: giờ t trống
                slot[t] = profit
                total_profit += profit
                break
    return total_profit

3.4. Minimum Number of Platforms (Sân ga)

Cho giờ đến và giờ đi của N chuyến tàu. Tìm số sân ga tối thiểu.

Greedy: Sắp xếp cả giờ đến và giờ đi. Duyệt, tăng số sân ga khi tàu đến, giảm khi tàu đi.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int minPlatforms(vector<int>& arrival, vector<int>& departure) {
    sort(arrival.begin(), arrival.end());
    sort(departure.begin(), departure.end());

    int platforms = 0, maxPlatforms = 0;
    int i = 0, j = 0, n = arrival.size();

    while (i < n && j < n) {
        if (arrival[i] <= departure[j]) {
            platforms++;  // Tàu đến → cần thêm sân ga
            maxPlatforms = max(maxPlatforms, platforms);
            i++;
        } else {
            platforms--;  // Tàu đi → giải phóng sân ga
            j++;
        }
    }
    return maxPlatforms;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def min_platforms(arrival, departure):
    arrival.sort()
    departure.sort()
    platforms = max_platforms = 0
    i = j = 0
    n = len(arrival)
    while i < n and j < n:
        if arrival[i] <= departure[j]:
            platforms += 1
            max_platforms = max(max_platforms, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return max_platforms

4. Proof of Greedy - Chứng minh tính đúng đắn

Để chứng minh Greedy đúng, ta thường dùng 2 phương pháp:

Phương pháp 1: Exchange Argument (Hoán đổi)

  1. Giả sử có nghiệm tối ưu O khác với nghiệm Greedy G
  2. Chỉ ra rằng ta có thể hoán đổi O để biến nó thành G mà không giảm chất lượng
  3. Kết luận: G cũng tối ưu

Ví dụ: Activity Selection

  • Giả sử O chọn hoạt động kết thúc lúc t₁, nhưng G chọn hoạt động kết thúc sớm hơn lúc t₀ < t₁
  • Hoán đổi: thay hoạt động t₁ bằng t₀ trong O
  • Kết quả: O mới có cùng số hoạt động, nhưng hoạt động cuối kết thúc sớm hơn → có thể chọn thêm nhiều hơn
  • → G không tệ hơn O

Phương pháp 2: Greedy Stays Ahead (Greedy luôn dẫn trước)

  1. Chứng minh rằng sau mỗi bước, nghiệm Greedy không tệ hơn nghiệm tối ưu
  2. Dùng quy nạp: bước đầu tiên Greedy chọn tốt nhất → các bước sau cũng vậy

Ví dụ: Đổi tiền {1, 5, 10, 50, 100}

  • Chứng minh: nếu Greedy chọn tờ 100, thì mọi nghiệm tối ưu cũng phải dùng tờ 100
  • Vì nếu không dùng tờ 100, cần ít nhất 10 tờ 10 → nhiều hơn 1 tờ 100
  • → Greedy đúng

5. So sánh Greedy vs DP vs Quay lui

Greedy DP Quay lui
Lựa chọn Tốt nhất cục bộ Xét tất cả Thử tất cả
Độ phức tạp Thường O(N log N) O(N²) hoặc O(NK) O(2^N) hoặc O(N!)
Khi nào đúng? Khi có tính tham lam Luôn đúng Luôn đúng
Ví dụ Activity Selection Knapsack 0/1 N-Queens
Code Ngắn, đơn giản Trung bình Dài hơn

Khi nào dùng Greedy?

  • Bài toán có tính tham lam (chứng minh được)
  • Cần độ phức tạp tốt (O(N log N))
  • Không cần xét tất cả khả năng

Khi nào KHÔNG dùng Greedy?

  • Không chứng minh được tính tham lam
  • Cần nghiệm chính xác tối ưu → dùng DP
  • Bài toán có nhiều ràng buộc phức tạp → dùng DP hoặc Quay lui

6. Bài toán Greedy nâng cao

6.1. Huffman Coding (Nén dữ liệu)

Mỗi ký tự có tần suất xuất hiện. Mã hóa sao cho tổng độ dài mã là nhỏ nhất.

Greedy: Luôn gộp 2 node có tần suất nhỏ nhất.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int huffmanCoding(vector<int>& freq) {
    priority_queue<int, vector<int>, greater<int>> pq(freq.begin(), freq.end());

    int totalCost = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        totalCost += a + b;
        pq.push(a + b);
    }
    return totalCost;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import heapq

def huffman_coding(freq):
    heapq.heapify(freq)
    total_cost = 0
    while len(freq) > 1:
        a = heapq.heappop(freq)
        b = heapq.heappop(freq)
        total_cost += a + b
        heapq.heappush(freq, a + b)
    return total_cost

6.2. Interval Partitioning (Phân đoạn)

Cho N hoạt động, mỗi hoạt động có bắt đầu và kết thúc. Tìm số phòng tối thiểu.

Greedy: Sắp xếp theo bắt đầu, gán phòng trống đầu tiên.

7. Lưu ý — lỗi Greedy có code SAI/ĐÚNG

Lỗi 1: Sort sai key (Activity Selection sort theo start)

1
2
3
4
5
6
7
// SAI: sort theo giờ bắt đầu → chọn việc bắt đầu sớm nhưng kết thúc muộn, chặn nhiều việc khác
sort(activities.begin(), activities.end(),
     [](auto& a, auto& b) { return a.first < b.first; }); // sort theo start ✗

// ĐÚNG: sort theo giờ kết thúc → việc kết thúc sớm nhất trước, nhường chỗ nhiều nhất
sort(activities.begin(), activities.end(),
     [](auto& a, auto& b) { return a.second < b.second; }); // sort theo end ✓

Ví dụ: [1,10], [2,3], [4,5] — sort theo start chọn [1,10] được 1 việc; sort theo end chọn [2,3], [4,5] được 2 việc!

Lỗi 2: Greedy cho 0/1-Knapsack (không được chia nhỏ)

1
2
3
4
5
6
7
8
// SAI: lấy theo tỉ lệ value/weight như Fractional Knapsack — SAI với 0/1!
// Ví dụ: W = 50, items = {(60,10), (100,20), (120,30)}
// Greedy tỉ lệ: lấy (60,10) + (100,20) = 160, còn 20 không đủ cho (120,30) → 160
// Đúng (DP): lấy (100,20) + (120,30) = 220 ✓ → Greedy THIẾU 60!
double greedy01 = 160; // SAI

// ĐÚNG: 0/1-Knapsack (mỗi món lấy hoặc không) phải dùng DP, không dùng Greedy
// dp[w] = giá trị lớn nhất với sức chứa w → đáp án 220

Quy tắc nhớ:

Bài toán Được chia nhỏ? Thuật toán đúng
Fractional Knapsack Có (xúc một phần) Greedy theo tỉ lệ ✓
0/1-Knapsack Không (lấy hoặc bỏ) DP, không Greedy ✗
  • Greedy không phải lúc nào cũng đúng! Phải chứng minh tính đúng đắn (xem §4)
  • Nếu không chắc Greedy đúng → dùng DP
  • Greedy thường kết hợp với sắp xếp trước khi chọn
  • Proof of Greedy là kỹ năng quan trọng trong thi đấu

8. Bài tập luyện tập

Bài Nền tảng Độ khó Chủ đề
grd-coin-change FPTOJ ⭐ Đổi tiền tham lam
grd-activities FPTOJ ⭐⭐ Activity Selection
grd-assign-cookies FPTOJ ⭐⭐ Phân bánh quy
grd-lemonade FPTOJ ⭐⭐ Trả tiền thừa
grd-max-subarray FPTOJ ⭐⭐ Kadane / Tổng lớn nhất
grd-knapsack-frac FPTOJ ⭐⭐ Fractional Knapsack
grd-job-deadline FPTOJ ⭐⭐⭐ Job Sequencing
grd-platforms FPTOJ ⭐⭐⭐ Sân ga tối thiểu
grd-merge-sticks FPTOJ ⭐⭐⭐ Gộp que (Huffman)
grd-max-units FPTOJ ⭐⭐⭐ Xe tải chở hàng tối ưu
grd-boats FPTOJ ⭐⭐⭐ Cứu hộ thuyền (2 con trỏ)
grd-candy FPTOJ ⭐⭐⭐ Phát kẹo (Candy)
grd-huffman FPTOJ ⭐⭐⭐⭐ Nén Huffman
grd-interval-part FPTOJ ⭐⭐⭐⭐ Interval Partitioning
grd-remove-digits FPTOJ ⭐⭐⭐⭐ Xóa chữ số (Stack)
grd-gas-station FPTOJ ⭐⭐⭐⭐ Trạm xăng vòng tròn
grd-two-city FPTOJ ⭐⭐⭐⭐ Chi phí hai thành phố
grd-min-arrows FPTOJ ⭐⭐⭐⭐ Bong bóng và mũi tên
grd-partition-labels FPTOJ ⭐⭐⭐⭐ Phân vùng chuỗi
grd-wiggle FPTOJ ⭐⭐⭐⭐ Dãy zigzag dài nhất

Bài viết liên quan

Tài liệu tham khảo

Bài tiếp theo: Hình học cơ bản →

💬 Bình luận