Q
硬幣改變算法
10
A
回答
21
這是一個典型的動態規劃問題的修改(首先注意到的貪心算法並不總是在這裏工作!)。
假定硬幣被排序使得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。
0
以下是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)
相關問題
- 1. 硬幣更改算法
- 2. 硬幣更改貪婪算法
- 3. 跟蹤遞歸硬幣更改算法
- 4. 硬幣算法優化
- 5. 硬幣改變算法:爲什麼加1?
- 6. 如何解釋這個硬幣改變算法
- 7. 貪心算法和硬幣算法
- 8. 快速硬幣更換算法最多3個硬幣在C
- 9. 在C++硬幣更改算法中計算錯誤
- 10. 使用動態編程改變硬幣
- 11. 用硬幣遊戲的算法
- 12. DP硬幣找零算法 - 從表
- 13. 貪婪算法硬幣更換C++
- 14. 硬幣找零算法動態規劃
- 15. 硬幣變化的變化
- 16. 不清楚爲什麼這個硬幣更改算法工作
- 17. 硬幣更改算法 - DP與1D陣列
- 18. 用有限的硬幣進行改變的分而治之算法
- 19. 硬幣更改:貪婪的方法
- 20. 硬幣更改記憶
- 21. 硬幣變化分析
- 22. 硬幣
- 23. 硬幣找零,但只有硬幣
- 24. 遞歸計算硬幣支付組合
- 25. 如何計算硬幣數量的變化? 「
- 26. 遞歸邏輯計算硬幣變化/足球比分
- 27. 如何判斷貪婪算法是否足以找到最小硬幣更改?
- 28. 硬幣兌換
- 29. 動態變化的決策算法,返回用於硬幣的實際列表
- 30. 如何計算連續硬幣投幣頭
幫助某個人解決一個家庭作業問題並不會突然讓他們成爲A +學生。在某些情況下,這可能會幫助學生「看清光明」,併成長爲一位聰明的年輕開發人員。然而,重複這種行爲的人(不是試圖自己解決問題)更可能是一個永遠不會成長的人,因爲他們不會挑戰自己。他們會在某個時候崩潰並燒傷,很可能是考試當天。至少在我上學的地方,考試是我們成績中如此之大的一部分,以至於作業實際上是無關緊要的(在一門課程考試中是100%)。 – jason 2009-12-31 20:13:13