Thuật toán tham lam (Greedy Algorithm) – Thực hành với C++

Bài viết được sự cho phép bởi tác giả Sơn Dương

Hôm nay chúng ta quay trở lại với series thuật toán chuyên sâu nhé. Mặc dù, nói tới thuật toán là mình cảm thấy đau đầu vì tính phức tạp của nó, nhưng khi đã thẩm thấu xong một thuật toán, bản thân lại cảm thấy vô cùng thích thú

Bài viết hôm nay, mình sẽ đề cập tới thuật toán tham lam (Greedy Algorithms) – nghe tên thôi đã thấy tham rùi.

Cùng với thuật toán “Chia để trị –  Divide and Conquer”, thuật toán tham lam là một trong những thuật toán thường xuyên xuất hiện trong các câu hỏi phỏng vấn tuyển dụng. Thật là thiết sót nếu bạn lại bỏ lỡ không biết về thuật toán này.

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

Hiểu một cách “nông dân” nhất có thể về thuật toán này như sau: Khi bạn gặp một bài toán lớn phải chứng minh nó đúng. Ví dụ: Chứng minh toàn bộ người dân Việt Nam đều là người cần cù, chịu khó, làm việc chăm chỉ.

Vấn đề là bạn không thể gặp và tiếp xúc tất cả người Việt Nam được. Thay vào đó, bạn gặp điểm một số người thôi, những người cùng quê, cùng gia đình, bạn bè… và bạn thấy đúng là họ đều cần cù, chịu khó, làm việc chăm chỉ cả. Thế là bạn suy ra toàn bộ người Việt Nam đều như vậy.

Tư tưởng của thuật toán này chỉ có vậy thôi.

Cái vấn đề của thuật toán này là: Có thể kết quả cuối cùng không chính xác và phụ thuộc rất nhiều vào bài toán con mà bạn chọn ra để kiểm chứng.

Nhưng ngược lại, thuật toán tham lam lại có ưu điểm là tốc độ xử lý nhanh. “võ đoán” thì lại chẳng nhanh, “may hơn khôn” mà.

Để hiểu hơn về thuật toán này, chúng ta cùng xem xét một ví dụ sau nhé.

Ví dụ đếm coins sử dụng thuật toán Tham lam

Giả sử trong ví, bạn có một số tờ tiền có các mệnh giá tương ứng: 1$, 2$, 5$ và 10$. Yêu cầu là chọn ra các tờ tiền để có tổng số tiền cần trả cho nhà hàng.

Trường hợp 1: tổng số tiền cần trả là 16$

Sử dụng thuật toán tham lam, bạn sẽ bắt đầu chọn các bước như sau:

• Đầu tiên, cứ lấy một đồng 10$ đã. Vậy là còn thiếu 6$ nữa
• Thế thì, tiếp theo, sẽ lấy 1 tờ 5$ và cuối cùng là tờ 1$

Với cách làm này, kết quả và bước thực hiện rất tối ưu. Nhưng… Tại sao bạn lại chọn tờ 10$ trước? Bạn hoàn toàn có thể chọn các tờ tiền khác trước cũng được mà?

Đây chính là đặc điểm của thuật toán tham lam.

Trường hợp 2: tổng số tiền cần trả là 17$

Cũng tương tự như cách ở trên, Bạn có thể sẽ làm như sau:

• Đầu tiên là lấy tờ 10$ đã.
• Tiếp theo, bạn lại chọn 7 tờ mệnh giá 1$.

Như trong trường hợp này thì thuật toán đã không còn tối ưu nữa.

Cấu trúc cơ bản của thuật toán Tham lam

Dưới đây là một tiêu chí, đặc điểm nhận biết để xem với một bài toán nào đó mà áp dụng thuật toán tham lam liệu có hiệu quả không?

• Chúng ta được cung cấp một danh sách các tài nguyên giống như coins, tasks,v.v…
• Chúng ta có thể bắt đầu với nguồn tài nguyên có giá trị lớn nhất.
• Tiếp theo, chúng ta có thể tiếp tục bổ sung các tài nguyên có giá trị lớn hơn để đạt đưuọc giải pháp tối ưu hóa nhất.

Việc làm C++ lương cao, hấp dẫn dành cho bạn!

Thực hành thuật toán tham lam với C++

Trăm hay không bằng tay quen, để có thể hiểu và làm chủ được một thuật toán, không có gì nhanh hơn là tự tay thực hành giải một bài toán.

Bài toán: Tìm thời gian tốt nhất để mua và bán cổ phiếu

Mô tả bài toán: bạn được cung cấp một mảng giá của một cố phiếu trong một số ngày. Bạn phải chọn ra một ngày để mua cổ phiếu và một ngày khác để bán cổ phiếu đó. Kết quả trả về là lợi nhuận mà bạn kiếm được.

Gợi ý giải pháp: Bỏ qua một bên các kiến thức chuyên ngành về chứng khoán, về “tâm linh”… Chúng ta chỉ bám vào nguyên tắc duy nhất: “Mua đáy bán đỉnh”. Tức là mua khi giá cổ phiếu thấp nhất và bán khi nó có giá cao nhất.

• Ý tưởng sắp xếp mảng là không khả thi. Vì giá cổ phiếu nó đi theo từng ngày, chứ không có độc lập. Do đó, trước hết bạn tìm giá cố phiếu thấp nhất từ mảng đầu vào đã.
• Vị trí của phần tử mà có giá cổ phiếu thấp nhất chính là ngày mình sẽ mua cổ phiếu
• Còn ngày bán, chắc chắn phải là những ngày sau khi bạn mua cổ phiếu đó.
• Do đó, bạn chạy một vòng lặp bắt đầu từ ngày mua cổ phiếu và tìm giá trị cổ phiếu cao nhất trong số những ngày còn lại.
• Cuối cùng là trừ giá cổ phiếu ở ngày bán cho giá cổ phiếu tại ngày mua là ra kết quả cần tìm.

Ví dụ dữ liệu:

Đầu vào: [7,1,5,3,6,4]

Kết quả mong muốn: 5

Code mẫu:

//C++ Program For Best Time to Buy and Sell Stock
#include
#include<bits/stdc++.h>

using namespace std;

int main() {
    //Implementing the array for prices on ith days of stock
    int n = 6;
    vector<int> prices = {7,1,5,3,6,4};

    //for storing best days to buy and sell stock
    pair<int,int> ans;
    //For storing maximum profit
    int maxProfit = 0;
    //For storing minimum purchase of stock
    int minBuy = INT_MAX;
    //index of minbuy
    int ind;

    for(int i=0;i<prices.size();i++){

        //if we get min price for buying than earlier then we update minBuy and its index
        if(minBuy>prices[i]){
            ind = i;
           minBuy = prices[i];
        }

        //Finding maximum profit by checking selling at ith day prices with minBuy
        if(maxProfit<prices[i] - minBuy){
            maxProfit=prices[i] - minBuy;
            ans = {ind,i};  // storing the days of buying and selling
        }
    }

    //Printing the best time to buy and sell stock and its maximum profit
    cout<<"Best Time to buy on day "<<ans.first+1<<" and sell on day "<<ans.second+1<<endl;
    cout<<"Maximum Profit Will be "<<maxProfit;
    return 0;
}

Chạy chương trình:

Best Time to buy on day 2 and sell on day 5.
Maximum Profit Will be 5

Tạm kết

Như vậy là chúng ta đã tìm hiểu xong về thuật toán tham lam, một trong những thuật toán phổ biến nhất.

Minh hi vọng, sau bài viết này bạn sẽ tự tin đi phỏng vấn mà không còn run sợ khi nhà tuyển dụng hỏi tới!

Bài viết gốc được đăng tải tại vntalking.com

Xem thêm:

• Thuật toán Gradient Descent
• Sử dụng thuật toán quay lui giải bài toán phân tích số bằng JavaScript
• Các thuật toán sắp xếp phổ biến trong JavaScript
• Xem thêm It Job for Developer hấp dẫn trên TopDev