硬币更换递归方法

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); 

需要注意的是，虽然这个解决方案是正确的，它不是效率很高。让我们再讨论这一天。