所有的解決方案，以改變與動態規劃

我審查我的講義爲我們的算法類使我開始思考這個問題：所有的解決方案，以改變與動態規劃

鑑於不同類型具有不同值的硬幣，發現所有的硬幣配置加起來達到一定數量而不重複。

在上課期間，我們解決了這個問題，找到一個總和的所有可能方法的數量和最少數量的硬幣。但是，我們從來沒有試圖找到解決方案。

我在考慮用動態規劃解決這個問題。

我帶着遞歸版本（爲簡單起見，我只打印解決方案）：

void solve(vector<string>& result, string& currSoln, int index, int target, vector<int>& coins) 
{ 
    if(target < 0) 
    { 
     return; 
    } 

    if(target == 0) 
    { 
     result.push_back(currSoln); 
    } 

    for(int i = index; i < coins.size(); ++i) 
    { 
     stringstream ss; 
     ss << coins[i]; 
     string newCurrSoln = currSoln + ss.str() + " "; 
     solve(result, newCurrSoln, i, target - coins[i], coins); 
    } 
}

但是，試圖利用DP來解決這個問題，當我卡住了。我有兩個主要障礙：

我不知道我應該用什麼數據結構來存儲以前的答案
我不知道我的自下而上的程序（使用循環來代替遞歸）應看起來像。

歡迎任何幫助，一些代碼將不勝感激！

謝謝你的時間。

來源

2014-08-27 Tianyu Lang

如果您可以針對此問題使用動態編程，那麼對我來說這並不是顯而易見的。如果我找到五十分之一，則增加四分之一，然後對25分錢進行「遞歸」，找到一分之五和五分之一的鎳幣。然後我回到開始，嘗試5個鎳幣，然後檢查25cents的結果，找到2個解決方案，所以我說總共有4個解決方案。但是1季度5個鎳幣和5個鎳幣+ 1個季度是重複的。 – 2014-08-27 18:28:26

可以有多種可能的解決方案來改變製作方式，所以DP會有所幫助，但可能還需要很長時間才能完成。你還好嗎？ – templatetypedef 2014-08-27 18:31:07

我寫了一個天真的版本比較：http：//coliru.stacked-crooked.com/a/d2c06ff6aa2ea45a – 2014-08-27 18:55:33

在一個dp解決方案中，您生成一組中間狀態，以及有多少種方式到達那裏。那麼你的答案就是成功狀態下的數字。

因此，對於更改計數，狀態是您已達到特定的變化量。計數是改變方式的數量。成功的狀態是你做出了正確的改變。

要從計數解決方案到枚舉它們，您需要保持這些中間狀態，並且還要記錄轉換到該狀態的所有狀態的每個狀態 - 以及關於如何執行的信息。（在更改計數的情況下，您將如何添加硬幣）

現在，您可以從成功狀態開始，通過dp數據結構遞歸地往回實際找到解決方案比計數。好消息是你所有的遞歸工作都是高效的 - 你總是隻看着成功的路徑，所以不要浪費時間在不起作用的事情上。但是如果有十億個解決方案，那麼沒有什麼皇家捷徑可以快速打印十億個解決方案。

但是，如果你希望有一點聰明，你可以把它變成一個可用的枚舉。例如，你可以說「我知道有4323431個解決方案，那麼432134是什麼？」並找到解決方案將很快。

來源

2014-08-27 19:52:51 btilly

所以你的意思是基本上。除了二維數組dp [i] [j]，其中i是剩餘金額，j是硬幣的類型，我仍然需要另一個數據結構來存儲我從一個狀態轉到另一個狀態時所用的硬幣。這樣，當我完成所有可能的方法的數量時，我可以蠻力，從完成狀態開始，並嘗試遞歸地找到所有解。這基本上是你在說什麼？ – 2014-08-28 19:57:58

@TianyuLang聽起來像你了。它會添加一個鏈接列表，列出你到達某個狀態的其他狀態，並在每次到達某個狀態時添加它。 – btilly 2014-08-28 21:21:36

很明顯，您可以採取動態編程方法。在大多數情況下（取決於硬幣的面值），您可以使用貪婪算法，這可能會更有效。參見Cormen，Leiserson，Rivest，Stein：算法導論第二版，問題16.1。

來源

2014-08-27 19:54:55 user1666959

是的。使用貪婪會更有效，但它不是一個通用的解決方案。既然它會失敗，如果你擁有的硬幣類型是「特定的」 – 2014-08-28 19:55:18

所有的解決方案，以改變與動態規劃

回答

相關問題