Bài toán Đổi tiền (Coin Change)

Giới thiệu

Bài toán đổi tiền (Coin Change) được đưa ra như sau: Cho một số tiền và một tập hợp các đồng xu, hãy tìm số đồng xu ít nhất cần để đổi số tiền đó. Đây là một bài toán quen thuộc trong lĩnh vực tối ưu hóa.

Các thuật toán

Có nhiều thuật toán khác nhau để giải quyết bài toán đổi tiền. Dưới đây là một số thuật toán phổ biến để giải bài toán này:

  1. Thuật toán tham lam (Greedy algorithm): Lựa chọn đồng xu lớn nhất có thể cho đến khi số tiền cần đổi bằng 0. Thuật toán này thường cho kết quả tối ưu nếu tập hợp các đồng xu đó là tập hợp đồng quy đổi được.

  2. Thuật toán quy hoạch động (Dynamic programming algorithm): Sử dụng bảng tính giá trị tối thiểu để đổi số tiền từ 0 đến số tiền cần đổi. Giải thuật này cho kết quả chính xác tối thiểu, tuy nhiên độ phức tạp tính toán có thể cao đối với số tiền và số lượng đồng xu lớn.

  3. Thuật toán nhánh cận (Branch and Bound algorithm): Tạo một cây tìm kiếm để liệt kê tất cả các khả năng đổi tiền, loại bỏ các phương án không tối ưu. Giải thuật này cho kết quả chính xác tối thiểu, tuy nhiên độ phức tạp tính toán có thể rất cao đối với số lượng đồng xu lớn.

  4. Thuật toán quy hoạch động phiên bản cải tiến (Improved dynamic programming algorithm): Sử dụng phương pháp đệ quy với kỹ thuật lưu trữ kết quả tính toán để tránh tính toán lại các giá trị đã tính. Thuật toán này cho kết quả chính xác tối thiểu với độ phức tạp tính toán tương đối thấp.

  5. Thuật toán phân tích tiền tệ (Change-making algorithm): Sử dụng phương pháp giải quyết bài toán tối thiểu hoá số đồng xu để đổi số tiền, với giả định tất cả các đồng xu đều có giá trị là lũy thừa của một số nguyên tố cơ bản. Thuật toán này cho kết quả chính xác tối thiểu với độ phức tạp tính toán tương đối thấp.

Độ phức tạp của mỗi thuật toán đối với bài toán đổi tiền (Coin Change) được tính theo độ phức tạp thời gian và độ phức tạp không gian.

  1. Thuật toán tham lam (Greedy algorithm): Độ phức tạp thời gian là O(n), trong đó n là số lượng đồng xu cần đổi. Độ phức tạp không gian là O(1), vì không cần lưu trữ bảng giá trị tối thiểu.

  2. Thuật toán quy hoạch động (Dynamic programming algorithm): Độ phức tạp thời gian là O(nm), trong đó n là số tiền cần đổi và m là số lượng đồng xu có sẵn. Độ phức tạp không gian là O(n), vì cần lưu trữ bảng giá trị tối thiểu từ 0 đến số tiền cần đổi.

  3. Thuật toán nhánh cận (Branch and Bound algorithm): Độ phức tạp thời gian và không gian phụ thuộc vào số lượng đồng xu có sẵn và số tiền cần đổi. Với số lượng đồng xu và số tiền cần đổi lớn, độ phức tạp của thuật toán này có thể rất cao.

  4. Thuật toán quy hoạch động phiên bản cải tiến (Improved dynamic programming algorithm): Độ phức tạp thời gian là O(nm), nhưng sử dụng kỹ thuật lưu trữ kết quả tính toán để tránh tính toán lại các giá trị đã tính, vì vậy độ phức tạp không gian chỉ là O(n).

  5. Thuật toán phân tích tiền tệ (Change-making algorithm): Độ phức tạp thời gian là O(nm), trong đó n là số tiền cần đổi và m là số lượng đồng xu có sẵn. Độ phức tạp không gian là O(n), vì cần lưu trữ bảng giá trị tối thiểu từ 0 đến số tiền cần đổi.

Cài đặt thuật toán

Ở đây ta phân tích và cài đặt thuật toán quy hoạch động. Thuật toán quy hoạch động (Dynamic Programming – DP) được áp dụng trong nhiều bài toán, trong đó bài toán đổi tiền (Coin Change) là một ví dụ điển hình. Các bước thực hiện thuật toán quy hoạch động bao gồm:

  1. Định nghĩa bài toán: Phân tích bài toán thành các phần nhỏ hơn để dễ dàng giải quyết. Trong trường hợp bài toán đổi tiền, ta cần tính số đồng tiền tối thiểu để đổi một số tiền cụ thể.

  2. Xác định trạng thái: Xác định trạng thái là thông tin cần thiết để tính toán kết quả cho bài toán. Trong trường hợp bài toán đổi tiền, trạng thái là số tiền cần đổi.

  3. Xác định trạng thái ban đầu: Khởi tạo trạng thái ban đầu để bắt đầu tính toán. Trong trường hợp bài toán đổi tiền, trạng thái ban đầu là số tiền cần đổi bằng 0.

  4. Xác định công thức truy hồi: Từ trạng thái hiện tại, tính toán giá trị cho trạng thái kế tiếp bằng công thức truy hồi. Trong trường hợp bài toán đổi tiền, công thức truy hồi là dp[i] = min(dp[i], dp[i - coins[j]] + 1) với dp[i] là số đồng tiền tối thiểu cần để đổi số tiền i, coins[j] là đồng tiền mệnh giá j.

  5. Xác định điều kiện dừng: Xác định điều kiện để dừng tính toán. Trong trường hợp bài toán đổi tiền, điều kiện dừng là khi tính toán xong số đồng tiền tối thiểu cần để đổi số tiền amount.

  6. Truy vết kết quả: Nếu cần, ta có thể sử dụng các giá trị tính toán được trước đó để truy vết lại kết quả cuối cùng.

  7. Tính toán và trả về kết quả: Tính toán và trả về kết quả cuối cùng.

Các bước thực hiện thuật toán quy hoạch động thường được lặp đi lặp lại cho đến khi tính toán được giá trị kết quả cuối cùng. Trong trường hợp bài toán đổi tiền, ta duyệt qua từng mệnh giá đồng tiền và cập nhật bảng DP để tính toán số đồng tiền tối thiểu cần để đổi số tiền amount. Cụ thể, các bước thực hiện thuật toán quy hoạch động trong bài toán đổi tiền có thể được trình bày như sau:

  1. Định nghĩa bài toán: Tính số đồng tiền tối thiểu cần để đổi một số tiền cụ thể bằng cách sử dụng các đồng tiền có sẵn.

  2. Xác định trạng thái: Số tiền cần đổi.

  3. Xác định trạng thái ban đầu: Số đồng tiền tối thiểu cần để đổi số tiền bằng 0.

  4. Xác định công thức truy hồi: dp[i] = min(dp[i], dp[i - coins[j]] + 1) với dp[i] là số đồng tiền tối thiểu cần để đổi số tiền i, coins[j] là đồng tiền mệnh giá j.

  5. Xác định điều kiện dừng: Tính toán xong số đồng tiền tối thiểu cần để đổi số tiền amount.

  6. Truy vết kết quả: Không cần thiết trong trường hợp này.

  7. Tính toán và trả về kết quả: Số đồng tiền tối thiểu cần để đổi số tiền amount.

Cài đặt bài toán với ngôn ngữ lập trình Python

def coin_change(coins, amount):
    """
    Giải bài toán đổi tiền với số lượng đồng xu có sẵn trong mảng `coins`, để đổi số tiền `amount`.
    """
    # Tạo ma trận DP có kích thước (len(coins) + 1) x (amount + 1)
    dp = [[0] * (amount + 1) for _ in range(len(coins) + 1)]
    # Thiết lập giá trị cơ sở của ma trận,
    # nếu đổi số tiền 0, thì không cần dùng đồng xu nào cả
    for i in range(len(coins) + 1):
        dp[i][0] = 0
    # Bắt đầu tính toán giá trị của từng ô trong ma trận
    for i in range(1, len(coins) + 1):
        for j in range(1, amount + 1):
            # Nếu đồng xu `i-1` lớn hơn số tiền cần đổi,
            # ta chỉ cần dùng các đồng xu trước đó (i-1)
            if coins[i-1] > j:
                dp[i][j] = dp[i-1][j]
            # Ngược lại, ta cân nhắc sử dụng đồng xu `i-1`
            # để đổi số tiền còn lại (j - coins[i-1])
            # và lấy kết quả nhỏ nhất của ba trường hợp:
            # không sử dụng đồng xu `i-1`, sử dụng một lần đồng xu `i-1`
            # hoặc sử dụng nhiều lần đồng xu `i-1`
            else:
                dp[i][j] = min(dp[i-1][j], 1 + dp[i][j-coins[i-1]])
    # Kết quả nằm ở ô cuối cùng của ma trận
    if dp[len(coins)][amount] == float("inf"):
        return -1
    return dp[len(coins)][amount]

Cài đặt bài toán với ngôn ngữ lập trình C++

#include <iostream>
#include <vector>
#include <climits>

int coin_change(std::vector<int>& coins, int amount) {
    // Tạo ma trận DP có kích thước (coins.size() + 1) x (amount + 1)
    std::vector<std::vector<int>> dp(coins.size() + 1, std::vector<int>(amount + 1, 0));
    // Thiết lập giá trị cơ sở của ma trận,
    // nếu đổi số tiền 0, thì không cần dùng đồng xu nào cả
    for (int i = 0; i <= coins.size(); i++) {
        dp[i][0] = 0;
    }
    // Bắt đầu tính toán giá trị của từng ô trong ma trận
    for (int i = 1; i <= coins.size(); i++) {
        for (int j = 1; j <= amount; j++) {
            // Nếu đồng xu `i-1` lớn hơn số tiền cần đổi,
            // ta chỉ cần dùng các đồng xu trước đó (i-1)
            if (coins[i-1] > j) {
                dp[i][j] = dp[i-1][j];
            }
            // Ngược lại, ta cân nhắc sử dụng đồng xu `i-1`
            // để đổi số tiền còn lại (j - coins[i-1])
            // và lấy kết quả nhỏ nhất của ba trường hợp:
            // không sử dụng đồng xu `i-1`, sử dụng một lần đồng xu `i-1`
            // hoặc sử dụng nhiều lần đồng xu `i-1`
            else {
                dp[i][j] = std::min(dp[i-1][j], 1 + dp[i][j-coins[i-1]]);
            }
        }
    }
    // Kết quả nằm ở ô cuối cùng của ma trận
    if (dp[coins.size()][amount] == INT_MAX) {
        return -1;
    }
    return dp[coins.size()][amount];
}

int main() {
    std::vector<int> coins = {1, 2, 5};
    int amount = 11;
    int min_coins = coin_change(coins, amount);
    std::cout << "Số đồng xu ít nhất cần để đổi " << amount << " đồng là: " << min_coins << std::endl;
    return 0;
}

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *