Bài 17.1. Nguyên lý thuật toán tham lam

Chào mừng trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Sau khi đã khám phá những viên gạch nền tảng, hôm nay chúng ta sẽ bắt đầu đi sâu vào các phương pháp thiết kế giải thuật mạnh mẽ. Và điểm dừng chân đầu tiên của chúng ta là một nguyên lý nghe có vẻ rất... đời thường: Nguyên lý Thuật toán Tham Lam (Greedy Algorithm Principle).

Nghe tên "tham lam" có vẻ tiêu cực, nhưng trong thế giới giải thuật, đó lại là một tư duy để giải quyết các bài toán tối ưu hóa. Hãy cùng khám phá xem "tham lam" ở đây có nghĩa là gì và làm thế nào để sử dụng nó một cách hiệu quả!

Tham Lam Trong Giải Thuật: Một Tư Duy Đơn Giản Nhưng Mạnh Mẽ

Bạn đã bao giờ đứng trước một loạt các lựa chọn và theo bản năng chọn ngay phương án có vẻ tốt nhất tại thời điểm đó mà không suy nghĩ quá xa về tương lai chưa? Đó chính là bản chất của sự "tham lam" mà chúng ta đang nói tới.

Trong bối cảnh giải thuật, Nguyên lý Thuật toán Tham Lam đề cập đến việc đưa ra lựa chọn tối ưu cục bộ (locally optimal choice) tại mỗi bước với hy vọng rằng chuỗi các lựa chọn tối ưu cục bộ này sẽ dẫn đến một giải pháp tối ưu toàn cục (globally optimal solution) cho toàn bộ bài toán.

Định nghĩa cốt lõi: Tại mỗi bước xử lý của thuật toán, chúng ta luôn luôn đưa ra quyết định có vẻ tốt nhất ngay lúc đó, không cần xem xét các bước tiếp theo hoặc các lựa chọn khác có thể tốt hơn trong dài hạn.

Nguyên lý này có vẻ đơn giản và trực giác, đúng không? Nó thường dẫn đến các giải thuật dễ cài đặt và có hiệu suất cao hơn so với các phương pháp khác (như Quy hoạch động hay vét cạn) nếu nó hoạt động. Tuy nhiên, mặt trái là nguyên lý tham lam không phải lúc nào cũng cho ra giải pháp tối ưu toàn cục. Nó chỉ đúng cho một lớp bài toán nhất định.

Khi Nào Nguyên Lý Tham Lam Có Sức Mạnh?

Để một bài toán tối ưu hóa có thể được giải quyết bằng thuật toán tham lam và đảm bảo tính tối ưu, nó thường phải thỏa mãn hai tính chất sau:

Tính chất Lựa chọn Tham lam (Greedy Choice Property): Đây là tính chất quan trọng nhất. Nó nói rằng một giải pháp tối ưu toàn cục cho bài toán có thể đạt được bằng cách thực hiện một chuỗi các lựa chọn tối ưu cục bộ. Cụ thể hơn, tại mỗi bước, có ít nhất một lựa chọn tối ưu cục bộ là nhất quán với một giải pháp tối ưu toàn cục nào đó. Nói cách khác, việc đưa ra lựa chọn "tốt nhất ngay bây giờ" không làm mất khả năng đạt được giải pháp tối ưu cuối cùng.
Cấu trúc Tối ưu con (Optimal Substructure): Tính chất này tương tự như trong Quy hoạch động. Nó nói rằng một giải pháp tối ưu cho bài toán lớn chứa đựng các giải pháp tối ưu cho các bài toán con của nó. Nếu sau khi thực hiện lựa chọn tham lam, bài toán còn lại (bài toán con) cũng có cấu trúc tương tự và có thể được giải quyết tối ưu, thì nguyên lý tham lam có tiềm năng hoạt động.

Khi cả hai tính chất này cùng tồn tại, chúng ta có thể tự tin (sau khi chứng minh toán học) rằng thuật toán tham lam sẽ cho ra giải pháp tối ưu. Ngược lại, nếu thiếu một trong hai hoặc cả hai, thuật toán tham lam có thể không cho ra kết quả tối ưu, mặc dù nó vẫn có thể cho ra một giải pháp gần tối ưu trong một số trường hợp.

Ví Dụ Minh Họa: Ánh Sáng Và Bóng Tối Của Sự Tham Lam

Cách tốt nhất để hiểu nguyên lý tham lam là thông qua các ví dụ. Chúng ta sẽ xem xét cả những bài toán mà thuật toán tham lam hoạt động tốt và cả những bài toán mà nó thất bại.

Ví Dụ 1: Bài toán Đổi Tiền (Coin Change) - Mặt tối của sự tham lam (đôi khi)

Mô tả bài toán: Cho một số tiền cần đổi amount và một tập hợp các loại mệnh giá tiền xu coins. Mục tiêu là tìm cách đổi tiền sao cho sử dụng ít số lượng xu nhất.

Tư duy Tham lam: Tại mỗi bước, chọn loại tiền xu có mệnh giá lớn nhất nhỏ hơn hoặc bằng số tiền còn lại cần đổi. Lặp lại cho đến khi số tiền cần đổi bằng 0.

Hãy xem xét trường hợp với các mệnh giá tiền xu phổ biến ở nhiều quốc gia, ví dụ: {1, 5, 10, 25} cents.

Cần đổi 34 cents.
- Bước 1: Tiền còn 34. Xu lớn nhất <= 34 là 25. Chọn 25. Còn lại 34 - 25 = 9 cents. (Sử dụng 1 xu 25)
- Bước 2: Tiền còn 9. Xu lớn nhất <= 9 là 5. Chọn 5. Còn lại 9 - 5 = 4 cents. (Sử dụng 1 xu 5)
- Bước 3: Tiền còn 4. Xu lớn nhất <= 4 là 1. Chọn 1. Còn lại 4 - 1 = 3 cents. (Sử dụng 1 xu 1)
- Bước 4: Tiền còn 3. Xu lớn nhất <= 3 là 1. Chọn 1. Còn lại 3 - 1 = 2 cents. (Sử dụng 1 xu 1)
- Bước 5: Tiền còn 2. Xu lớn nhất <= 2 là 1. Chọn 1. Còn lại 2 - 1 = 1 cent. (Sử dụng 1 xu 1)
- Bước 6: Tiền còn 1. Xu lớn nhất <= 1 là 1. Chọn 1. Còn lại 1 - 1 = 0 cents. (Sử dụng 1 xu 1)

Tổng số xu: 1 (xu 25) + 1 (xu 5) + 4 (xu 1) = 6 xu. Đây là giải pháp tối ưu cho trường hợp này.

Code C++ minh họa (cho trường hợp các mệnh giá chuẩn):

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

// Hàm thực hiện đổi tiền theo nguyên lý tham lam
// coins: vector chứa các mệnh giá tiền xu
// amount: số tiền cần đổi
// Trả về một map chứa số lượng của mỗi loại xu được sử dụng
map<int, int> greedyCoinChange(vector<int>& coins, int amount) {
    // Sắp xếp các mệnh giá theo thứ tự giảm dần để luôn chọn đồng lớn nhất
    sort(coins.rbegin(), coins.rend());

    map<int, int> result; // Lưu kết quả: mệnh giá -> số lượng
    int remaining_amount = amount;

    // Duyệt qua từng loại mệnh giá
    for (int coin : coins) {
        // Nếu mệnh giá hiện tại nhỏ hơn hoặc bằng số tiền còn lại
        while (remaining_amount >= coin) {
            // Chọn đồng xu này
            result[coin]++; // Tăng số lượng xu của mệnh giá này
            remaining_amount -= coin; // Giảm số tiền còn lại
        }
        // Nếu số tiền còn lại đã về 0, dừng lại
        if (remaining_amount == 0) {
            break;
        }
    }

    // Kiểm tra xem có đổi hết tiền không (trường hợp không đổi hết có thể xảy ra với tập mệnh giá bất kỳ)
    if (remaining_amount > 0) {
        cerr << "Can't make exact change for " << amount << " with given coins using greedy approach." << endl;
        // Trong bài toán đổi tiền chuẩn, nếu 1 là mệnh giá nhỏ nhất, điều này sẽ không xảy ra
        // Nhưng với tập mệnh giá tùy ý, thuật toán tham lam có thể không đổi hết được.
        // Để đơn giản, ví dụ này giả định có mệnh giá 1 hoặc các mệnh giá cho phép đổi hết.
    }


    return result;
}

int main() {
    vector<int> standard_coins = {1, 5, 10, 25}; // Các mệnh giá chuẩn
    int amount1 = 34;

    cout << "Doi tien " << amount1 << " cents voi menh gia {1, 5, 10, 25}:" << endl;
    map<int, int> change1 = greedyCoinChange(standard_coins, amount1);
    for (auto const& [coin, count] : change1) {
        cout << "- Menh gia " << coin << ": " << count << " dong" << endl;
    }
    cout << endl;

    // --- Bây giờ, hãy xem mặt tối của sự tham lam ---
    vector<int> weird_coins = {1, 5, 10, 25, 40}; // Một tập mệnh giá "kỳ lạ"
    int amount2 = 40;

    cout << "Doi tien " << amount2 << " cents voi menh gia {1, 5, 10, 25, 40} (Tham lam):" << endl;
    map<int, int> change2 = greedyCoinChange(weird_coins, amount2);
    for (auto const& [coin, count] : change2) {
         cout << "- Menh gia " << coin << ": " << count << " dong" << endl;
    }
    // Phân tích kết quả cho trường hợp này

    cout << "\n----------------------" << endl;
    cout << "Phan tich bai toan doi tien:" << endl;
    cout << "Voi menh gia chuan {1, 5, 10, 25}, thuat toan tham lam HOAT DONG TOT." << endl;
    cout << "Voi menh gia {1, 5, 10, 25, 40} can doi 40 cents:" << endl;
    cout << "  - Thuat toan tham lam cho ra: 1 dong 25, 1 dong 10, 1 dong 5 (Tong cong 3 dong)." << endl;
    cout << "  - Giai phap toi uu la: 1 dong 40 (Tong cong 1 dong)." << endl;
    cout << "=> Thuat toan tham lam THAT BAI o day!" << endl;
    cout << "Ly do that bai: Tinh chat LUA CHON THAM LAM khong duoc thoa man cho tap menh gia nay." << endl;
    cout << "Viec chon dong xu lon nhat (25) khong dan den giai phap toi uu toan cuc (su dung dong 40)." << endl;

    return 0;
}

Giải thích Code:

Chúng ta sử dụng vector<int> coins để lưu các mệnh giá.
sort(coins.rbegin(), coins.rend()); dùng để sắp xếp các mệnh giá theo thứ tự giảm dần. Điều này là cần thiết để nguyên lý tham lam hoạt động: luôn ưu tiên đồng xu có giá trị lớn nhất có thể. rbegin() và rend() cung cấp iterator ngược để sắp xếp giảm dần.
map<int, int> result; dùng để lưu trữ số lượng của mỗi loại xu được chọn. map rất tiện lợi cho việc này vì nó lưu trữ cặp key-value (mệnh giá -> số lượng).
Vòng lặp for (int coin : coins) duyệt qua các mệnh giá từ lớn nhất đến nhỏ nhất.
Vòng lặp while (remaining_amount >= coin) là bước "tham lam". Chừng nào số tiền còn lại lớn hơn hoặc bằng mệnh giá hiện tại, chúng ta cứ lấy đồng xu đó.
result[coin]++; tăng số đếm cho mệnh giá coin.
remaining_amount -= coin; cập nhật số tiền còn lại.
Đoạn code sau main minh họa rõ ràng trường hợp thất bại với tập mệnh giá {1, 5, 10, 25, 40} khi cần đổi 40 cents. Thuật toán tham lam chọn 25 + 10 + 5 (3 xu), trong khi giải pháp tối ưu là 40 (1 xu). Điều này chứng minh rằng Tính chất Lựa chọn Tham lam không đúng cho mọi tập mệnh giá.

Ví Dụ 2: Bài toán Chọn Hoạt Động (Activity Selection) - Nơi Tham Lam Tỏa Sáng

Mô tả bài toán: Cho một tập hợp n hoạt động, mỗi hoạt động có thời gian bắt đầu s_i và thời gian kết thúc f_i. Giả sử bạn chỉ có thể thực hiện một hoạt động tại một thời điểm. Mục tiêu là chọn một tập hợp con các hoạt động tương thích (không chồng lấn về thời gian) sao cho số lượng hoạt động được chọn là lớn nhất.

Tư duy Tham lam: Sắp xếp các hoạt động theo thời gian kết thúc tăng dần. Chọn hoạt động đầu tiên (kết thúc sớm nhất). Sau đó, duyệt qua các hoạt động còn lại và chọn hoạt động đầu tiên mà thời gian bắt đầu của nó lớn hơn hoặc bằng thời gian kết thúc của hoạt động đã chọn trước đó. Lặp lại cho đến hết danh sách hoạt động.

Vì sao tư duy này lại hoạt động ở đây? Việc chọn hoạt động kết thúc sớm nhất ở mỗi bước là một lựa chọn tham lam. Trực giác cho thấy rằng hoạt động kết thúc sớm nhất sẽ chừa lại nhiều thời gian nhất cho các hoạt động tiếp theo, từ đó tối đa hóa số lượng hoạt động có thể thực hiện. Hóa ra, trực giác này là đúng và nó thỏa mãn Tính chất Lựa chọn Tham lam cho bài toán này.

Code C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>

// Cấu trúc để lưu thông tin về một hoạt động
struct Activity {
    int start;
    int finish;
};

// Hàm so sánh dùng để sắp xếp các hoạt động theo thời gian kết thúc
bool compareActivities(const Activity& a, const Activity& b) {
    return a.finish < b.finish;
}

// Hàm thực hiện chọn hoạt động theo nguyên lý tham lam
// activities: vector chứa các hoạt động
// Trả về vector chứa các hoạt động đã được chọn
vector<Activity> greedyActivitySelection(vector<Activity>& activities) {
    // Bước 1: Sắp xếp các hoạt động theo thời gian kết thúc tăng dần
    sort(activities.begin(), activities.end(), compareActivities);

    vector<Activity> selected_activities; // Danh sách các hoạt động được chọn

    // Bước 2: Chọn hoạt động đầu tiên (hoạt động kết thúc sớm nhất)
    if (!activities.empty()) {
        selected_activities.push_back(activities[0]);
    }

    // Bước 3: Duyệt qua các hoạt động còn lại và áp dụng nguyên lý tham lam
    // Giữ chỉ mục của hoạt động được chọn gần nhất
    int last_selected_idx = 0;

    for (int i = 1; i < activities.size(); ++i) {
        // Nếu thời gian bắt đầu của hoạt động hiện tại >= thời gian kết thúc
        // của hoạt động được chọn gần nhất
        if (activities[i].start >= activities[last_selected_idx].finish) {
            // Thì chọn hoạt động hiện tại
            selected_activities.push_back(activities[i]);
            // Cập nhật chỉ mục của hoạt động được chọn gần nhất
            last_selected_idx = i;
        }
    }

    return selected_activities;
}

int main() {
    vector<Activity> activities = {
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
    }; // (start, finish)

    cout << "Danh sach hoat dong ban dau:" << endl;
    for (const auto& act : activities) {
        cout << "(" << act.start << ", " << act.finish << ") ";
    }
    cout << endl;

    vector<Activity> selected = greedyActivitySelection(activities);

    cout << "\nCac hoat dong duoc chon (toi uu theo nguyen ly tham lam):" << endl;
    for (const auto& act : selected) {
        cout << "(" << act.start << ", " << act.finish << ") ";
    }
    cout << "\nTong so hoat dong duoc chon: " << selected.size() << endl;
    cout << "\n----------------------" << endl;
    cout << "Phan tich bai toan chon hoat dong:" << endl;
    cout << "Nguyen ly tham lam (sap xep theo thoi gian ket thuc va chon cai dau tien tu sau do) HOAT DONG TOT o day." << endl;
    cout << "Viec chon hoat dong ket thuc som nhat luon luon la mot phan cua mot giai phap toi uu." << endl;
    cout << "No thoa man Tinh chat LUA CHON THAM LAM va Cau truc TOI UU CON." << endl;


    return 0;
}

Giải thích Code:

struct Activity định nghĩa cấu trúc dữ liệu cho mỗi hoạt động.
compareActivities là hàm so sánh custom để sort có thể sắp xếp vector các Activity dựa trên thuộc tính finish.
Trong greedyActivitySelection:
- Đầu tiên, sort được gọi để sắp xếp vector activities theo thời gian kết thúc tăng dần. Đây là bước chuẩn bị quan trọng nhất cho nguyên lý tham lam trong bài toán này.
- Kiểm tra nếu danh sách không rỗng, thêm hoạt động đầu tiên (kết thúc sớm nhất) vào selected_activities.
- Duyệt từ hoạt động thứ hai (i = 1).
- activities[i].start >= activities[last_selected_idx].finish là điều kiện "tham lam". Nó kiểm tra xem hoạt động hiện tại có bắt đầu sau hoặc đúng lúc hoạt động được chọn gần nhất kết thúc hay không.
- Nếu điều kiện đúng, hoạt động hiện tại tương thích, nên chúng ta chọn nó (thêm vào selected_activities) và cập nhật last_selected_idx để tham chiếu đến hoạt động vừa chọn.
Kết quả là vector selected_activities chứa tập hợp con lớn nhất các hoạt động không chồng lấn.

Ví Dụ 3: Bài toán Cái Túi Phân Số (Fractional Knapsack) - Một Lần Nữa, Tham Lam Thành Công

Mô tả bài toán: Cho một cái túi có sức chứa tối đa W và một tập hợp n vật phẩm. Mỗi vật phẩm i có trọng lượng w_i và giá trị v_i. Bạn có thể lấy một phần của vật phẩm (do đó gọi là "phân số"). Mục tiêu là chọn các vật phẩm (hoặc một phần của chúng) để đưa vào túi sao cho tổng giá trị thu được là lớn nhất, mà tổng trọng lượng không vượt quá W.

Tư duy Tham lam: Tính giá trị trên mỗi đơn vị trọng lượng (v_i / w_i) cho mỗi vật phẩm. Sắp xếp các vật phẩm theo tỷ lệ này giảm dần. Sau đó, lần lượt đưa vật phẩm vào túi theo thứ tự đã sắp xếp: nếu vật phẩm còn đủ chỗ trong túi, lấy toàn bộ; nếu không, lấy một phần của nó cho đến khi túi đầy.

Vì sao tư duy này lại hoạt động ở đây? Đối với bài toán cái túi phân số, việc ưu tiên các vật phẩm mang lại nhiều giá trị nhất cho mỗi đơn vị trọng lượng là chiến lược tối ưu. Bạn luôn muốn "lấp đầy" túi bằng những thứ "đậm đặc" giá trị nhất trước. Điều này thỏa mãn Tính chất Lựa chọn Tham lam. Khác với bài toán cái túi 0/1 (không được lấy một phần), ở đây, việc lấy một phần không làm hỏng cấu trúc bài toán con còn lại, giúp thỏa mãn Cấu trúc Tối ưu con.

Code C++ minh họa:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> // Để định dạng output double

// Cấu trúc để lưu thông tin về một vật phẩm
struct Item {
    int value;
    int weight;
    double value_per_weight; // Giá trị trên mỗi đơn vị trọng lượng
};

// Hàm so sánh dùng để sắp xếp các vật phẩm theo value_per_weight giảm dần
bool compareItems(const Item& a, const Item& b) {
    return a.value_per_weight > b.value_per_weight; // Sắp xếp giảm dần
}

// Hàm thực hiện bài toán cái túi phân số theo nguyên lý tham lam
// W: Sức chứa tối đa của túi
// items: vector chứa các vật phẩm
// Trả về tổng giá trị lớn nhất có thể đạt được
double greedyFractionalKnapsack(int W, vector<Item>& items) {
    // Bước 1: Tính giá trị trên mỗi đơn vị trọng lượng cho mỗi vật phẩm
    for (auto& item : items) {
        item.value_per_weight = static_cast<double>(item.value) / item.weight;
    }

    // Bước 2: Sắp xếp các vật phẩm theo value_per_weight giảm dần
    sort(items.begin(), items.end(), compareItems);

    double total_value = 0.0; // Tổng giá trị thu được
    int current_weight = 0;   // Trọng lượng hiện tại trong túi

    cout << "\n--- Qua trinh dua vat pham vao tui ---" << endl;

    // Bước 3: Lần lượt đưa vật phẩm vào túi theo thứ tự đã sắp xếp
    for (const auto& item : items) {
        // Tính toán xem có thể lấy bao nhiêu trọng lượng của vật phẩm này
        int remaining_capacity = W - current_weight;

        // Nếu có thể lấy toàn bộ vật phẩm
        if (item.weight <= remaining_capacity) {
            current_weight += item.weight;
            total_value += item.value;
            cout << "Lay toan bo vat pham (V=" << item.value << ", W=" << item.weight << ", V/W=" << item.value_per_weight << "). Tui hien tai: W=" << current_weight << ", V=" << total_value << endl;
        }
        // Nếu chỉ có thể lấy một phần
        else {
            double fraction = static_cast<double>(remaining_capacity) / item.weight;
            current_weight += remaining_capacity; // Tui day
            total_value += item.value * fraction;
            cout << "Lay mot phan (" << fixed << setprecision(2) << fraction * 100 << "%) cua vat pham (V=" << item.value << ", W=" << item.weight << ", V/W=" << item.value_per_weight << "). Tui hien tai: W=" << current_weight << ", V=" << total_value << endl;
            break; // Tui da day, dung lai
        }

        // Nếu túi đã đầy (trọng lượng hiện tại bằng sức chứa tối đa)
        if (current_weight == W) {
             cout << "Tui da day." << endl;
            break;
        }
    }

    return total_value;
}

int main() {
    int W = 50; // Sức chứa của túi
    vector<Item> items = {
        {60, 10, 0}, // Gia tri, Trong luong, Ty le (se tinh sau)
        {100, 20, 0},
        {120, 30, 0}
    };

    cout << "Bai toan Cai tui Phan so voi suc chua W = " << W << endl;
    cout << "Cac vat pham: (Gia tri, Trong luong)" << endl;
    for(const auto& item : items) {
        cout << "(" << item.value << ", " << item.weight << ") ";
    }
    cout << endl;

    double max_value = greedyFractionalKnapsack(W, items);

    cout << "\n----------------------" << endl;
    cout << "Tong gia tri toi da co the dat duoc: " << fixed << setprecision(2) << max_value << endl;

    cout << "\n----------------------" << endl;
    cout << "Phan tich bai toan cai tui phan so:" << endl;
    cout << "Nguyen ly tham lam (sap xep theo ty le gia tri/trong luong va lay dan) HOAT DONG TOT o day." << endl;
    cout << "Viec luon chon vat pham co ty le V/W cao nhat la lua chon toi uu cuc bo va dan den toi uu toan cuc." << cout;
    cout << "No thoa man Tinh chat LUA CHON THAM LAM va Cau truc TOI UU CON." << endl;


    return 0;
}

Giải thích Code:

struct Item lưu trữ giá trị, trọng lượng và tỷ lệ giá trị/trọng lượng của mỗi vật phẩm.
compareItems là hàm so sánh để sắp xếp các Item theo value_per_weight giảm dần.
Trong greedyFractionalKnapsack:
- Vòng lặp đầu tiên tính value_per_weight cho tất cả các vật phẩm.
- sort sắp xếp vector items dựa trên tỷ lệ này giảm dần.
- Duyệt qua các vật phẩm đã sắp xếp.
- Tính toán lượng trống còn lại trong túi (remaining_capacity).
- Nếu trọng lượng vật phẩm hiện tại (item.weight) nhỏ hơn hoặc bằng lượng trống, lấy toàn bộ vật phẩm, cập nhật trọng lượng và giá trị.
- Nếu trọng lượng vật phẩm lớn hơn lượng trống, tính phần trăm (fraction) có thể lấy để lấp đầy túi, lấy phần đó, cập nhật trọng lượng (túi đầy) và giá trị, rồi dừng lại (break) vì túi đã đầy.
- Sử dụng fixed và setprecision để hiển thị giá trị double với số lượng chữ số thập phân cố định cho dễ đọc.
Kết quả là tổng giá trị lớn nhất có thể thu được.

Ưu Điểm và Nhược Điểm

Ưu điểm:
- Đơn giản: Thường rất dễ hiểu và cài đặt.
- Hiệu quả: Nếu áp dụng được, thuật toán tham lam thường chạy nhanh hơn đáng kể so với các phương pháp khác như quy hoạch động hoặc vét cạn. Độ phức tạp thường bị chi phối bởi bước sắp xếp (nếu có), thường là O(N log N), hoặc chỉ O(N) nếu không cần sắp xếp.
Nhược điểm:
- Không luôn tối ưu: Đây là nhược điểm lớn nhất. Nó chỉ đảm bảo tính tối ưu cho một lớp bài toán nhất định.
- Khó chứng minh: Việc chứng minh rằng thuật toán tham lam thực sự cho ra giải pháp tối ưu đòi hỏi phân tích toán học cẩn thận (kiểm tra Tính chất Lựa chọn Tham lam và Cấu trúc Tối ưu con), điều này đôi khi không hề đơn giản.

Bài tập ví dụ:

[Tham Lam]. Số may mắn

Hoàng yêu thích các số may mắn. Ta biết rằng một số là số may mắn nếu biểu diễn thập phân của nó chỉ chứa các chữ số may mắn là 4 và 7. Ví dụ, các số 47, 744, 4 là số may mắn và 5, 17, 467 không phải. Hoàng muốn tìm số may mắn bé nhất có tổng các chữ số bằng n. Hãy giúp anh ấy.

Input Format

Dòng duy nhất chứa số nguyên dương n.(1<=n<=10^6)

Constraints

Output Format

In ra đáp án của bài toán, nếu không tồn tại đáp án thì in ra -1.

Ví dụ:

Dữ liệu vào

Dữ liệu ra

Bài toán yêu cầu tìm số may mắn bé nhất có tổng các chữ số bằng $n$. Số may mắn chỉ chứa chữ số 4 và 7.

Phân tích cấu trúc số: Để số tạo thành là bé nhất với một số lượng chữ số 4 và 7 cho trước, các chữ số 4 (bé hơn) nên đứng trước các chữ số 7 (lớn hơn). Ví dụ, với hai chữ số 4 và một chữ số 7, số bé nhất là 447, không phải 474 hay 744. Do đó, số may mắn bé nhất sẽ có dạng gồm một dãy các chữ số 4, sau đó là một dãy các chữ số 7.
Bài toán quy về tìm số lượng: Gọi số lượng chữ số 4 là $c_4$ và số lượng chữ số 7 là $c_7$. Ta cần tìm các số nguyên không âm $c_4, c_7$ sao cho tổng các chữ số bằng $n$: $4 \times c_4 + 7 \times c_7 = n$ Và số tạo bởi $c_4$ chữ số 4 đứng trước $c_7$ chữ số 7 là nhỏ nhất.
Tối ưu hóa: Để số tạo thành là nhỏ nhất, ta cần tối thiểu hóa tổng số chữ số $c_4 + c_7$. Từ phương trình $4 \times c_4 + 7 \times c_7 = n$, ta có $c_4 = (n - 7 \times c_7) / 4$. Tổng số chữ số là $c_4 + c_7 = (n - 7 \times c_7) / 4 + c_7 = n/4 - 7/4 \times c_7 + c_7 = n/4 - 3/4 \times c_7$. Để $c_4 + c_7$ là nhỏ nhất, ta cần tối đa hóa $c_7$ (vì hệ số của $c_7$ là âm).
Thuật toán:
- Ta tìm giá trị $c_7$ lớn nhất có thể thỏa mãn phương trình và điều kiện $c_4 \ge 0$.
- Giá trị lớn nhất có thể của $c_7$ là $\lfloor n/7 \rfloor$.
- Ta thử các giá trị $c_7$ từ $\lfloor n/7 \rfloor$ giảm dần về 0.
- Với mỗi giá trị $c_7$, tính phần tổng còn lại cần bù đắp bằng chữ số 4: $remaining_sum = n - 7 \times c_7$.
- Kiểm tra xem $remaining_sum$ có không âm ($remaining_sum \ge 0$) và có chia hết cho 4 hay không ($remaining_sum \pmod 4 == 0$).
- Nếu có, ta tìm được số lượng $c_4 = remaining_sum / 4$. Cặp $(c_4, c_7)$ này là cặp thỏa mãn điều kiện tổng bằng $n$ và có $c_7$ lớn nhất (vì ta duyệt $c_7$ giảm dần và dừng lại ngay khi tìm thấy).
- In ra $c_4$ chữ số 4, sau đó in ra $c_7$ chữ số 7. Đây chính là số may mắn bé nhất. Kết thúc chương trình.
- Nếu vòng lặp kết thúc mà không tìm thấy cặp $(c_4, c_7)$ nào thỏa mãn, nghĩa là không tồn tại số may mắn có tổng chữ số bằng $n$. In ra -1.

Hướng dẫn triển khai bằng C++:

Đọc số nguyên dương $n$.
Sử dụng một vòng lặp duyệt biến $c_7$ từ $n/7$ xuống 0.
Trong vòng lặp, tính rem = n - 7 * c7.
Kiểm tra nếu rem >= 0 và rem % 4 == 0.
Nếu điều kiện đúng:
- Tính c4 = rem / 4.
- Dùng vòng lặp in ra c4 lần chữ số '4'.
- Dùng vòng lặp in ra c7 lần chữ số '7'.
- In xuống dòng.
- Thoát chương trình (hoặc dùng cờ hiệu để báo đã tìm thấy và sau đó thoát).
Nếu vòng lặp kết thúc mà chưa thoát, in ra -1 và xuống dòng.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.