解决供应商机器“更改提供”问题的 Java 算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7067044/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java Algorithm to solve vendor machine 'change giving' problem
提问by L-Samuels
As a graduate I went for an interview for a java development role and was doing pretty well in the technical examinations until i came up against this question.
作为一名毕业生，我参加了 Java 开发职位的面试，并且在技术考试中表现不错，直到我遇到了这个问题。
If i was setting up a vending machine which (for simplicity) returned ￡2 change. How would i produce an implemtation that would list all the possible combinations of ￡2.
如果我正在设置一台自动售货机，它（为简单起见）返回 ￡2 零钱。我将如何生成一个列出 ￡2 的所有可能组合的实现。
For e.g ￡1 + ￡1 , ￡1 + 50p + 50p, 50p + 50p + 50p + 50p and so on..
例如 ￡1 + ￡1 , ￡1 + 50p + 50p, 50p + 50p + 50p + 50p 等等..
How could i list all the different combinations of ￡2.00 change possible by the vending machine.
我怎么能列出自动售货机可能的 ￡2.00 变化的所有不同组合。
I began to write something and this is what ive came up with so far.
我开始写一些东西，这就是我目前想到的。
Its almost working except can someone help me find out why its not expanding fully. A second pair of eyes will be grateful. And also any ways it can be optimised.
它几乎可以工作，除非有人可以帮助我找出为什么它没有完全扩展。第二双眼睛会感激。以及任何可以对其进行优化的方式。
Thanks guys.
多谢你们。
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);
}
my output
我的输出
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:
回答by Ricky Bobby
To answer your second question:
回答你的第二个问题：
Try with only {20,10} you will see that your program is really not right .
只用 {20,10} 试试你会发现你的程序真的不对。
You tried to transform my recurence into a loop, and I guess it's the best solution. But it's very difficult to do that in one loop (you're missing a lot of possibilities).
您试图将我的递归转换为循环，我想这是最好的解决方案。但是在一个循环中做到这一点非常困难（你错过了很多可能性）。
You can try to reinialise the while loop with different constraint at each step for example adding a new while loop around your loop like this one
您可以尝试在每一步使用不同的约束重新初始化 while 循环，例如在循环周围添加一个新的 while 循环，就像这样
while (i<denominations.length){
total=200;
denomCoinIndex=i;
tempArray = new int[1000];
i++;
but it's still not enough ... so you will need to add some loop again until you treat all the cases.
但这还不够......所以你需要再次添加一些循环，直到你处理所有的情况。
I don't think your approach with a while loop is the good one here.
我不认为你的 while 循环方法在这里是好的。
The easiest way would be to use for loop like this to treat all the possible solutions (from the similar question to your question):
最简单的方法是使用像这样的 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);
Hope it helps
希望能帮助到你
回答by panzerschreck
Probably get started on looking at Dynamic programming. However you could any approach problem for that matter trivially. How would you do that manually ??. Jot down the steps. Convert it into an algorithm yourself. Probably studying Permutations & Combinations would help for better understanding of the problem you have stated.
可能开始研究动态编程。但是，您可以轻而易举地解决任何问题。您将如何手动执行此操作？？记下步骤。自己将其转换为算法。可能学习排列和组合将有助于更好地理解您所说的问题。
Hope it helps.
希望能帮助到你。
回答by Jim Garrison
Reframe the problem as follows: Given a standard (modern) car odometer that registers 6 digits with no fractions, find all possible values where the sum of the digits is some value, say 15. If you can solve that, you can solve the given problem.
将问题重构如下：给定一个标准（现代）汽车里程表，它记录 6 位数字，没有分数，找到所有可能的值，其中数字的总和是某个值，比如 15。如果你能解决这个问题，你就可以解决给定的问题。
回答by Ricky Bobby
Let say your possible coins are x1 ...xn :
假设您可能的硬币是 x1 ...xn ：
if you're asked to print all the possiblities for $2 then you could print recursivelyall the possibilities for :
如果您被要求以 2 美元的价格打印所有可能性，那么您可以递归打印以下所有可能性：
2-x1
2-x2
..
2-xn
Yoou will eventually get all the solutions
你最终会得到所有的解决方案
You can initialise this recursive process with amount-xi = 0 then print
您可以使用 amount-xi = 0 初始化这个递归过程，然后打印
回答by Brian Gordon
Algorithm F on (in-text) page 7 is exactly what you're looking for. :)
(in-text) page 7 上的算法 F 正是您正在寻找的。:)
回答by user3499861
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
