递归计算硬币支付组合

我正在尝试实施一种递归算法，该算法可计算给定数量的所有可能支付组合。我根本没有太多的递归经验，所以我希望得到一些帮助。递归计算硬币支付组合

可用欧元硬币：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

递归计算硬币支付组合

回答

相关问题