Java算法解决供应商机器“改变给予”问题

作为一名gradle生，我参加了一个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  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 = 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 

但它仍然不够......所以你需要再次添加一些循环，直到你处理所有的情况。

我不认为你的while循环方法在这里是好的。

最简单的方法是使用这样的循环来处理所有可能的解决方案（从类似的问题到你的问题）：

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

希望能帮助到你

Answer 2

可能开始研究动态编程。 但是，你可以解决这个问题。 你会如何手动完成？ 记下步骤。 自己将其转换为算法。 可能正在研究排列和组合将有助于更好地理解您所述的问题。

希望能帮助到你。

Answer 3

重新解决问题如下：给定一个标准（现代）汽车里程表，注册6位数字没有分数，找到所有可能的值，其中数字的总和是一些值，比如15。如果你能解决这个问题，你可以解决给定的问题问题。

Answer 4

假设您的可能硬币是x1 … xn：

如果要求您以2美元的价格打印所有可能性，那么您可以递归打印所有可能性：

 2-x1 2-x2 .. 2-xn 

Yoou最终将获得所有解决方案

您可以使用amount-xi = 0初始化此递归过程，然后打印

Answer 5

第7页的（文本内）算法F正是您正在寻找的。 🙂

http://www-cs-staff.stanford.edu/~uno/fasc3a.ps.gz

Answer 6

 public class VendeningMachine { public static final int[] coins = {1, 5, 10, 25}; public static final int[] coinMax = {200, 40, 20, 8}; public static final int[] coinsString = { "Penny", "Nickle", "Dime", "Quarter"}; public static void main(String[] args) { } public static void vendingMachine() { for ( int a = 0; a <= coinMax[0]; a++ ) { for ( int b = 0; b <= coinMax[1]; b++ ) { for ( int c = 0; c < coinMax[2]; c++ ) { for ( int d = 0; d < coinMax[3]; d++ ) { checkCoins(a, b, c, d); } } } } } public static void checkCoins(int penny, int nickle, int dime, int quarter) { int total = coins[0] * penny + coins[1] * nickle + coins[2] * dime + coins[3] * quarter; if ( total == 200 ) printCoins(penny, nickle, dime, quarter); } public static void printCoins(int penny, int nickle, int dime, int quarter) { System.out.println("Penney : " + penny + " Nickle: " + nickle + " Dime: " + dime + " Quarter: " + quarter); } }enter code here