Bài 17.5. Bài tập tổng hợp về thuật toán tham lam

Chào mừng trở lại series blog về Cấu trúc dữ liệu và Giải thuật! Ở các bài trước, chúng ta có lẽ đã tìm hiểu về bản chất của thuật toán tham lam (Greedy Algorithm). Nhắc lại một chút, ý tưởng chính của tham lam là tại mỗi bước, chúng ta đưa ra lựa chọn tối ưu cục bộ 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.

Tuy nhiên, không phải bài toán nào cũng có thể giải bằng tham lam một cách đúng đắn. Tính hiệu quả của thuật toán tham lam phụ thuộc rất nhiều vào cấu trúc tối ưu của bài toán đó. Cách tốt nhất để thực sự hiểu khi nào và làm thế nào để áp dụng tham lam là thông qua việc thực hành giải quyết các bài toán cụ thể.

Bài viết này sẽ là một buổi thực hành tổng hợp, nơi chúng ta cùng nhau đi sâu vào một số bài toán kinh điển và xem thuật toán tham lam được áp dụng như thế nào. Hãy chuẩn bị sẵn sàng để viết code nhé!

Bài toán 1: Đổi tiền tệ (Coin Change Problem - Greedy Approach)

Mô tả bài toán: Cho một tập hợp các mệnh giá tiền xu có sẵn (ví dụ: 1, 5, 10, 25 cents) và một số tiền mục tiêu. Cần tìm số lượng ít nhất các đồng xu để tạo ra số tiền mục tiêu đó, với giả định có số lượng vô hạn các đồng xu thuộc mỗi mệnh giá.

Ý tưởng tham lam: Để có số lượng đồng xu ít nhất, tại mỗi bước, ta nên ưu tiên sử dụng đồng xu có mệnh giá lớn nhất có thể mà vẫn không vượt quá số tiền còn lại cần đổi. Lặp lại quá trình này cho đến khi số tiền cần đổi bằng 0.

Lưu ý quan trọng: Chiến lược tham lam này không phải lúc nào cũng cho kết quả tối ưu cho mọi hệ thống mệnh giá tiền tệ. Nó chỉ hoạt động chính xác với các hệ thống mệnh giá được gọi là "canonical", như hệ thống tiền tệ của Mỹ hay Euro. Với các hệ thống mệnh giá "không canonical" (ví dụ: 1, 3, 4 để đổi lấy 6), tham lam (4+1+1 = 3 xu) sẽ kém tối ưu hơn giải pháp động (3+3 = 2 xu). Tuy nhiên, với các hệ thống canonical phổ biến, tham lam là một giải pháp đơn giản và hiệu quả.

Minh họa bằng C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional> // For std::greater

// Hàm đếm số lượng đồng xu tối thiểu bằng thuật toán tham lam
int countCoinsGreedy(int amount, std::vector<int>& denominations) {
    // Sắp xếp các mệnh giá theo thứ tự giảm dần
    // Đây là bước quan trọng để chiến lược tham lam hoạt động: luôn chọn đồng lớn nhất
    std::sort(denominations.begin(), denominations.end(), std::greater<int>());

    int coin_count = 0;
    std::cout << "De doi " << amount << " don vi, su dung cac dong xu: ";

    // Duyệt qua từng mệnh giá từ lớn đến nhỏ
    for (int coin : denominations) {
        // Lấy số lượng đồng xu mệnh giá 'coin' nhiều nhất có thể
        while (amount >= coin) {
            amount -= coin;
            coin_count++;
            std::cout << coin << " "; // In ra đồng xu đã sử dụng (tùy chọn)
        }
    }
    std::cout << std::endl;
    return coin_count;
}

int main() {
    // Hệ thống mệnh giá canonical (ví dụ: USD cents)
    std::vector<int> denominations_canonical = {100, 25, 10, 5, 1};
    int amount1 = 178; // Ví dụ: $1.78

    std::cout << "--- Voi he thong canonical ---" << std::endl;
    int min_coins1 = countCoinsGreedy(amount1, denominations_canonical);
    std::cout << "So dong xu toi thieu cho " << amount1 << ": " << min_coins1 << std::endl; // Output: 100 25 25 25 1 1 1 (6 xu)

    std::cout << "\n";

    // Hệ thống mệnh giá KHÔNG canonical (ví dụ: 1, 3, 4)
    // Tham lam sẽ cho kết quả không tối ưu cho amount = 6
    std::vector<int> denominations_non_canonical = {4, 3, 1};
    int amount2 = 6;

    std::cout << "--- Voi he thong KHONG canonical ---" << std::endl;
    // Lưu ý: Truyền một bản sao để không làm thay đổi denominations_non_canonical gốc nếu cần sử dụng lại
    std::vector<int> temp_denominations = denominations_non_canonical;
    int min_coins2_greedy = countCoinsGreedy(amount2, temp_denominations);
    std::cout << "So dong xu cho " << amount2 << " (tham lam): " << min_coins2_greedy << std::endl; // Output: 4 1 1 (3 xu)
    // So sánh với tối ưu thực tế: 3 + 3 = 6 (2 xu). Tham lam kém tối ưu.

    return 0;
}

Giải thích code:

Chúng ta định nghĩa hàm countCoinsGreedy nhận số tiền amount và vector các mệnh giá denominations.
Bước then chốt của chiến lược tham lam ở đây là sắp xếp các mệnh giá theo thứ tự giảm dần (std::sort với std::greater<int>). Điều này đảm bảo rằng chúng ta luôn xét đến các đồng xu có giá trị lớn nhất trước.
Biến coin_count dùng để đếm tổng số đồng xu đã sử dụng.
Ta duyệt qua từng mệnh giá coin trong vector đã sắp xếp.
Với mỗi mệnh giá, ta sử dụng vòng lặp while để lấy càng nhiều càng tốt các đồng xu có mệnh giá đó miễn là số tiền cần đổi (amount) còn đủ lớn hơn hoặc bằng coin.
Mỗi lần lấy một đồng xu, ta giảm amount đi giá trị của đồng xu và tăng coin_count.
Quá trình lặp cho đến khi duyệt hết các mệnh giá hoặc amount về 0.
Hàm trả về tổng số đồng xu đã dùng.
Trong main, ta thử nghiệm với cả hệ thống mệnh giá canonical (hoạt động tốt) và non-canonical (cho thấy tham lam không tối ưu).

Độ phức tạp thời gian của thuật toán này chủ yếu phụ thuộc vào việc sắp xếp (O(N log N), với N là số lượng mệnh giá) và vòng lặp lồng nhau. Vòng lặp bên trong while có thể chạy nhiều lần, nhưng tổng số lần giảm amount trên tất cả các mệnh giá không vượt quá một ngưỡng nhất định (phụ thuộc vào amount và mệnh giá nhỏ nhất), thường hiệu quả trong thực tế cho các hệ thống tiền tệ chuẩn. Tuy nhiên, về lý thuyết worst-case, nó có thể là O(N * Amount) nếu không cẩn thận, nhưng với việc amount giảm nhanh chóng khi sử dụng đồng xu lớn, nó thường nhanh hơn nhiều. Sắp xếp thường là phần chiếm nhiều thời gian nhất, nên độ phức tạp tổng thể là O(N log N).

Bài toán 2: Chọn hoạt động (Activity Selection Problem)

Mô tả bài toán: Cho một tập hợp các hoạt động, mỗi hoạt động có thời gian bắt đầu và thời gian kết thúc. Cần chọn ra số lượng lớn nhất các hoạt động sao cho không có hai hoạt động nào bị trùng lặp (thời gian của chúng chồng lên nhau).

Ý tưởng tham lam: Để chọn được nhiều hoạt động nhất, một chiến lược trực quan là luôn chọn hoạt động kết thúc sớm nhất trong số các hoạt động khả dụng còn lại. Lý do là việc chọn một hoạt động kết thúc sớm sẽ "giải phóng" thời gian sớm hơn, cho phép nhiều cơ hội hơn để chọn các hoạt động khác theo sau.

Minh họa bằng C++:

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

// Cấu trúc để biểu diễn một hoạt động
struct Activity {
    int start;
    int finish;
};

// Hàm so sánh tùy chỉnh để 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; // Sắp xếp tăng dần theo thời gian kết thúc
}

// Hàm thực hiện chọn hoạt động bằng thuật toán tham lam
void selectActivitiesGreedy(std::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
    std::sort(activities.begin(), activities.end(), compareActivities);

    std::cout << "Cac hoat dong duoc chon (Tham lam):" << std::endl;

    // Bước 2: Hoạt động đầu tiên sau khi sắp xếp luôn được chọn
    // (vì nó kết thúc sớm nhất)
    int i = 0; // Index của hoạt động được chọn gần nhất
    std::cout << "- Hoat dong [" << activities[i].start << ", " << activities[i].finish << "]" << std::endl;

    // Bước 3: Duyệt qua các hoạt động còn lại
    for (int j = 1; j < activities.size(); j++) {
        // Nếu thời gian bắt đầu của hoạt động hiện tại (j)
        // lớn hơn hoặc bằng thời gian kết thúc của hoạt động được chọn gần nhất (i)
        // tức là chúng không bị trùng lặp
        if (activities[j].start >= activities[i].finish) {
            std::cout << "- Hoat dong [" << activities[j].start << ", " << activities[j].finish << "]" << std::endl;
            i = j; // Cập nhật hoạt động được chọn gần nhất là hoạt động hiện tại
        }
    }
}

int main() {
    std::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}
    };

    selectActivitiesGreedy(activities);
    // Kết quả mong đợi (dựa trên chỉ mục của vector gốc): 0, 3, 7, 10
    // [1, 4], [5, 7], [8, 11], [12, 16] -> Tổng cộng 4 hoạt động được chọn.

    return 0;
}

Giải thích code:

Chúng ta định nghĩa cấu trúc Activity để lưu trữ thời gian bắt đầu và kết thúc.
Hàm so sánh compareActivities được tạo ra để sắp xếp vector các Activity dựa trên trường finish (thời gian kết thúc) theo thứ tự tăng dần.
Trong hàm selectActivitiesGreedy, bước đầu tiên và quan trọng nhất của chiến lược tham lam là sắp xếp các hoạt động theo thời gian kết thúc (std::sort với compareActivities).
Hoạt động đầu tiên trong danh sách đã sắp xếp luôn được chọn, vì nó kết thúc sớm nhất và tối đa hóa "không gian" còn lại để chọn các hoạt động khác. Ta lưu chỉ mục của hoạt động này vào biến i.
Ta duyệt qua các hoạt động còn lại từ hoạt động thứ hai (j = 1).
Đối với mỗi hoạt động j, ta kiểm tra xem nó có bắt đầu sau hoặc đúng vào lúc hoạt động i kết thúc hay không (activities[j].start >= activities[i].finish). Nếu có, điều này có nghĩa là hoạt động j không trùng lặp với hoạt động i.
Nếu không trùng lặp, ta chọn hoạt động j, in thông tin của nó ra và cập nhật i = j để hoạt động j trở thành hoạt động được chọn gần nhất cho lần lặp tiếp theo.
Quá trình này lặp lại cho đến hết danh sách. Các hoạt động được in ra là những hoạt động được chọn.

Độ phức tạp thời gian của thuật toán này là O(N log N) do bước sắp xếp chiếm ưu thế, trong đó N là số lượng hoạt động. Sau khi sắp xếp, việc duyệt qua danh sách chỉ mất O(N) thời gian.

Bài toán 3: Balo phân số (Fractional Knapsack Problem)

Mô tả bài toán: Cho một tập hợp các vật phẩm, mỗi vật phẩm có một trọng lượng và một giá trị, cùng với sức chứa tối đa của một cái balo. Cần chọn các vật phẩm để đưa vào balo sao cho tổng giá trị là lớn nhất, với khả năng lấy một phần của vật phẩm (khác với bài toán Balo 0/1 chỉ được lấy toàn bộ hoặc không lấy).

Ý tưởng tham lam: Để tối đa hóa tổng giá trị khi có thể lấy phân số, chiến lược tốt nhất là ưu tiên các vật phẩm mang lại nhiều giá trị nhất trên mỗi đơn vị trọng lượng. Tỷ lệ này được gọi là tỷ lệ giá trị/trọng lượng (value-to-weight ratio). Bằng cách luôn chọn vật phẩm có tỷ lệ này cao nhất trước tiên, ta đảm bảo balo được lấp đầy bằng "các phần" vật phẩm hiệu quả nhất cho đến khi đầy.

Minh họa bằng C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip> // For setting precision

// Cấu trúc để biểu diễn một vật phẩm
struct Item {
    int weight;
    int value;
    double ratio; // Tỷ lệ giá trị / trọng lượng
};

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

// Hàm giải bài toán Balo phân số bằng thuật toán tham lam
double fractionalKnapsackGreedy(int capacity, std::vector<Item>& items) {
    // Bước 1: Tính toán tỷ lệ giá trị/trọng lượng cho mỗi vật phẩm
    for (auto& item : items) {
        item.ratio = static_cast<double>(item.value) / item.weight;
    }

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

    double total_value = 0.0;
    int current_capacity = capacity;

    std::cout << "Nhet balo (Tham lam theo ty le Gia tri/Trong luong):" << std::endl;

    // Bước 3: Duyệt qua các vật phẩm đã sắp xếp
    for (const auto& item : items) {
        // Nếu balo đã đầy, dừng lại
        if (current_capacity <= 0) {
            break;
        }

        // Nếu trọng lượng của vật phẩm hiện tại nhỏ hơn hoặc bằng sức chứa còn lại
        // -> Lấy toàn bộ vật phẩm này
        if (item.weight <= current_capacity) {
            current_capacity -= item.weight;
            total_value += item.value;
            std::cout << "  Lay toan bo vat pham (W:" << item.weight << ", V:" << item.value << ", Ratio:" << std::fixed << std::setprecision(2) << item.ratio << "). Suc chua con lai: " << current_capacity << std::endl;
        }
        // Ngược lại (trọng lượng vật phẩm lớn hơn sức chứa còn lại)
        // -> Lấy một phần của vật phẩm để lấp đầy balo
        else {
            double fraction = static_cast<double>(current_capacity) / item.weight;
            total_value += item.value * fraction;
            current_capacity = 0; // Balo đã đầy
            std::cout << "  Lay mot phan (" << std::fixed << std::setprecision(2) << fraction * 100 << "%) cua vat pham (W:" << item.weight << ", V:" << item.value << ", Ratio:" << std::fixed << std::setprecision(2) << item.ratio << "). Suc chua con lai: " << current_capacity << std::endl;
            break; // Dừng lại vì balo đã đầy
        }
    }

    return total_value;
}

int main() {
    std::vector<Item> items = {
        {10, 60},  // Item 1: W=10, V=60
        {20, 100}, // Item 2: W=20, V=100
        {30, 120}  // Item 3: W=30, V=120
    };
    int capacity = 50;

    // Tính toán tỷ lệ:
    // Item 1: 60/10 = 6.0
    // Item 2: 100/20 = 5.0
    // Item 3: 120/30 = 4.0
    // Thứ tự tham lam (giảm dần ratio): Item 1, Item 2, Item 3

    double max_value = fractionalKnapsackGreedy(capacity, items);

    std::cout << "\nTong gia tri toi da trong balo: " << std::fixed << std::setprecision(2) << max_value << std::endl;
    // Kết quả mong đợi theo tham lam:
    // Lay toan bo Item 1 (W=10, V=60). Suc chua con: 50-10=40. Tong V=60.
    // Lay toan bo Item 2 (W=20, V=100). Suc chua con: 40-20=20. Tong V=60+100=160.
    // Lay mot phan Item 3 (W=30, V=120). Phan lay = 20/30. V = (20/30)*120 = 80. Suc chua con: 0. Tong V=160+80=240.
    // Tong gia tri toi da = 240.00

    return 0;
}

Giải thích code:

Chúng ta định nghĩa cấu trúc Item bao gồm trọng lượng weight, giá trị value, và một trường ratio để lưu tỷ lệ giá trị/trọng lượng.
Hàm so sánh compareItems được dùng để sắp xếp các vật phẩm dựa trên ratio theo thứ tự giảm dần.
Trong hàm fractionalKnapsackGreedy:
- Đầu tiên, vòng lặp duyệt qua tất cả vật phẩm để tính toán và lưu ratio vào mỗi đối tượng Item.
- Sau đó, danh sách vật phẩm được sắp xếp theo ratio giảm dần bằng std::sort và compareItems.
- Biến total_value để lưu tổng giá trị đã thu được, current_capacity để theo dõi sức chứa còn lại của balo.
- Ta duyệt qua từng vật phẩm đã sắp xếp.
- Nếu sức chứa còn lại (current_capacity) bằng 0 hoặc âm, balo đã đầy, ta dừng lại.
- Nếu trọng lượng của vật phẩm hiện tại (item.weight) nhỏ hơn hoặc bằng sức chứa còn lại, ta lấy toàn bộ vật phẩm đó. Cập nhật current_capacity và total_value.
- Nếu trọng lượng của vật phẩm hiện tại lớn hơn sức chứa còn lại, ta chỉ lấy một phần của nó. Phần này được tính bằng current_capacity / item.weight. Ta cộng giá trị tương ứng của phần này (item.value * fraction) vào total_value và đặt current_capacity về 0 vì balo đã đầy. Sau đó, ta dừng vòng lặp.
- std::fixed và std::setprecision(2) được sử dụng để hiển thị giá trị tiền tệ với 2 chữ số thập phân cho dễ nhìn.
Hàm trả về tổng giá trị tối đa có thể chứa trong balo.

Độ phức tạp thời gian của thuật toán này là O(N log N) do bước sắp xếp vật phẩm dựa trên tỷ lệ giá trị/trọng lượng, trong đó N là số lượng vật phẩm. Sau khi sắp xếp, việc lấp đầy balo chỉ mất O(N) thời gian trong trường hợp xấu nhất.

Bài tập ví dụ:

[Tham Lam]. Sắp đặt xâu kí tự

Cho xâu kí tự S chỉ bao gồm các kí tự in thường, hãy kiểm tra xem có thể sắp đặt lại các kí tự trong xâu sao cho không có 2 kí tự kề nhau nào giống nhau hay không?

Input Format

Dòng duy nhất chứa xâu S.(1<=len(S)<=10000)

Constraints

Output Format

Nếu có thể sắp đặt lại xâu kí tự in ra YES, ngược lại in ra NO.

Ví dụ:

Dữ liệu vào

aaaaabbbc

Dữ liệu ra

YES

Tuyệt vời, đây là hướng dẫn ngắn gọn để giải bài toán "Sắp đặt xâu kí tự" bằng C++:

Ý tưởng chính: Khả năng sắp xếp lại xâu sao cho không có hai ký tự kề nhau nào giống nhau phụ thuộc vào tần suất xuất hiện của các ký tự. Cụ thể, nếu ký tự xuất hiện nhiều nhất có tần suất quá cao so với độ dài của xâu, thì không thể sắp xếp được.
Ngưỡng giới hạn: Ký tự xuất hiện nhiều nhất (max_freq) chỉ có thể chiếm tối đa một nửa số vị trí trong xâu, cộng thêm 1 nếu độ dài xâu là lẻ. Hay nói cách khác, nếu max_freq lớn hơn (độ dài xâu + 1) / 2 (phép chia nguyên), thì không thể sắp xếp được.
Các bước thực hiện:
- Đọc xâu đầu vào S.
- Đếm tần suất xuất hiện của mỗi ký tự (a-z) trong xâu S. Có thể dùng một mảng kích thước 26 hoặc một std::map.
- Tìm tần suất xuất hiện lớn nhất (max_freq) trong tất cả các ký tự.
- So sánh max_freq với ngưỡng (độ dài xâu + 1) / 2.
- Nếu max_freq > (độ dài xâu + 1) / 2, in ra "NO".
- Ngược lại, in ra "YES".
Lưu ý: Bạn chỉ cần kiểm tra điều kiện tần suất này. Nếu điều kiện này thỏa mãn, luôn tồn tại một cách sắp xếp hợp lệ.

Chúc bạn làm bài tốt!

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

Comments

There are no comments at the moment.