什麼是使用動態編程輸出解決方案的好技術？

這個問題專門針對硬幣更換問題。我知道的算法來找到用於查找任何金額變更的硬幣的最佳數量，我也明白，但我不明白的是我怎麼可能「標誌」，如果你將採取的路徑找到這樣的解決方案。我試圖使用父指針，我相信是這樣做的方式，但我根本不知道如何實現它。這是一個例子。例子：給出硬幣面值：1，10，25 變化：30 最佳解決方案要求：3枚硬幣使用金幣：10，10，10什麼是使用動態編程輸出解決方案的好技術？

我不是真的那麼好於解決動態規劃問題。

來源

2013-05-08 Sektrax

假設你知道到29你怎麼可以用它來尋找解決方案30對1最優解？ – ElKamina 2013-05-08 23:54:21

對不起，我忘了讓你們知道我目前解決這個問題的方法只存在於一個數組中，我不是在製作表格。所以我從1 - 29的解決方案，但使用的硬幣數量，而不是哪個硬幣。我很抱歉，如果這應該是直觀的，但它真的不是我。我想我的問題是：如果我要實現與從0到n爲1行和硬幣面值金額二維表以K爲列，這將是各單元格的值，我將如何計算呢？ – Sektrax 2013-05-08 23:57:43

你可以更有效地解決它。保留一個指向前一個最優解的指針，從中獲得當前最優解。例如。 10有一個鏈接到零。 20個鏈接到10個，30個鏈接到20個。現在你所要做的就是回溯。 30的鏈接是20，所以是30-20 = 10，20的鏈接是10-> 20-10 = 10和10-0 = 10。這就是你如何得到3 10 – ElKamina 2013-05-09 00:07:35

你知道T [30] = 3。你必須找到一個T [30-c] = 2，嘗試{1,10,25}中的所有c。由於T [30-10] = 2，你知道你會使用10美分的硬幣，現在必須解決T的問題[20]。

重複，直到T [0] = 0

來源

2013-05-09 03:19:59

什麼是使用動態編程輸出解決方案的好技術？

回答

相關問題