java - Java算法解决供应商机器的“变更赋予”问题

作为一名毕业生，我参加了一个Java开发职位的面试，在技术考试中表现不错，直到我遇到这个问题。
如果我正在安装一台自动售货机，它（为了简单起见）退回了2英镑的零钱。我该如何产生一个恳求，列出所有可能的组合2英镑。
例如1+1英镑、1+50p+50p、50p+50p+50p+50p+50p等等。
我怎么能列出自动售货机2英镑零钱的所有不同组合呢？
我开始写一些东西，这就是我到目前为止的想法。
它几乎可以工作了，除非有人能帮我找出为什么它不能完全扩展。第二双眼睛会感激的。以及任何可以优化的方法。
谢谢你们。

 private static void printCoins(int[] tempArray) {

    for (int i = 0; i < tempArray.length - 1; i++){

// to stop my array from printing out any non-denominator coins e.g
    if (tempArray[i] > 0){
 System.out.print(tempArray[i] + ": ");
    }
    System.out.println("\n");
  }
}


public static void vendingMachine() {
    int[] denominations = {200,100, 50, 20, 10, 5, 2, 1};
    int[] tempArray = new int[50]; //combination of coins made
    int total = 200;
    int coinCombiIndex = 0, denomCoinIndex = 0;

    // whilst all denominations havent been visited
 while (denomCoinIndex < denominations.length)

     // if i have the correct change
    if (total - denominations[denomCoinIndex] == 0){
        tempArray[coinCombiIndex] = denominations[denomCoinIndex];

        denomCoinIndex++;  //increment so that next iteration starts with lower denom
        printCoins(tempArray); // return coins
    }

 // checks to see whether new total minus coin (denominator) is still >= 0
      else if (total - denominations[denomCoinIndex] >= 0) {

            // if so SUBTRACT from total and ADD coin to coin-combination-array
            total = total - denominations[denomCoinIndex];
            tempArray[coinCombiIndex] = denominations[denomCoinIndex];
            coinCombiIndex++;

            }
        else {
        denomCoinIndex++;

    }

    //  printCoins(tempArray);

}

我的输出

200:

100: 100:

100: 50: 50:

100: 50: 20: 20: 10:

100: 50: 20: 20: 5: 5:

100: 50: 20: 20: 5: 2: 2: 1:

最佳答案

回答你的第二个问题：
只用{20,10}试试，你会发现你的程序确实不对。
你想把我的复发变成一个循环，我想这是最好的解决办法但要在一个循环中做到这一点是非常困难的（你错过了很多可能性）。
您可以尝试在每个步骤使用不同的约束重新序列化while循环，例如在循环周围添加一个新的while循环，如下所示

while (i<denominations.length){
             total=200;
             denomCoinIndex=i;
             tempArray = new int[1000];
             i++;

但还是不够所以在处理完所有的病例之前，你需要再添加一些循环。
我不认为你用while循环的方法是好的。
最简单的方法是使用这样的for循环来处理所有可能的解决方案（从类似的问题到您的问题）：

 int total = 200;

               System.out. printf("quarter\tdime\tnickle\tpenny\tto make %d\n", total);

                int combos = 0;

                for (int q = 0; q <= total / 25; q++)
                {
                    int total_less_q = total - q * 25;
                    for (int d = 0; d <= total_less_q / 10; d++)
                    {
                        int total_less_q_d = total_less_q - d * 10;
                        for (int n = 0; n <= total_less_q_d / 5; n++)
                        {
                            int p = total_less_q_d - n * 5;
                            System.out.printf("%d\t%d\t%d\t%d\n", q, d, n, p);
                            combos++;
                        }
                    }
                }

                System.out.printf("%d combinations\n", combos);

希望有帮助