使用递归的Java硬币更改问题 - 不起作用

Question

我为此搜索了代码和逻辑，基本上从 https://www.youtube.com/watch?v=k4y5Pr0YVhg 复制了代码 和 https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/

但是我的程序是错误的，因为绝对有超过 2 种方法可以制作 2 磅。

public class TwoPounds
{
private static int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
private static int amount;
private static int count;
public TwoPounds()
{
amount = 2;
count = 0;
}
public static void main(String[] args)
{
TwoPounds run = new TwoPounds();
count = run.combos(amount);
run.printOut();
}
public int combos(int amountIn)
{       
if (amountIn == 0)
{
return 1;
}
if (amountIn < 0)
{
return 0;
}
int combosCount = 0;
for(int i = 0; i < coins.length; i++)
{
System.out.println("amountIn now is " + amountIn);
combosCount += combos(amountIn - coins[i]);
}
return combosCount;
}
public void printOut()
{
System.out.println("nnn");
System.out.println("There are " + count + " ways can 2 pounds be made, "
+ "using any number of coins");
System.out.println("nnn");
}
}

输出：

There are 2 ways can 2 pounds be made, using any number of coins

Answer 1

您的coins以美分为单位(或便士，因为我猜您使用的是 GB 英镑(，所以由于您正在与它们一起执行amountIn - coins[i]，这意味着您的金额也是美分/便士。

因此，将您的金额更改为：

amount = 200;

值得花点时间考虑变量命名，以及它如何帮助识别 - 甚至避免 - 这个问题。 术语"金额"和"金额"是模棱两可的。

言语中没有任何暗示单位。 因此，养成使变量名称尽可能具体和明确的习惯 - 并在适当的情况下包含单位。

例如，如果变量被称为"金额磅"，那么在写入时错误会变得更加明显amountInPounds - coins[i]

现在，在更新到amount = 200;之前，请注意：

1(将会有大量的结果(200便士，198便士+ 2p(，一次迭代一分钱需要一些时间，再加上

2(您的代码当前被编写为通过每个离散有序组合 - 例如，它将计数：

• 198 "1 美分" + 1 "2 分">
• 197 "1 美分" + 1 "2 美分" + 1 "1 美分">
• 196 "1 美分
" + 1 "2 美分" + 2 "1 美分"
• 195 "1 美分" + 1 "2 美分" + 3 "1 美分" 等

同样，执行时间太多。 你想要的是不要每次都从零开始for(int i = 0; i < coins.length; i++)，而是添加一个额外的参数来combos- 所以像这样：

public int combos (int amountIn, int startCoin)
{       
// blah ... existing code ... blah
for(int i = startCoin; i < coins.length; i++)
{
System.out.println("amountIn now is " + amountIn);
combosCount += combos(amountIn - coins[i], i);
}

最后，正如我之前所说，200 将导致大数字，实际上您不可能确认正确性，因此请从您可以检查的少量开始。

Answer 2

该算法允许使用相同面额的几种硬币，因此有 2 种方法可以赚取 2 磅：

1. {1， 1}
2. {2}