用有限的硬幣進行改變的分而治之算法

該算法應該找到只使用一角硬幣，五分硬幣和便士，就可以對輸入數量進行改變的方法數量。我的做法是採用分而治之的策略，通過找出用最大的硬幣進行變化的方式數量，一角硬幣以及不用一角硬幣就能做出改變的方法數量。我爲這個算法編寫了一個實現，它正確地解決了1 ... 14輸入的問題，但是當輸入等於或大於15時，返回的結果是不正確的。顯然，我的算法是錯誤的，並且想知道需要做些什麼修改來修復代碼，以及我的方法是否是一個適當的分治法。用有限的硬幣進行改變的分而治之算法

的代碼如下：

public static int makeChange(int n) { 

     if(n < 0) 
      return 0; 
     else { 

     int sum = makeChange(n-10) + makeChange(n-5) + 1; 

     return sum; 
    } 
}

非常感謝。

來源

2013-10-21 MartinS

是什麼'makeChange2'樣子？張貼它也。 – Raptor

動態規劃比分而治之更適合這個問題。 – Kunal

*「當輸入等於或大於15時，返回的結果不正確。」*您獲得了什麼結果？你期望的結果是什麼？（或者你只是想給我們留下「不正確的」??）。我還指出，你不會在你的帖子中的任何地方提問。 – abelenky

提示：

int nways_10 (int n) { 
    int s = 0; 
    int d = n/10; 

    for (int i = 0; i <= d; ++i) { 
     s += nways_5 (n - 10*i); 
    } 

    return s; 
}

你應該得到的想法如何寫nways_5等功能，如果需要的話。

來源

2013-10-21 17:02:14 chill

只是爲了解釋這裏發生了什麼：對於你可以使用的每一個可能數量的硬幣，找出改變方法的數量，而不用使用任何硬幣。 –

你可以從我得到的答案基本算法這裏：https://stackoverflow.com/questions/19440228/creating-a-function-that-returns-combinations-of-change/19440582#19440582

，您將需要修改它，而不是輸出的，你應該返回1，並總結所有的人，顯示計數

來源

2013-10-21 17:09:47

用有限的硬幣進行改變的分而治之算法

回答

相關問題