Проблема изменения монет 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

Ваши coins выражены в центах (или пенсах, так как я полагаю, что вы используете фунты стерлингов), поэтому, поскольку вы выполняете с ними amountIn - coins[i], это означает, что ваша сумма также равна центам / пенсам.

Итак, измените свою сумму на:

amount = 200;

Стоит уделить время рассмотрению именования переменных и того, как это могло бы помочь идентифицировать - или даже избежать - эту проблему в целом. Термины «сумма» и «сумма в» неоднозначны.

Ничто в словах не говорит о единицах. Итак, приобретите привычку делать имена переменных как можно более конкретными и недвусмысленными - и включать единицы, где это уместно.

Например, если переменные назывались 'amountInPounds', то ошибка становится более очевидной при записи 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}