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

一尘不染

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

algorithm

作为一名毕业生，我参加了Java开发职位的面试，并且在技术考试中表现出色，直到我遇到了这个问题。

如果我要设置一个自动售货机（为简单起见）返还2英镑的零钱。我将如何产生一个实现，列出所有2英镑的可能组合。

例如，£1 +£1，£1 + 50p + 50p，50p + 50p + 50p + 50p等。

我如何列出自动售货机可能会更改的£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:

阅读 215

2020-07-28

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

希望能帮助到你

2020-07-28