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("\n\n\n");
        System.out.println("There are " + count + " ways can 2 pounds be made, "
            + "using any number of coins");
        System.out.println("\n\n\n");
    }
 }

输出：

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

Answer 1

此算法允许使用相同面额的多个硬币，因此有 2 种方法可以赚取 2 英镑：

{1, 1}
{2}

Answer 2

您的 coins 以美分（或便士，因为我猜您使用的是 GB 英镑）为单位，所以由于您与他们一起表演 amountIn - coins[i]，这意味着您的金额是 cents/pence 还有。

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

amount = 200;

值得花点时间考虑一下变量命名，以及它如何帮助识别 - 甚至完全避免 - 这个问题。术语 "amount" 和 "amountIn" 有歧义。

文字中没有任何表示单位的内容。因此，养成使变量名称尽可能具体和明确的习惯 - 并在适当的地方包括单位。

例如，如果变量被调用'amountInPounds'，那么在写amountInPounds - coins[i]

时错误会变得更加明显

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

1) 会有大量的结果（200 pennies, 198 pennies+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 将产生大数字，您实际上不可能确认正确性，因此请从您可以检查的小数字开始。

Java 使用递归的硬币找零问题 -- 不工作

Java Coin Change Problem Using Recursion -- not working

java

arrays

algorithm

recursion

coin-change