换币递归法

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

根据您的算法，penny-then-nickel被视为与nickel-then-penny不同的溶液。你应该执行特定的命令。（这在数学上称为排列和组合之间的差异。）

我会考虑添加一个硬币面值列表作为递归函数的第二个参数。然后，在每个步骤（除了一个终端步骤），你会考虑两种可能性：

（a）考虑添加另一枚硬币的可能性，但只有列表前面的面额中的一个。

B）考虑递归调用的可能性，其中您正在截断列表中的第一个元素。

Answer 2

这个问题的解决方案已经发布了，所以我假设你问的是如何思考它，而不是答案本身。

试试这个：

设V为目标值。

让C[i]成为第i个硬币的价值。

递归解决方案是指做出一个选择，减少问题的规模，然后在较小的问题上递归地使用相同的解决方案。

当问题很小，不需要重复就可以轻松解决时，我们只返回该解决方案。这就是“基本情况”

这里的选择是使用特定数量的硬币N[i]的价值C[i]。

对于N[i]的所有可能的值，我们需要这样做，即。N[i]=0,1,2，...地板（V/C[i]）。整数层（V/C[i]）是可能产生正确变化的第i个硬币的最大数量。

一旦我们决定了使用多少i'th硬币，我们就不应该改变这个决定。（这就是您的解决方案出错的地方。）实现这一点的最简单方法是利用货币数组html" target="_blank">索引的隐含顺序。对于目标值的剩余部分：V-N[i]*coins[i]，我们递归地找到使用硬币i 1和更大的硬币进行更改的方法的数量。

（另一种设计是将硬币保留在一个集合中，并通过在重复出现之前从集合中移除硬币[i]来进行选择。但让我们继续使用索引，因为生成的代码更简单。）

为了产生结果，我们只需将所有递归确定的计数相加。

基于这种想法，我们可以为递归方法选择一个签名：

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

是时候考虑一下基本情况了。“成功”是指值完全为零时：我们可以通过完全不做任何事情的方式以完全1的方式进行更改！当值不为零，并且我们没有硬币值可供尝试时，就会出现“失败”。这正是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;
}

要开始递归，只需使用目标值和0的iMin：

int result = count(target, 0);

请注意，虽然此解决方案是正确的，但效率不高。让我们改天再讨论吧。

Answer 3

首先，你应该替换：

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）。