遞歸計算硬幣支付組合

我正在嘗試實施一種遞歸算法，該算法可計算給定數量的所有可能支付組合。我根本沒有太多的遞歸經驗，所以我希望得到一些幫助。遞歸計算硬幣支付組合

可用歐元硬幣：1美分，2美分，5美分，10美分，20美分，50美分，1歐元，2歐元。

所以我正在尋找函數的絕對值，它給出了以美分給定量的8個硬幣的線性組合。

所有這些線性組合的絕對值或集合可以被分成兩個不相交的子集，即M1是不包含硬幣n的所有線性組合的集合和其中硬幣n至少出現一次的子集M2在每個線性組合中，這相當於以下內容：

爲了說明這一點，此處舉例說明了5美分的金額，其中存在4種不同的付款方式，即：5個1美分硬幣，2個2美分硬幣， 1分硬幣和1分硬幣，1分2分硬幣+ 3分1分硬幣，1分5分硬幣。

這是我用Java實現：

public class Coins { 


static int[] c = { 1, 2, 5, 10, 20, 50, 100, 200}; 
static long M1 = 0; 


public static long pay (int m) 
{ 
    int n = c.length; 
    long M = pay(m, n); 
    return M; 
} 

private static long pay(int m, int n) 
{ 

    if (n == 1) 
    { 
     return 1; 
    } 
    if (m == 0) 
     return 1; 
    if (m < 0) 
     return 0; 
    M1 += pay(m, n - 1) + pay(m - c[n-1], n); 
    return M1; 
} 

public static void main(String[] args) { 
    int m = 6; 
    long norm = pay(m); 
    System.out.println(norm); 
} 
}

此實現不給我正確的解決方案，我不知道爲什麼它不還是它在做什麼，在所有。我試着用打印報表，爲m = 6的情況下，給我中間結果：

count = 1 m= 6 n= 8 M1= 0 

count = 3 m= 6 n= 7 M1= 0 

count = 5 m= 6 n= 6 M1= 0 

count = 7 m= 6 n= 5 M1= 0 

count = 9 m= 6 n= 4 M1= 0 

count = 11 m= 6 n= 3 M1= 0 

count = 13 m= 6 n= 2 M1= 0 

count = 15 m= 6 n= 1 M1= 0 

count = 16 m= 4 n= 2 M1= 0 

count = 18 m= 4 n= 1 M1= 0 

count = 19 m= 2 n= 2 M1= 0 

count = 21 m= 2 n= 1 M1= 0 

count = 22 m= 0 n= 2 M1= 0 

count = 23 m= 1 n= 3 M1= 4 

count = 25 m= 1 n= 2 M1= 4 

count = 27 m= 1 n= 1 M1= 4 

count = 28 m= -1 n= 2 M1= 4 

count = 29 m= -4 n= 3 M1= 5 

count = 30 m= -4 n= 4 M1= 13 

count = 31 m= -14 n= 5 M1= 13 

count = 32 m= -44 n= 6 M1= 13 

count = 33 m= -94 n= 7 M1= 13 

count = 34 m= -194 n= 8 M1= 13

現在，它實際上在某種意義上正確計算，如果你想補充的案件中，m=0和n=1，你會得到正確的解決方案，但它以某種方式得到結果13.有人可以告訴我這裏發生了什麼嗎？爲什麼我的實現產生13結果而不是5？

來源

2013-12-22 eager2learn

可能的重複[查找所有組合的硬幣時給予一些美元的價值]（http://stackoverflow.com/questions/1106929/find-all-combinations-of-coins-when-given-some-dollar-value ） – Sylwester

變化

M1 += pay(m, n - 1) + pay(m - c[n-1], n);

到

M1 = pay(m, n - 1) + pay(m - c[n-1], n);

M1是它下面的2個分支的總和。

每個遞歸調用計算其子分支的M1並將結果返回給它的父節點。

來源

2013-12-22 17:56:42 parkydr

遞歸計算硬幣支付組合

回答

相關問題