硬币改变递归方法-Java 学习之路

我试图用递归方法解决硬币变化问题 . 问题是这样的：

您将获得不同面额和总金额的硬币 . 编写一个函数来计算构成该数量的组合数 . 给你一笔金额和一系列硬币 .

这是我到目前为止：

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 .

4 回答

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） .
回复于 2024-04-30T03:20:25+08:00
5
已经发布了这个问题的解决方案，所以我假设你问的是如何思考它，而不是答案本身 .

试试这个：

设V为目标值 .

设C [i]为第i个硬币值 .

递归解决方案是关于做出减少问题大小的选择，然后在较小的问题上递归使用相同的解决方案 .

当问题小到足以轻易解决而不再发生时，我们只返回该解决方案 . 这是“基本情况” .

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

我们需要对所有可能的N [i]值，即N [i] = 0,1,2，... floor（V / C [i]） . 整数层（V / C [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);
```
是时候考虑基础案例了 . "Success"是 value 恰好为零时：我们可以通过什么都不做来完全改变！当 value isn 't zero, and we'超出硬币值时，会发生"Failure" . 这恰好是 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);
```
请注意，尽管此解决方案是正确的，但效率并不高 . 让我们再讨论这一天 .
回复于 2024-04-30T03:20:25+08:00
0

我还没有足够的声誉发表评论，目前正致力于解决您的问题 . 这是我在你当前代码中注意到的一个缺陷：你正在追踪“独特的排列”（我不知道官方的数学名称是什么）而不是“相似的排列”，我相信你想要的 .

例如，如果你想找到 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

回复于 2024-04-30T03:20:25+08:00
0

根据你的算法，便士然后将镍视为镍和便士的不同解决方案 . 您应该执行特定订单 . （这在数学中被称为排列和组合之间的差异 . ）

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

A）考虑添加另一枚硬币的可能性，但仅限于此列表前面的一个面额

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

回复于 2024-04-30T03:20:25+08:00

硬币改变递归方法

4 回答

相关问题