硬幣更換遞歸方法

Question

我想用遞歸方法解決硬幣更換問題。問題是這樣的：

給你不同面值的硬幣和總金額。編寫一個函數來計算構成該數量的組合的數量。

給你一定數量的硬幣。

這是我到目前爲止有：

private static int[] coins = {1,2,5}; 

public static void main(String[] args) { 
    System.out.println(count(13)); 
} 

public static int count(int n) 
{ 
    // If n is 0 then there is 1 solution 
    if (n == 0) 
     return 1; 

    // If n is less than 0 then no solution exists 
    if (n < 0) 
     return 0; 

    return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]); 
} 

當我做這個，我什麼也沒得到接近正確的組合。我認爲這個問題與迴歸，但我不明白爲什麼。在這裏，我從數量中減去硬幣並每次將它們加在一起。當它變爲0時，它返回1.

Answer 1

首先就應該更換：

return count(n - coins[0]) + count(n - coins[1]) + count(n - coins[2]); 

有了一個循環：

int nCoins = 0; 
for(int coin=0; coin<coins.length; coin++) 
{ 
    nCoins += count(n-coins[coin]); 
} 
return nCoins; 

這樣做的問題在於，它會產生硬幣（= 634）的所有排列。爲了獲得每一個獨特的硬幣組合，你需要確保你在當前的硬幣上開始每一級遞歸。爲此，您需要爲count方法添加一個參數，以指示硬幣陣列中開始的位置。

public static int count(int n, int startCoin) 

你的循環就變成

int nCoins = 0; 
for(int coin=startCoin; coin<coins.length; coin++) 
{ 
    nCoins += count(n-coins[coin], coin); 
} 
return nCoins; 

其中給出正確答案（14）。

Answer 2

根據你的算法，便士然後鎳被視爲不同於鎳和便士的解決方案。你應該執行一個特定的命令。 （這在數學中被認爲是排列和組合之間的差異）。

我會考慮添加硬幣面額列表作爲遞歸函數的第二個參數。然後，在每一個步驟（除端子步驟除外），會考慮兩種可能性：僅面額的一個

A）考慮加入另一種硬幣的可能性，但在列表

B的前面）考慮遞歸調用的可能性，其中您將列表中的第一個元素截斷

Answer 3

我還沒有足夠的聲望進行評論，目前正在爲您的問題提供解決方案。這是我在當前代碼中注意到的一個缺陷：您正在跟蹤「獨特的排列」（我不知道官方的數學名稱會是什麼），而不是「相似的排列」，因爲我相信您會喜歡。

例如，如果你想找到count(5)，你會得到以下9個可能的排列/辦法在5到：

[2,2,1]，[2,1,2 ]，[1,2,2]，[5]，[2,1,1,1]，[1,2,1,1]，[1,1,2,1]，[1,1,1 ，2]和[1,1,1,1,1]。

雖然我相信你會只想要回四（4）如下排列：

[1,1,1,1,1]，[2,1,1]，[2,2 ，1]，[5]

這裏是我認爲進一步回答你的問題的鏈接。請在未來提出問題之前通過Stack Overflow進行搜索！

How to count possible combination for coin problem

How to find all combinations of coins when given some dollar value

Answer 4

對於這個問題的解決方案已經發布，所以我會假設你問如何看待它，而不是答案本身。

試試這個：

設V是目標值。

設C [i]爲第i個硬幣值。

遞歸解決方案是關於做一個減少問題大小的選擇，然後在較小的問題上遞歸使用相同的解決方案。

當問題很小，不需要重複就可以輕鬆解決，我們只需返回該解決方案即可。這是「基本案例」。

這裏的選擇是使用具有值C [i]的特定數目N [i]的硬幣。對於N [i]的所有可能值，即N [i] = 0,1,2，... floor（V/C [i]），我們需要對此進行解釋。整數平面（V/C [i]）只是可能產生正確變化的第i個硬幣的最大數量。

一旦我們選擇了使用多少第i個硬幣，我們就不應該改變這個決定。 （這是你的解決方案出錯的地方。）最簡單的方法是利用數組索引造成的硬幣隱式順序。我們遞歸地找到使用硬幣i + 1和更大的目標值的剩餘部分進行改變的方法的數量：V-N [i] * coins [i]。

（另一種設計是保持硬幣在一組和由[i]從復現之前去除硬幣做出的選擇。但是，讓我們留在指數，因爲所產生的代碼更簡單。）

爲了得出結果，我們將所有遞歸確定的計數加起來。

有了這種想法，我們可以選擇一個簽名的遞歸方法：

/** 
* Return the number of ways to make change for the given value 
* using coins i >= iMin. 
*/ 
int count(int value, int iMin); 

時間去想基地的情況。 「成功」是當value恰好爲零時：我們可以完全不做任何改變！當value不是零時，發生「失敗」，並且我們沒有足夠的硬幣值來嘗試。這就是當iMin已經達到coins陣列的長度時。

讓我們把這個想法變成代碼：

int count(int value, int iMin) { 
    if (value == 0) return 1; // Success base case. 
    if (iMin >= coins.length) return 0; // Failure base case. 
    result = 0; 
    for (int ni = 0; ni <= value/coins[iMin]; ++ni) 
    result += count(value - ni * coins[iMin], iMin + 1); 
    return result; 
} 

要開始遞歸，只需使用目標值和零iMin：

int result = count(target, 0); 

需要注意的是，雖然這個解決方案是正確的，它不是效率很高。讓我們再討論這一天。