Thuật toán thay đổi tiền xu

Question

Giả sử tôi có một tập hợp các đồng tiền có mệnh giá a1, a2, ... ak.

Một trong số đó được biết đến là bằng 1.

Tôi muốn thực hiện thay đổi cho tất cả các số nguyên từ 1 tới n sử dụng số lượng tối thiểu của tiền xu.

Bất kỳ ý tưởng nào cho thuật toán.

eg. 1, 3, 4 coin denominations 
n = 11 
optimal selection is 3, 0, 2 in the order of coin denominations. 

n = 12 
optimal selection is 2, 2, 1. 

Lưu ý: không làm bài tập chỉ là một sửa đổi của this vấn đề

Answer 1

Đây là một vấn đề lập trình năng động cổ điển (lưu ý đầu tiên rằng các thuật toán tham lam không phải lúc nào làm việc ở đây!).

Giả sử tiền xu được đặt hàng để a_1 > a_2 > ... > a_k = 1. Chúng tôi xác định một vấn đề mới. Chúng tôi nói rằng vấn đề (i, j) là tìm số tiền tối thiểu thực hiện thay đổi cho j sử dụng tiền xu a_i > a_(i + 1) > ... > a_k. Vấn đề chúng tôi muốn giải quyết là (1, j) đối với bất kỳ j nào với 1 <= j <= n. Giả sử rằng C(i, j) là câu trả lời cho vấn đề (i, j).

Bây giờ, hãy xem xét một cá thể (i, j). Chúng ta phải quyết định liệu chúng ta có đang sử dụng một trong số tiền a_i không. Nếu không, chúng tôi chỉ giải quyết một vấn đề (i + 1, j) và câu trả lời là C(i + 1, j). Nếu có, chúng tôi hoàn thành giải pháp bằng cách thực hiện thay đổi cho j - a_i. Để làm điều này bằng cách sử dụng càng ít tiền càng tốt, chúng tôi muốn giải quyết vấn đề (i, j - a_i). Chúng tôi sắp xếp mọi thứ để hai vấn đề này đã được giải quyết cho chúng tôi và sau đó:

C(i, j) = C(i + 1, j)       if a_i > j 
     = min(C(i + 1, j), 1 + C(i, j - a_i)) if a_i <= j 

Bây giờ hãy tìm hiểu xem trường hợp ban đầu là gì và cách dịch sang ngôn ngữ bạn chọn và bạn nên làm tốt.

Nếu bạn muốn thử sức với một vấn đề thú vị khác yêu cầu lập trình động, hãy xem Project Euler Problem 67.

Answer 2

Dưới đây là triển khai mẫu của thuật toán lập trình động trong Python. Nó đơn giản hơn thuật toán Jason mô tả, bởi vì nó chỉ tính toán 1 hàng của bảng 2D mà anh ta mô tả.

Xin lưu ý rằng việc sử dụng mã này để lừa dối bài tập về nhà sẽ làm cho Zombie Dijkstra khóc.

import sys 
def get_best_coins(coins, target): 
    costs = [0] 
    coins_used = [None] 
    for i in range(1,target + 1): 
     if i % 1000 == 0: 
      print '...', 
     bestCost = sys.maxint 
     bestCoin = -1 
     for coin in coins: 
      if coin <= i: 
       cost = 1 + costs[i - coin] 
       if cost < bestCost: 
        bestCost = cost 
        bestCoin = coin 
     costs.append(bestCost) 
     coins_used.append(bestCoin) 
    ret = []  
    while target > 0: 
     ret.append(coins_used[target]) 
     target -= coins_used[target] 
    return ret 

coins = [1,10,25] 
target = 100033 
print get_best_coins(coins, target)