Cài đặt thuật toán Coin Change Problem trong lập trình

Thuật toán Coin Change Problem là một bài toán kinh điển trong lý thuyết thuật toán và lập trình, được sử dụng rộng rãi trong các vấn đề liên quan đến tối ưu hóa, lập trình động và lý thuyết đồ thị. Mục tiêu của bài toán là tìm ra cách tốt nhất để đổi một số tiền nhất định bằng cách sử dụng ít đồng xu nhất từ một tập hợp các mệnh giá đồng xu đã cho trước.

Để giải quyết vấn đề này, có nhiều cách tiếp cận khác nhau. Trong bài viết này, chúng ta sẽ xem xét hai phương pháp chính: sử dụng lập trình động và sử dụng đệ quy có ghi nhớ.

Phương pháp 1: Lập trình động

Lập trình động là một kỹ thuật tuyệt vời để giải quyết bài toán này vì nó giúp chúng ta tối ưu hóa các tính toán bằng cách lưu trữ kết quả của các phép tính trước đó để tái sử dụng trong tương lai.

Các bước thực hiện:

1. Khởi tạo một mảng dp: Ban đầu, tạo một mảng dp với kích thước là số tiền cần đổi + 1. Giá trị của dp[i] sẽ biểu thị số lượng ít nhất các đồng xu cần để tạo ra số tiền i.

2. Giá trị khởi đầu: Khởi tạo dp[0] = 0 vì không cần đồng xu nào để tạo ra số tiền 0. Tất cả các giá trị còn lại trong dp sẽ được khởi tạo bằng một số lớn (vô cùng).

3. Duyệt qua các mệnh giá: Duyệt qua mỗi mệnh giá trong tập hợp các đồng xu. Với mỗi mệnh giá, cập nhật mảng dp dựa trên các giá trị đã tính toán trước đó.

4. Trả kết quả: Giá trị cuối cùng của dp[số tiền cần đổi] sẽ là kết quả cần tìm. Nếu giá trị này vẫn là số lớn (vô cùng), điều đó có nghĩa là không thể đổi được số tiền đó bằng các đồng xu có sẵn.

Mã nguồn minh họa bằng Python:

def coin_change(coins, amount):
    # Khởi tạo mảng dp với số lượng lớn
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    # Duyệt qua các mệnh giá đồng xu
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

# Ví dụ sử dụng
coins = [1, 2, 5]
amount = 11
print(coin_change(coins, amount))  # Output: 3 (11 = 5 + 5 + 1)

Phương pháp 2: Đệ quy có ghi nhớ

Phương pháp đệ quy có ghi nhớ cũng là một cách hiệu quả để giải quyết bài toán này, đặc biệt khi chúng ta muốn tận dụng lại các kết quả tính toán trước đó.

Các bước thực hiện:

1. Tạo một hàm đệ quy: Hàm này sẽ trả về số lượng ít nhất các đồng xu cần để đổi một số tiền nhất định.

2. Ghi nhớ các kết quả trung gian: Sử dụng một từ điển (dictionary) để lưu trữ các kết quả đã tính toán trước đó nhằm tránh các phép tính lặp lại.

3. Trả kết quả: Hàm đệ quy sẽ trả về số lượng ít nhất các đồng xu cần hoặc -1 nếu không thể đổi được số tiền đó.

Mã nguồn minh họa bằng Python:

def coin_change_recursive(coins, amount, memo={}):
    if amount in memo:
        return memo[amount]
    if amount == 0:
        return 0
    if amount < 0:
        return -1

    min_coins = float('inf')
    for coin in coins:
        res = coin_change_recursive(coins, amount - coin, memo)
        if res >= 0 and res < min_coins:
            min_coins = res + 1
            
    memo[amount] = min_coins if min_coins != float('inf') else -1
    return memo[amount]

# Ví dụ sử dụng
coins = [1, 2, 5]
amount = 11
print(coin_change_recursive(coins, amount))  # Output: 3 (11 = 5 + 5 + 1)

Kết luận

Cả hai phương pháp lập trình động và đệ quy có ghi nhớ đều là các kỹ thuật hiệu quả để giải quyết bài toán Coin Change Problem. Tùy thuộc vào yêu cầu và giới hạn của bài toán mà người lập trình có thể chọn phương pháp phù hợp. Lập trình động thường được ưa chuộng hơn trong các tình huống yêu cầu tối ưu hóa về thời gian tính toán. Trong khi đó, đệ quy có ghi nhớ giúp việc cài đặt dễ dàng và trực quan hơn.