硬幣改變算法

假設我有一組面額爲a1，a2，... ak的硬幣。硬幣改變算法

其中之一被稱爲是等於1

我想做出改變使用硬幣的最低數量的所有整數1到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.

注：不做作業只是this問題

來源

2009-12-31 Rohit Banga

+10

幫助某個人解決一個家庭作業問題並不會突然讓他們成爲A +學生。在某些情況下，這可能會幫助學生「看清光明」，併成長爲一位聰明的年輕開發人員。然而，重複這種行爲的人（不是試圖自己解決問題）更可能是一個永遠不會成長的人，因爲他們不會挑戰自己。他們會在某個時候崩潰並燒傷，很可能是考試當天。至少在我上學的地方，考試是我們成績中如此之大的一部分，以至於作業實際上是無關緊要的（在一門課程考試中是100％）。 – jason 2009-12-31 20:13:13

這是一個典型的動態規劃問題的修改（首先注意到的貪心算法並不總是在這裏工作！）。

假定硬幣被排序使得a_1 > a_2 > ... > a_k = 1。我們定義一個新問題。我們說(i, j)的問題是使用硬幣a_i > a_(i + 1) > ... > a_k找到爲j進行更改的最小硬幣數量。我們希望解決的問題是(1, j)對於任何j與1 <= j <= n。說C(i, j)是(i, j)問題的答案。

現在，考慮一個實例(i, j)。我們必須決定是否使用a_i硬幣中的一種。如果我們不是，我們只是解決(i + 1, j)問題，答案是C(i + 1, j)。如果是，我們通過更改j - a_i來完成解決方案。要儘可能使用盡可能少的硬幣，我們要解決(i, j - a_i)問題。我們安排的事情讓這兩個問題都已經解決了我們，然後：

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

現在找出最初的案件，以及如何這個翻譯成你所選擇的語言，你應該是好去。

如果你想試試你的手在需要動態編程另一個有趣的問題，看看項目歐拉Problem 67。

來源

2009-12-31 19:46:59 jason

爲什麼不貪婪的方法總是工作，我不明白？ – hhafez 2009-12-31 19:51:30

@hhafez：考慮給予'30，'給定幣種{1,10,20,25'}的硬幣。貪婪算法產生「{25,1,1,1,1,1}」，但最優解爲「{20，10}」。我認爲貪婪算法確實有效的硬幣套的術語是「友善的硬幣套」。確定一個硬幣是否友善是一個有趣的問題。我可以說這個詞是錯的，但這個問題無論哪種方式都很有趣。 – jason 2009-12-31 19:52:02

非常感謝您的解釋 – hhafez 2009-12-31 19:57:43

以下是Python中動態編程算法的示例實現。它比Jason所描述的算法簡單，因爲它只計算他描述的2D表的1行。

請注意，使用此代碼騙功課會讓殭屍的Dijkstra哭。

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)

來源

2009-12-31 21:41:25 RossFabricant

硬幣改變算法

回答

相關問題