Lập trình C/C++

Thuật toán tham lam trong C++ (Full Code)

Posted on by Đỗ Thành
Nhóm học lập trình
02
Th2
View: 67

Thuật toán tham lam (Greedy Algorithm) là một trong những phương pháp giải quyết vấn đề phổ biến trong lập trình và khoa học máy tính. Thuật toán này thường được sử dụng để giải quyết các bài toán tối ưu hóa, nơi mà tại mỗi bước, chúng ta chọn lựa tối ưu cục bộ với hy vọng rằng kết quả cuối cùng sẽ là tối ưu toàn cục.

Các đặc điểm chính của thuật toán tham lam:

  1. Lựa chọn tối ưu cục bộ: Tại mỗi bước, thuật toán chọn lựa tối ưu nhất tại thời điểm đó mà không quan tâm đến kết quả cuối cùng.
  2. Không quay lui: Một khi đã đưa ra quyết định, thuật toán không xem xét lại các lựa chọn trước đó.
  3. Hiệu quả: Thuật toán tham lam thường có độ phức tạp thời gian thấp và dễ cài đặt.

Các bước để thiết kế thuật toán tham lam:

  1. Xác định bài toán: Xác định bài toán cần giải quyết và mục tiêu cần tối ưu.
  2. Xác định lựa chọn tối ưu cục bộ: Tại mỗi bước, xác định lựa chọn tối ưu nhất dựa trên tiêu chí đã định.
  3. Chứng minh tính đúng đắn: Chứng minh rằng lựa chọn tối ưu cục bộ sẽ dẫn đến kết quả tối ưu toàn cục.
  4. Cài đặt thuật toán: Viết mã để thực hiện thuật toán.

Một số bài toán kinh điển sử dụng thuật toán tham lam:

1. Bài toán đổi tiền (Coin Change Problem)

  • Mô tả: Cho một số tiền S và các mệnh giá tiền có sẵn. Tìm cách đổi số tiền S với số lượng tờ tiền ít nhất.
  • Cách tiếp cận tham lam: Luôn chọn mệnh giá lớn nhất có thể tại mỗi bước.
  • Ví dụ:
    • Mệnh giá: [1, 2, 5, 10, 20, 50, 100, 200, 500]
    • Số tiền cần đổi: 1234
    • Kết quả: 500 + 500 + 200 + 20 + 10 + 2 + 2
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> coinChange(int S, vector<int>& coins) {
    vector<int> result;
    sort(coins.rbegin(), coins.rend()); // Sắp xếp giảm dần

    for (int coin : coins) {
        while (S >= coin) {
            S -= coin;
            result.push_back(coin);
        }
    }

    return result;
}

int main() {
    vector<int> coins = {1, 2, 5, 10, 20, 50, 100, 200, 500};
    int S = 1234; // Số tiền cần đổi

    vector<int> result = coinChange(S, coins);

    cout << "Các tờ tiền cần đổi: ";
    for (int coin : result) {
        cout << coin << " ";
    }
    cout << endl;

    return 0;
}

2. Bài toán xếp lịch (Interval Scheduling)

  • Mô tả: Cho n công việc, mỗi công việc có thời gian bắt đầu và kết thúc. Tìm cách chọn nhiều công việc nhất mà không có sự chồng chéo thời gian.
  • Cách tiếp cận tham lam: Sắp xếp các công việc theo thời gian kết thúc tăng dần, sau đó chọn công việc kết thúc sớm nhất và loại bỏ các công việc chồng chéo.
  • Ví dụ:
    • Công việc: [(1, 3), (2, 5), (3, 6), (6, 8), (7, 10), (8, 9)]
    • Kết quả: [(1, 3), (6, 8), (8, 9)]
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Job {
    int start, finish;
};

bool compareJobs(Job a, Job b) {
    return a.finish < b.finish;
}

void scheduleJobs(vector<Job>& jobs) {
    sort(jobs.begin(), jobs.end(), compareJobs);

    cout << "Các công việc được chọn: \n";
    cout << "Công việc 1: (" << jobs[0].start << ", " << jobs[0].finish << ")\n";

    int lastSelected = 0;
    for (int i = 1; i < jobs.size(); i++) {
        if (jobs[i].start >= jobs[lastSelected].finish) {
            cout << "Công việc " << i + 1 << ": (" << jobs[i].start << ", " << jobs[i].finish << ")\n";
            lastSelected = i;
        }
    }
}

int main() {
    vector<Job> jobs = {{1, 3}, {2, 5}, {3, 6}, {6, 8}, {7, 10}, {8, 9}};

    scheduleJobs(jobs);

    return 0;
}

3. Bài toán phân chia công việc (Job Sequencing with Deadlines)

  • Mô tả: Cho n công việc, mỗi công việc có thời hạn (deadline) và lợi nhuận. Tìm cách chọn các công việc để tối đa hóa tổng lợi nhuận mà vẫn đảm bảo thời hạn.
  • Cách tiếp cận tham lam: Sắp xếp các công việc theo lợi nhuận giảm dần, sau đó chọn công việc có lợi nhuận cao nhất và đặt vào vị trí phù hợp nhất trong thời hạn.
  • Ví dụ:
    • Công việc: [(1, 2, 100), (2, 1, 50), (3, 2, 150), (4, 1, 200)] (id, deadline, profit)
    • Kết quả: [4, 3] với tổng lợi nhuận là 350.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Job {
    int id, deadline, profit;
};

bool compareJobs(Job a, Job b) {
    return a.profit > b.profit;
}

void jobSequencing(vector<Job>& jobs) {
    sort(jobs.begin(), jobs.end(), compareJobs);

    int maxDeadline = 0;
    for (const Job& job : jobs) {
        if (job.deadline > maxDeadline) {
            maxDeadline = job.deadline;
        }
    }

    vector<int> slot(maxDeadline + 1, -1);
    int totalProfit = 0;

    for (const Job& job : jobs) {
        for (int i = job.deadline; i > 0; i--) {
            if (slot[i] == -1) {
                slot[i] = job.id;
                totalProfit += job.profit;
                break;
            }
        }
    }

    cout << "Các công việc được chọn: ";
    for (int i = 1; i <= maxDeadline; i++) {
        if (slot[i] != -1) {
            cout << slot[i] << " ";
        }
    }
    cout << "\nTổng lợi nhuận: " << totalProfit << endl;
}

int main() {
    vector<Job> jobs = {{1, 2, 100}, {2, 1, 50}, {3, 2, 150}, {4, 1, 200}};

    jobSequencing(jobs);

    return 0;
}

4. Bài toán Cái Túi (Knapsack Problem)

  • Mô tả: Cho một cái túi có sức chứa tối đa W và n vật phẩm, mỗi vật phẩm có trọng lượng và giá trị. Tìm cách chọn các vật phẩm để đóng gói vào túi sao cho tổng giá trị là lớn nhất.
  • Cách tiếp cận tham lam: Sắp xếp các vật phẩm theo giá trị trên đơn vị trọng lượng giảm dần, sau đó chọn vật phẩm có giá trị cao nhất trước.
  • Ví dụ:
    • Vật phẩm: [(10, 60), (20, 100), (30, 120)] (trọng lượng, giá trị)
    • Sức chứa túi: 50
    • Kết quả: Chọn toàn bộ vật phẩm 1 và 2, một phần vật phẩm 3, tổng giá trị là 240.
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Item {
    int weight, value;
};

bool compareItems(Item a, Item b) {
    double ratioA = (double)a.value / a.weight;
    double ratioB = (double)b.value / b.weight;
    return ratioA > ratioB;
}

double fractionalKnapsack(int W, vector<Item>& items) {
    sort(items.begin(), items.end(), compareItems);

    double totalValue = 0.0;
    for (const Item& item : items) {
        if (W >= item.weight) {
            W -= item.weight;
            totalValue += item.value;
        } else {
            totalValue += item.value * ((double)W / item.weight);
            break;
        }
    }

    return totalValue;
}

int main() {
    vector<Item> items = {{10, 60}, {20, 100}, {30, 120}};
    int W = 50; // Sức chứa túi

    double maxValue = fractionalKnapsack(W, items);
    cout << "Tổng giá trị tối đa: " << maxValue << endl;

    return 0;
}

5. Bài toán tìm dãy con tăng dài nhất (Longest Increasing Subsequence – LIS)

  • Mô tả: Cho một dãy số, tìm dãy con tăng dài nhất (không nhất thiết liên tiếp).
  • Cách tiếp cận tham lam: Sử dụng thuật toán tối ưu với độ phức tạp O(n log n) bằng cách duy trì một mảng chứa các phần tử nhỏ nhất có thể của dãy con tăng.
  • Ví dụ:
    • Dãy số: [10, 22, 9, 33, 21, 50, 41, 60]
    • Kết quả: [10, 22, 33, 50, 60] (độ dài 5).
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp;
    for (int num : nums) {
        auto it = lower_bound(dp.begin(), dp.end(), num);
        if (it == dp.end()) {
            dp.push_back(num);
        } else {
            *it = num;
        }
    }
    return dp.size();
}

int main() {
    vector<int> nums = {10, 22, 9, 33, 21, 50, 41, 60};
    int lisLength = lengthOfLIS(nums);

    cout << "Độ dài dãy con tăng dài nhất: " << lisLength << endl;

    return 0;
}

Thuật toán tham lam (Greedy Algorithm) là một trong những chiến lược giải quyết bài toán hiệu quả nhưng không phải lúc nào cũng đem lại kết quả tối ưu. Dưới đây là một số ưu, nhược điểm và các bài toán nên áp dụng thuật toán này:

Ưu điểm:

  1. Đơn giản và dễ hiểu: Thuật toán tham lam rất dễ hiểu và dễ triển khai.
  2. Hiệu suất cao: Trong nhiều trường hợp, thuật toán tham lam có thể giải quyết bài toán với thời gian tính toán rất nhanh, đặc biệt là các bài toán cần đáp ứng yêu cầu thời gian thực.
  3. Không cần lưu trữ toàn bộ thông tin: Chỉ cần lưu trữ các quyết định hiện tại, không cần lưu trữ toàn bộ trạng thái của bài toán như các thuật toán khác.

Nhược điểm:

  1. Không đảm bảo kết quả tối ưu: Thuật toán tham lam chỉ đảm bảo kết quả tối ưu cho một số bài toán cụ thể mà không phải tất cả. Trong nhiều trường hợp, nó có thể đưa ra giải pháp không tối ưu.
  2. Thiếu linh hoạt: Do chiến lược của nó là tối ưu cục bộ từng bước, nó có thể bỏ qua các giải pháp tối ưu toàn cục.
  3. Phụ thuộc vào cấu trúc của bài toán: Thuật toán tham lam chỉ áp dụng tốt cho những bài toán có tính chất cụ thể, đặc biệt là những bài toán có cấu trúc dễ dàng nhận biết.
Đỗ Thành