解决vendor machine 'change giving'问题的Java算法

Question

作为一名毕业生，我参加了 Java 开发职位的面试，在遇到这个问题之前，我在技术考试中表现相当不错。

如果我正在设置一台自动售货机(为简单起见)返回 2 英镑的零钱。我将如何产生一个列出 2 英镑所有可能组合的实现。

例如 1 英镑 + 1 英镑、1 英镑 + 50 便士 + 50 便士、50 便士 + 50 便士 + 50 便士 + 50 便士等等。

我如何列出自动售货机可能的 2.00 英镑零钱的所有不同组合。

我开始写一些东西，这是我到目前为止想到的。

它几乎可以正常工作，但有人可以帮我找出它没有完全扩展的原因。第二双眼睛会很感激。以及可以优化的任何方式。

谢谢你们。

 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: 

Answer 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);

希望对你有帮助