硬幣找零（動態規劃）

我們通常爲硬幣找零問題如下遞推關係：（P是我們需要改變，d_i的總金額可在硬幣）硬幣找零（動態規劃）

但不能我們做出這樣的：（V是給定排序的錢幣可用，i和j是其下標與Vj報錯的最高值硬幣）

C[p,Vi,j] = C[p,Vi,j-1]  if Vj > p 
      = C[p-Vj,Vi,j] + 1 if Vj <=p

我寫的東西有什麼不對嗎？雖然解決方案不是動態的，但效率更高嗎？

2012-10-25 Gaurav

這不是假設V將包含一個價值1個單位的硬幣。如果P = 7並且V = [3,2]，那麼最終得到2個值爲3的硬幣，然後出錯而不是1個值3硬幣和2個值2硬幣。 –

@LastCoder我明白了你的觀點。上述解決方案假設我們有一個值得1個單位的硬幣。現在接下來的事情是，如果我們給硬幣值1個單位，那麼上面是更有效的解決方案，然後動態的解決方案，對嗎？ – Gaurav

你在公式中使用「Vi」？ – IVlad

考慮P = 6, V = {4, 3, 1}。你會選擇4, 1, 1而不是3, 3，所以3硬幣而不是最佳的2。

2012-10-25 19:11:19 IVlad

謝謝。這解決了我的問題。 – Gaurav

你寫的是類似於只在某些條件下工作的貪婪算法。（見 - How to tell if greedy algorithm suffices for finding minimum coin change?）。

而且，在你的版本中，你實際上並沒有使用Vi復發內，所以它只是一個浪費內存

2012-10-25 19:09:31 dfb

回答