硬幣找零優化

Question

我試圖解決這個問題：

假設我有一組N個硬幣{A_1，A2，...，A_N}。總是會出現一個值爲 1的硬幣。 I 需要達到M的最小數量的硬幣是多少？

約束條件是：

• 1≤N≤25
• 1≤米≤10^6
• 1≤A_I≤100

好的，我知道這是改變的問題。 我試圖解決這個問題，使用廣度優先搜索，動態編程和貪婪（這是不正確的，因爲它並不總是提供最佳的解決方案）。但是，我得到超時限制（3秒）。

所以我想知道是否有這個問題的優化。 描述和約束稱爲我的注意，但我不知道如何使用它對我有利：

• 總是會出現值爲1的硬幣。
• 1≤A_I≤100

我在維基百科看到，這個問題也可以通過「與概率卷積樹動態規劃」來解決。但我什麼都聽不懂。

你能幫我嗎？ 這個問題可以在這裏找到：http://goo.gl/nzQJem

Answer 1

讓a_n是最大的硬幣。使用這兩個線索：

• 結果是>= ceil(M/a_n)，
• 結果的配置有很多a_n's。

最好是嘗試用最大的a_n's比檢查它是否是用更少的a_n's更好的結果，直到它有可能找到更好的結果。

類似於：let R({a_1, ..., a_n}, M)是返回給定問題結果的函數。比R可以執行：

num_a_n = floor(M/a_n) 
best_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n) 
while num_a_n > 0: 
    num_a_n = num_a_n - 1 
    # Check is it possible at all to get better result 
    if num_a_n + ceil(M-a_n*num_a_n/a_(n-1)) >= best_r: 
    return best_r 
    next_r = num_a_n + R({a_1, ..., a_(n-1)}, M-a_n*num_a_n) 
    if next_r < best_r: 
    best_r = next_r 
return best_r