Giới thiệu bài toán đổi tiền

Bài toán đổi tiền (Coin Change Problem) là một bài toán kinh điển trong khoa học máy tính, thường được định nghĩa như sau: Cho một tập hợp các mệnh giá tiền xu (ví dụ: {1, 2, 5}) và một tổng số tiền cần đổi (ví dụ: 11). Yêu cầu là tìm số lượng tiền xu tối thiểu cần thiết để tạo thành tổng số tiền đã cho. Giả sử rằng mỗi mệnh giá tiền xu có số lượng không giới hạn. Nếu không có cách nào để tạo ra tổng số tiền đó, kết quả trả về là -1.

Phương pháp 1: Thuật toán tham lam (Cách tiếp cận không chính xác)

Một trong những suy nghĩ đầu tiên khi đối mặt với bài toán này là áp dụng thuật toán tham lam. Ý tưởng cơ bản của phương pháp tham lam ở đây là luôn ưu tiên chọn đồng xu có mệnh giá lớn nhất có thể cho đến khi tổng số tiền đạt được hoặc vượt quá mục tiêu. Khi tổng vượt quá, đồng xu cuối cùng sẽ được loại bỏ và quá trình tiếp tục với các đồng xu có mệnh giá nhỏ hơn.

Tuy nhiên, thuật toán tham lam không hoạt động chính xác cho bài toán đổi tiền trong mọi trường hợp. Xem xét ví dụ sau: các mệnh giá tiền xu là {10, 4, 3} và tổng số tiền cần đổi là 19. Theo cách tiếp cận tham lam được mô tả trong mã nguồn bên dưới:

1. Chọn đồng 10. Tổng = 10, Số xu = 1.
2. Tiếp tục với đồng 10. Tổng = 20, Số xu = 2 (vượt quá 19).
3. Vì Tổng > 19, loại bỏ đồng 10 cuối cùng. Tổng = 10, Số xu vẫn là 2 (đây là một lỗi logic). Chuyển sang mệnh giá tiếp theo (4).
4. Với đồng 4: Tổng = 10 + 4 = 14, Số xu = 3.
5. Với đồng 4: Tổng = 14 + 4 = 18, Số xu = 4.
6. Với đồng 4: Tổng = 18 + 4 = 22, Số xu = 5 (vượt quá 19).
7. Vì Tổng > 19, loại bỏ đồng 4 cuối cùng. Tổng = 18, Số xu vẫn là 5. Chuyển sang mệnh giá tiếp theo (3).
8. Với đồng 3: Tổng = 18 + 3 = 21, Số xu = 6 (vượt quá 19).
9. Vì Tổng > 19, loại bỏ đồng 3 cuối cùng. Tổng = 18, Số xu vẫn là 6. Không còn mệnh giá nào.

Cuối cùng, thuật toán trả về -1, cho rằng không có giải pháp. Nhưng trên thực tế, có một giải pháp tối ưu là 10 + 3 + 3 + 3 = 19, chỉ với 4 đồng xu.

class CoinChangerGreedyAttempt {
public:
    int getMinCoins(std::vector<int>& availableCoins, int totalAmount) {
        // Sắp xếp các mệnh giá theo thứ tự giảm dần
        std::sort(availableCoins.begin(), availableCoins.end(), std::greater<int>()); 
        
        int currentTotal = 0;
        int countOfCoins = 0;
        int coinIdx = 0;

        // Đây là một cách triển khai thuật toán tham lam như đã mô tả,
        // nhưng có vấn đề về mặt logic và không đảm bảo kết quả tối ưu.
        while (coinIdx < availableCoins.size()) {
            // Liên tục thêm đồng xu hiện tại cho đến khi tổng đạt hoặc vượt quá mục tiêu
            while (currentTotal < totalAmount) {
                currentTotal += availableCoins[coinIdx];
                countOfCoins++;
            }

            if (currentTotal == totalAmount) {
                return countOfCoins;
            } else { // currentTotal > totalAmount, nghĩa là đã vượt quá
                // Gỡ bỏ đồng xu cuối cùng đã thêm của loại này.
                // LƯU Ý: Mã gốc không giảm 'countOfCoins' ở đây, 
                // đây là một phần nguyên nhân dẫn đến sai sót.
                currentTotal -= availableCoins[coinIdx]; 
                coinIdx++; // Chuyển sang mệnh giá nhỏ hơn tiếp theo
            }
        }
        return -1; // Không tìm thấy giải pháp nào với chiến lược tham lam này
    }
};

Ví dụ này minh họa rõ ràng rằng thuật toán tham lam, dù đơn giản, không đủ mạnh để giải quyết bài toán đổi tiền một cách chính xác trong mọi tình huống.

Phương pháp 2: Quay lui với cơ chế dừng sớm (Cách tiếp cận không tối ưu)

Một phương pháp khác là sử dụng quay lui (backtracking) để khám phá các tổ hợp đồng xu. Trong phương pháp này, chúng ta cố gắng xây dựng tổng số tiền bằng cách thử từng đồng xu. Một cải tiến thường được nghĩ đến là sử dụng một "cờ" hoặc biến toàn cục để báo hiệu rằng đã tìm thấy một giải pháp hợp lệ. Khi giải pháp đầu tiên được tìm thấy, chúng ta sẽ dừng tất cả các nhánh đệ quy khác và trả về kết quả đó, với giả định rằng đây là kết quả sớm nhất và có thể là tối ưu.

Tuy nhiên, cách tiếp cận này cũng có một lỗ hổng nghiêm trọng: việc tìm thấy giải pháp đầu tiên không đảm bảo đó là giải pháp tối ưu (tức là sử dụng số lượng đồng xu ít nhất). Ví dụ, với các mệnh giá {10, 7, 1} và tổng số tiền 14:

Nếu các đồng xu được sắp xếp giảm dần và quá trình quay lui bắt đầu:

1. Thử 10. Còn lại 4.
2. Để có 4, dùng 1 + 1 + 1 + 1 (4 đồng 1).
3. Tổng cộng: 10 + 1 + 1 + 1 + 1 = 14 (5 đồng xu).

Nếu cơ chế dừng sớm được kích hoạt ngay tại đây, nó sẽ trả về 5 đồng xu. Nhưng giải pháp tối ưu thực sự là 7 + 7 = 14, chỉ với 2 đồng xu.

class CoinChangerEarlyExit {
private:
    bool solutionFoundGlobally = false;
    int currentCoinsCount = 0;
    int firstFoundCoinCount = -1; // Lưu số lượng xu của giải pháp đầu tiên tìm được

    void explore(int currentIndex, int currentSum, int targetAmount, const std::vector<int>& denominations) {
        if (solutionFoundGlobally) { // Dừng ngay nếu đã tìm thấy giải pháp
            return;
        }
        if (currentSum == targetAmount) {
            solutionFoundGlobally = true;
            firstFoundCoinCount = currentCoinsCount;
            return;
        }
        // Cắt tỉa nhánh nếu tổng vượt quá mục tiêu
        if (currentSum > targetAmount) { 
            return;
        }

        for (int i = currentIndex; i < denominations.size(); ++i) {
            currentCoinsCount++;
            explore(i, currentSum + denominations[i], targetAmount, denominations);
            currentCoinsCount--; // Quay lui: hoàn tác lựa chọn đồng xu
            if (solutionFoundGlobally) { // Kiểm tra lại sau khi gọi đệ quy để đảm bảo dừng
                return;
            }
        }
    }

public:
    int getMinCoins(std::vector<int>& denominations, int targetAmount) {
        // Sắp xếp giảm dần có thể giúp tìm một giải pháp (chưa chắc tối ưu) nhanh hơn
        std::sort(denominations.begin(), denominations.end(), std::greater<int>()); 
        explore(0, 0, targetAmount, denominations);
        return firstFoundCoinCount;
    }
};

Rõ ràng, việc chỉ tìm giải pháp đầu tiên mà không khám phá đầy đủ các khả năng không đủ để đảm bảo kết quả tối ưu cho bài toán đổi tiền.

Phương pháp 3: Quay lui đầy đủ (Đúng logic nhưng độ phức tạp thời gian cao)

Để khắc phục các nhược điểm của hai phương pháp trên, chúng ta cần một phương pháp quay lui khám phá tất cả các tổ hợp có thể tạo ra tổng số tiền mong muốn và ghi lại số lượng đồng xu tối thiểu trong số đó. Phương pháp này về mặt lý thuyết là chính xác và sẽ luôn tìm ra câu trả lời đúng.

Mặc dù đúng về mặt logic, phương pháp quay lui đầy đủ có một nhược điểm lớn về hiệu suất. Với các tập dữ liệu lớn, số lượng các đường dẫn cần khám phá trong cây đệ quy có thể tăng theo cấp số nhân. Điều này thường dẫn đến vượt quá giới hạn thời gian (Time Limit Exceeded - TLE) trong các hệ thống đánh giá tự động như LeetCode. Ngay cả với các kỹ thuật cắt tỉa (pruning) cơ bản, độ phức tạp thời gian vẫn quá cao cho nhiều trường hợp kiểm thử.

Ví dụ, với đầu vào denominations = [411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422] và targetAmount = 9806, giải pháp đúng là 24. Một giải pháp quay lui đầy đủ sẽ tìm ra kết quả này nhưng có thể mất rất nhiều thời gian để hoàn thành.

#include <vector>
#include <algorithm>
#include <limits> // For std::numeric_limits

class CoinChangerFullBacktracking {
private:
    int currentCoinsUsed = 0;
    // Khởi tạo với giá trị số nguyên lớn nhất để đảm bảo mọi kết quả tìm được sẽ nhỏ hơn
    int minimumCoinsFound = std::numeric_limits<int>::max(); 

    void exploreCombinations(int startIndex, int currentTotal, int targetAmount, const std::vector<int>& denominations) {
        if (currentTotal == targetAmount) {
            minimumCoinsFound = std::min(minimumCoinsFound, currentCoinsUsed);
            return;
        }
        if (currentTotal > targetAmount) { // Cắt tỉa nhánh: tổng vượt quá mục tiêu
            return;
        }

        // Cắt tỉa bổ sung: nếu số lượng đồng xu hiện tại đã lớn hơn hoặc bằng
        // số lượng đồng xu tối thiểu đã tìm thấy, thì nhánh này không thể 
        // dẫn đến một giải pháp tốt hơn, do đó không cần tiếp tục.
        if (currentCoinsUsed >= minimumCoinsFound) {
            return;
        }

        for (int i = startIndex; i < denominations.size(); ++i) {
            currentCoinsUsed++;
            exploreCombinations(i, currentTotal + denominations[i], targetAmount, denominations);
            currentCoinsUsed--; // Quay lui: hoàn tác lựa chọn đồng xu
        }
    }

public:
    int calculateMinimumCoins(std::vector<int>& denominations, int targetAmount) {
        if (targetAmount < 0) return -1;
        if (targetAmount == 0) return 0;

        // Sắp xếp giảm dần có thể giúp tìm các giải pháp có ít đồng xu hơn nhanh hơn
        // trong một số trường hợp, nhưng không làm thay đổi độ phức tạp tổng thể của quay lui.
        std::sort(denominations.begin(), denominations.end(), std::greater<int>());
        
        exploreCombinations(0, 0, targetAmount, denominations);
        
        // Nếu minimumCoinsFound vẫn là giá trị khởi tạo, nghĩa là không tìm thấy tổ hợp nào
        if (minimumCoinsFound == std::numeric_limits<int>::max()) {
            return -1;
        } else {
            return minimumCoinsFound;
        }
    }
};

Mặc dù giải pháp quay lui đầy đủ này về mặt lý thuyết là chính xác, độ phức tạp thời gian theo cấp số nhân của nó làm cho nó không phù hợp cho các bài toán đổi tiền với kích thước lớn. Để giải quyết bài toán này một cách hiệu quả trong thực tế, các kỹ thuật tối ưu hóa như quy hoạch động (dynamic programming) thường được sử dụng.