1. Thông tin chung

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

Thuật toán Tham lam (Greedy Algorithm) là một phương pháp thiết kế thuật toán giải quyết bài toán tối ưu bằng cách đưa ra lựa chọn tốt nhất ở thời điểm hiện tại tại mỗi bước thực hiện mà không quay lại kiểm tra hay xét đến toàn bộ không gian nghiệm trong tương lai.

Tư tưởng giải quyết:

Chia bài toán lớn thành một chuỗi các quyết định nối tiếp. Lần lượt chọn phương án "có lợi" nhất trước mắt cho từng bài toán con, với kỳ vọng rằng tổng các lựa chọn tối ưu cục bộ sẽ dẫn đến kết quả tối ưu toàn cụ

Đặc điểm của Thuật toán Tham lam:

1. Lựa chọn cục bộ (Local Choice): Tại mỗi bước, chọn giải pháp tốt nhất ngay lúc đó dựa trên một tiêu chí đánh giá nhất định.
2. Không quay đầu (No Backtracking): Đã quyết định chọn cái gì ở bước trước thì sẽ giữ nguyên, không bao giờ hay quay lại sửa sai.
3. Độ phức tạp cực kỳ tối ưu: Vì không cần duyệt lại hay lưu trữ trạng thái phức tạp, thuật toán Tham lam chạy rất nhanh, thường có độ phức tạp là ~O(N)~ hoặc ~O(N \log N)~ (thời gian chủ yếu dành cho việc sắp xếp dữ liệu ban đầu).

Ưu điểm và Thách thức:

• Ưu điểm: Cài đặt siêu nhanh, code ngắn gọn, chạy cực kỳ hiệu quả về mặt thời gian và bộ nhớ.
• Thách thức: Không phải bài toán nào dùng Tham lam cũng ra kết quả đúng! Nếu chọn sai tiêu chí tham lam, thuật toán sẽ cho ra đáp án sai. Do đó, thách thức lớn nhất không phải là gõ code, mà là chứng minh tính đúng đắn của chiến lược tham lam đó!

2. Bài toán khơi gợi

Để hiểu rõ hơn tư tưởng này, hãy xét một bài toán thực tế như sau:

Bài toán: Luyện Tập Thuật Toán Trong Kỳ Nghỉ Đông

Bạn Steph muốn nâng cao trình độ lập trình của mình trong kỳ nghỉ đông. Bạn ấy có tổng cộng ~X~ phút (~1 \le X \le 10^4~) dành cho việc học. Có ~N~ chủ đề thuật toán (~1 \le N \le 100~), chủ đề thứ ~i~ cần ~a_i~ phút (~1 \le a_i \le 100~) để học xong.

Yêu cầu: Hãy giúp Steph chọn các thuật toán để học sao cho số lượng thuật toán học được là NHIỀU NHẤT KHI CÓ THỂ trong khoảng thời gian ~X~ phút.

Ví dụ cụ thể:

• ~X = 15~ phút
• Số thuật toán ~N = 6~
• Thời gian học từng thuật toán ~a = \{4, 3, 8, 4, 7, 3\}~

3. Cách giải quyết

Tư duy bước qua các câu hỏi:

Bây giờ trả lời câu hỏi: Muốn học được nhiều bài nhất, chúng ta nên ưu tiên chọn bài tốn ít thời gian hay bài tốn nhiều thời gian trước?

Tất nhiên sẽ là bài tốn ít thời gian trước vì tổng thời gian có hạn (~X~ phút), nếu ta cứ "ôm" bài khó tốn 7 - 8 phút ngay từ đầu thì sẽ không còn quỹ thời gian cho các bài khác.

Các bước thực hiện (Step-by-Step):

• Bước 1 (Sắp xếp): Sắp xếp danh sách thời gian học các thuật toán theo thứ tự tăng dần.
  • Dãy ban đầu: {4, 3, 8, 4, 7, 3}
  • Dãy sau khi sắp xếp: {3, 3, 4, 4, 7, 8}
• Bước 2 (Tham lam chọn lựa): Duyệt lần lượt từng thuật toán từ đầu đến cuối danh sách đã sắp xếp. Cứ mỗi thuật toán, nếu tổng thời gian tích lũy chưa vượt quá ~X~, ta chọn học thuật toán đó.
  • Xét bài 1 (~a_1 = 3~): Tổng thời gian = ~3 \le 15~ ~\rightarrow~ Chọn (Số bài = 1)
  • Xét bài 2 (~a_2 = 3~): Tổng thời gian = ~3 + 3 = 6 \le 15~ ~\rightarrow~ Chọn (Số bài = 2)
  • Xét bài 3 (~a_3 = 4~): Tổng thời gian = ~6 + 4 = 10 \le 15~ ~\rightarrow~ Chọn (Số bài = 3)
  • Xét bài 4 (~a_4 = 4~): Tổng thời gian = ~10 + 4 = 14 \le 15~ ~\rightarrow~ Chọn (Số bài = 4)
  • Xét bài 5 (~a_5 = 7~): Tổng thời gian = ~14 + 7 = 21 > 15~ ~\rightarrow~ Dừng lại!
• Bước 3 (Kết luận): Steph học được tối đa 4 thuật toán với tổng thời gian là ~14~ phút.

Cài đặt chương trình (C++):

#include <bits/stdc++.h>

using namespace std;

int main() {
    // Tối ưu tốc độ vào ra dữ liệu trong C++
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int X, N;
    cin >> X >> N;

    vector<int> algorithms(N);
    for (int i = 0; i < N; i++) {
        cin >> algorithms[i];
    }

    // Bước 1: Sắp xếp thời gian học tăng dần
    sort(algorithms.begin(), algorithms.end());

    int minutes = 0; // Tổng thời gian đã sử dụng
    int count = 0;   // Số lượng thuật toán đã học

    // Bước 2: Duyệt tham lam chọn từ bài tốn ít thời gian nhất
    while (count < N && minutes + algorithms[count] <= X) {
        minutes += algorithms[count];
        count++;
    }

    // Bước 3: In ra kết quả
    cout << count << endl;

    return 0;
}

Đánh giá độ phức tạp:

• Thời gian (Time Complexity):
  • Sắp xếp mảng mất ~O(N \log N)~.
  • Vòng lặp duyệt mảng mất ~O(N)~.
  • Tổng độ phức tạp thời gian: ~O(N \log N)~. Với ~N \le 100~, chương trình chạy trong chưa tới 1 millisecond!
• Bộ nhớ (Space Complexity): ~O(N)~ để lưu mảng dữ liệu.

4. Các bài toán khác

Bài toán: Sắp Xếp Lịch Hoạt Động (Interval Scheduling Problem)

Đề bài: Có ~N~ sự kiện diễn ra. Sự kiện thứ ~i~ bắt đầu tại thời điểm ~S_i~ và kết thúc tại ~E_i~. Bạn Jason muốn tham gia nhiều sự kiện nhất có thể, nhưng tại một thời điểm bạn ấy chỉ có thể tham dự 1 sự kiện (không bị trùng thời gian).

Tiêu chí Tham lam nào là ĐÚNG?

Hãy cùng phân tích các ý tưởng tham lam mà học sinh thường nghĩ ra:

1. Ý tưởng 1 (SAI): Chọn sự kiện bắt đầu sớm nhất (Earliest Start Time).

   • Phản ví dụ: Giả sử sự kiện A kéo dài từ 8h00 đến 18h00, còn sự kiện B (9h00-10h00) và C (10h00-11h00). Nếu chọn A vì bắt đầu sớm nhất, ta chỉ tham dự được 1 sự kiện. Nhưng đáp án tối ưu là chọn B và C (2 sự kiện).

2. Ý tưởng 2 (ĐÚNG): Chọn sự kiện KẾT THÚC SỚM NHẤT (Earliest End Time)!

   • Tại sao lại đúng? Khi ta chọn sự kiện kết thúc càng sớm, khoảng thời gian còn lại phía sau càng rộng mở, giúp ta có thêm nhiều cơ hội để chọn các sự kiện tiếp theo.

Các bước thực hiện:

• Bước 1: Sắp xếp danh sách các sự kiện theo thời gian kết thúc (~E_i~) tăng dần.
• Bước 2: Duyệt qua từng sự kiện. Nếu thời gian bắt đầu của sự kiện đang xét ~S_i \ge~ thời gian kết thúc của sự kiện được chọn gần nhất, ta sẽ chọn thêm sự kiện này và cập nhật lại mốc kết thúc mới.

Cài đặt C++:

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    vector<pair<int, int>> events;

    for (int i = 0; i < N; i++) {
        int start, end;
        cin >> start >> end;
        events.push_back({end, start});
    }

    // Sắp xếp theo thời gian kết thúc tăng dần
    sort(events.begin(), events.end());

    int ans = 0;
    int currentEventEnd = -1;

    for (int i = 0; i < N; i++) {
        int end = events[i].first;
        int start = events[i].second;

        if (start >= currentEventEnd) {
            ans++;
            currentEventEnd = end;
        }
    }

    cout << ans << '\n';

    return 0;
}

Kiểm tra trước khi viết code:

1. Luôn phản biện: Trước khi viết code Tham lam trong kỳ thi, tự hỏi: "Liệu có ví dụ phản bác (counterexample) nào làm chiến lược này sai không?"
2. Thử nghiệm test thủ công: Tạo ra 2 - 3 test biên để kiểm tra tính đúng đắn của tiêu chí tham lam.