🎯 Thuật toán Tham lam và Quy hoạch động cơ bản với C++

Trong quá trình học thuật toán, hai kỹ thuật nổi bật giúp giải quyết các bài toán tối ưu là: Tham lam (Greedy) và Quy hoạch động (Dynamic Programming). Tuy cùng hướng tới mục tiêu tìm lời giải tốt nhất, nhưng chúng khác nhau hoàn toàn về cách tư duy, cách tiếp cận và phạm vi ứng dụng. Với C++, bạn hoàn toàn có thể triển khai cả hai kỹ thuật một cách rõ ràng, hiệu quả và tối ưu về hiệu suất.

NỘI DUNG

⚡ Thuật toán Tham lam (Greedy)

🧠 Tư duy chính: Ở mỗi bước, chọn phương án tốt nhất hiện tại, với hy vọng toàn bộ lời giải là tối ưu.

📌 Đặc điểm:

Nhanh, đơn giản
Không quay lui hay xét toàn bộ
Không đảm bảo tối ưu nếu không chứng minh được tính chất bài toán

🧮 Ví dụ 1: Đổi tiền (tờ tiền mệnh giá cố định)

Bài toán: Cho các mệnh giá {100, 50, 20, 10, 5, 1} và số tiền n, hãy đổi sao cho số tờ ít nhất.

int greedyChange(int n) {
    int count = 0;
    int coins[] = {100, 50, 20, 10, 5, 1};
    for (int coin : coins) {
        count += n / coin;
        n %= coin;
    }
    return count;
}

✅ Với hệ mệnh giá “chuẩn”, thuật toán cho kết quả tối ưu.

📦 Ví dụ 2: Bài toán cái ba lô phân đoạn (Fractional Knapsack)

Có thể lấy một phần vật phẩm
Chọn theo giá trị/khối lượng lớn nhất

📌 Cần sắp xếp và duyệt greedy – rất nhanh và hiệu quả.

🧱 Khi nên dùng Tham lam?

✅ Bài toán có tính chọn lựa cục bộ tối ưu → dẫn tới toàn cục tối ưu
✅ Có thể chứng minh bằng bất đẳng thức, cấu trúc bài toán hoặc phản chứng

🧠 Quy hoạch động (Dynamic Programming – DP)

🧩 Tư duy chính:

Bài toán lớn được chia thành các bài toán con chồng lặp
Kết quả bài toán con được lưu lại để tái sử dụng (memoization/tabulation)

⏱️ Giúp tối ưu các bài toán có độ phức tạp cao do lặp lại tính toán

📘 Ví dụ 1: Dãy Fibonacci – tránh lặp lại

int fibo(int n) {
    int f[1000];
    f[0] = 0; f[1] = 1;
    for (int i = 2; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
    return f[n];
}

📉 Nếu dùng đệ quy thường: O(2ⁿ)
✅ Dùng DP: O(n)

🎒 Ví dụ 2: Bài toán cái ba lô 0/1 (0/1 Knapsack)

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1] = {0};

    for (int i = 0; i <= n; i++)
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    return dp[n][W];
}

✅ Giải được bài toán tối ưu nhưng không thể dùng tham lam!

🔍 Khác biệt giữa Tham lam và Quy hoạch động

Tiêu chí	Tham lam (Greedy)	Quy hoạch động (DP)
Chiến lược	Chọn tốt nhất tại mỗi bước	Xét mọi khả năng, lưu kết quả
Hiệu suất	Rất nhanh (O(n log n))	Trung bình (O(n²), O(n·W),…)
Độ chính xác	Có thể sai nếu không chứng minh	Luôn đúng nếu triển khai đúng
Dữ liệu cần lưu	Ít	Phải lưu bảng kết quả
Khó khăn	Phải chứng minh được tính tham lam	Xác định trạng thái và công thức

✅ Mẹo phân biệt và lựa chọn

Nếu bài toán đơn giản, có tính chọn lựa rõ ràng → thử Greedy
Nếu kết quả phụ thuộc vào nhiều phương án trước đó → dùng DP
Thử Greedy → nếu sai, chuyển sang DP là hướng đi hiệu quả!

🧾 Kết luận

🎯 Tham lam và Quy hoạch động là hai công cụ mạnh mẽ nhưng phải dùng đúng chỗ. Một người lập trình giỏi không chỉ biết viết code, mà còn phải biết phân tích bài toán, hiểu rõ bản chất dữ liệu và chọn đúng công cụ giải quyết.

💡 Kỹ năng lập trình giỏi không nằm ở số dòng lệnh – mà ở lựa chọn giải pháp thông minh.

Lập trình C/C++