×

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

Avatar of admin
admin 0 Views

Thuật toán Coin Change là một trong những bài toán kinh điển trong lĩnh vực thuật toán và lập trình. Mục đích của nó là xác định cách chia một số tiền cụ thể thành các mệnh giá (coin denominations) nhỏ nhất có thể. Hôm nay, chúng ta sẽ xem xét việc cài đặt phương pháp tham lam (Greedy) cho bài toán này.

Phương pháp tham lam thực hiện các lựa chọn cục bộ tối ưu tại mỗi bước với hi vọng rằng cuối cùng sẽ đi đến tổng thể tối ưu. Đối với bài toán Coin Change, điều này có nghĩa là ở mỗi bước, ta sẽ cố gắng sử dụng mệnh giá lớn nhất có thể.

Bước 1: Xác định yêu cầu và chuẩn bị dữ liệu

Giả sử ta có một list các mệnh giá coins = [1, 5, 10, 25] và số tiền cần chia amount = 63. Mục tiêu là xác định số lượng ít nhất các đồng xu để đạt được tổng số tiền là 63.

Bước 2: Xây dựng thuật toán

Thuật toán cơ bản theo phương pháp tham lam sẽ như sau:

  1. Khởi tạo một biến để lưu số lượng đồng xu cần thiết, ban đầu đặt bằng 0.
  2. Sắp xếp các mệnh giá coins theo thứ tự giảm dần.
  3. Với mỗi mệnh giá trong coins:
    • Chia số tiền remaining_amount cho mệnh giá hiện tại để tính số lượng đồng xu của mệnh giá đó cần dùng.
    • Cộng số lượng đồng xu này vào kết quả tổng.
    • Trừ giá trị của các đồng xu này khỏi remaining_amount.
  4. Lặp lại cho đến khi remaining_amount là 0.

Bước 3: Viết mã lệnh

Dưới đây là một ví dụ về cách cài đặt thuật toán này bằng ngôn ngữ Python:

def coin_change_greedy(coins, amount):
    """
    coins: List of coin denominations.
    amount: The total amount of money.
    Returns the minimum number of coins that make up that amount.
    """
    # Sắp xếp mệnh giá theo thứ tự giảm dần
    coins.sort(reverse=True)
    
    total_coins = 0
    remaining_amount = amount
    
    for coin in coins:
        if remaining_amount == 0:
            break
        # Số lượng đồng xu của mệnh giá hiện tại cần dùng
        num_coins = remaining_amount // coin
        total_coins += num_coins
        # Cập nhật số tiền còn lại
        remaining_amount -= num_coins * coin
        
    return total_coins

# Ví dụ chạy thử
coins = [1, 5, 10, 25]
amount = 63
print(coin_change_greedy(coins, amount))  # Output: 5

Bước 4: Kiểm tra và đánh giá

Cần thận trọng rằng phương pháp tham lam không phải lúc nào cũng đưa ra kết quả tối ưu cho mọi tập hợp mệnh giá. Để đảm bảo độ chính xác, nên kiểm thử với nhiều bộ dữ liệu khác nhau.

Kết luận

Cài đặt thuật toán Coin Change (Greedy) rất đơn giản và hiệu quả đối với nhiều tập hợp mệnh giá. Tuy nhiên, nó có thể không luôn đưa ra kết quả tối ưu cho mọi trường hợp, vì vậy đôi khi cần sử dụng các thuật toán khác như Quy Hoạch Động (Dynamic Programming) để đạt được kết quả tốt hơn. Việc hiểu được giới hạn và khả năng ứng dụng của các thuật toán khác nhau là một kỹ năng quan trọng trong lập trình và thiết kế thuật toán.

Comments

Bài viết liên quan