Java 用有限数量的钞票给钱的ATM算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22128759/
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
ATM algorithm of giving money with limited amount of bank notes
提问by Yoda
All the change-making problem in the web talk only about ideal situation where we have unlimited ammount of coins/banknotes of every kind.
网络上的所有更改问题都只讨论理想情况，即我们拥有无限量的各种硬币/纸币。
I want to deal with situation when ATM has limited ammount of: 10,20,50,100,200 bank notes and it has to find way to make change.
我想处理 ATM 数量有限的情况：10,20,50,100,200 张纸币，它必须想办法进行更改。
I've done sth like that but I cannot deal with for example demand of 110 dollars.Whole algorithm is in method withdrawCash()you can copy the code it compiles and works.
我已经这样做了，但我无法处理例如 110 美元的需求。整个算法在方法中，withdrawCash()您可以复制它编译和工作的代码。
Output or 110$:
输出或 110$：
10 * 1 = 10
20 * 4 = 80
Notes of 10 left are 0
Notes of 20 left are 0
Notes of 50 left are 2
Notes of 100 left are 2
Notes of 200 left are 10
public class ATM {
/** The Constant Currency Denominations. */
protected static final int[] currDenom = { 10, 20, 50, 100, 200 };
/** The Number of Currencies of each type */
protected static int[] currNo = { 1, 4, 2, 2, 10 };
/** The count. */
protected int[] count = { 0, 0, 0, 0, 0 };
protected static int totalCorpus;
static {
calcTotalCorpus();
}
public static void calcTotalCorpus() {
for (int i = 0; i < currDenom.length; i++) {
totalCorpus = totalCorpus + currDenom[i] * currNo[i];
}
}
public ATM() {
}
public synchronized void withdrawCash(int amount) {
if (amount <= totalCorpus) {
for (int i = 0; i < currDenom.length; i++) {
if (currDenom[i] <= amount) {//If the amount is less than the currDenom[i] then that particular denomination cannot be dispensed
int noteCount = amount / currDenom[i];
if (currNo[i] > 0) {//To check whether the ATM Vault is left with the currency denomination under iteration
//If the Note Count is greater than the number of notes in ATM vault for that particular denomination then utilize all of them
count[i] = noteCount >= currNo[i] ? currNo[i] : noteCount;
currNo[i] = noteCount >= currNo[i] ? 0 : currNo[i] - noteCount;
//Deduct the total corpus left in the ATM Vault with the cash being dispensed in this iteration
totalCorpus = totalCorpus - (count[i] * currDenom[i]);
//Calculate the amount that need to be addressed in the next iterations
amount = amount - (count[i] * currDenom[i]);
}
}
}
displayNotes();
displayLeftNotes();
} else {
System.out.println("Unable to dispense cash at this moment for this big amount");
}
}
private void displayNotes() {
for (int i = 0; i < count.length; i++) {
if (count[i] != 0) {
System.out.println(currDenom[i] + " * " + count[i] + " = " + (currDenom[i] * count[i]));
}
}
}
private void displayLeftNotes() {
for (int i = 0; i < currDenom.length; i++) {
System.out.println("Notes of " + currDenom[i] + " left are " + currNo[i]);
}
}
public static void main(String[] args) {
new ATM().withdrawCash(110);
}
}
采纳答案by libik
It can be done relatively easily, you just have to keep trying adding bank notes that left in every possibility and then discard possibilities, which already have more than you try to achieve.
它可以相对容易地完成，您只需要继续尝试添加存在各种可能性的钞票，然后丢弃已经超过您尝试实现的可能性。
This is working code, values are "bank notes" values and in "ammounts" are ammounts of bank notes you have :
这是有效的代码，值是“钞票”值，“金额”是您拥有的钞票数量：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class JavaApplication55 {
int[] values = {10,20,50,100,200};
public static void main(String[] args) {
int[] values = {10,20,50,100,200};
int[] ammounts = {10,10,10,10,10};
List<Integer[]> results = solutions(values, ammounts, new int[5], 180, 0);
for (Integer[] result : results){
System.out.println(Arrays.toString(result));
}
}
public static List<Integer[]> solutions(int[] values, int[] ammounts, int[] variation, int price, int position){
List<Integer[]> list = new ArrayList<>();
int value = compute(values, variation);
if (value < price){
for (int i = position; i < values.length; i++) {
if (ammounts[i] > variation[i]){
int[] newvariation = variation.clone();
newvariation[i]++;
List<Integer[]> newList = solutions(values, ammounts, newvariation, price, i);
if (newList != null){
list.addAll(newList);
}
}
}
} else if (value == price) {
list.add(myCopy(variation));
}
return list;
}
public static int compute(int[] values, int[] variation){
int ret = 0;
for (int i = 0; i < variation.length; i++) {
ret += values[i] * variation[i];
}
return ret;
}
public static Integer[] myCopy(int[] ar){
Integer[] ret = new Integer[ar.length];
for (int i = 0; i < ar.length; i++) {
ret[i] = ar[i];
}
return ret;
}
}
This code having this ouput (it is output for 10,20,50,100,200 bank notes, you have 10 of each of them and you want to get 180 in sum)
这段代码有这个输出（它是 10,20,50,100,200 张纸币的输出，每张纸币有 10 张，你想总共得到 180 张）
[10, 4, 0, 0, 0]
[9, 2, 1, 0, 0]
[8, 5, 0, 0, 0]
[8, 0, 2, 0, 0]
[8, 0, 0, 1, 0]
[7, 3, 1, 0, 0]
[6, 6, 0, 0, 0]
[6, 1, 2, 0, 0]
[6, 1, 0, 1, 0]
[5, 4, 1, 0, 0]
[4, 7, 0, 0, 0]
[4, 2, 2, 0, 0]
[4, 2, 0, 1, 0]
[3, 5, 1, 0, 0]
[3, 0, 3, 0, 0]
[3, 0, 1, 1, 0]
[2, 8, 0, 0, 0]
[2, 3, 2, 0, 0]
[2, 3, 0, 1, 0]
[1, 6, 1, 0, 0]
[1, 1, 3, 0, 0]
[1, 1, 1, 1, 0]
[0, 9, 0, 0, 0]
[0, 4, 2, 0, 0]
[0, 4, 0, 1, 0]
回答by Vikram Bhat
Making amount from given set of coins is n-p complete problem because it reduces to subset sumproblem or knapsackproblem. But you have a pseudo polynomial time algorithm for the knapsack problem which is efficient enough for your purpose. Here you are using a greedy algorithm which gives solutions which can give solution for most cases but fails for some and hence cannot be used but you can use a combination of the pseudo polynomial time algorithm and the greedy to get an efficient algorithm that solves for all cases with high speed solution for best cases.
从给定的一组硬币中获得数量是 np 完全问题，因为它简化为子集和问题或背包问题。但是你有一个用于背包问题的伪多项式时间算法，它对你的目的来说足够有效。在这里，您使用的是贪心算法，该算法提供的解决方案可以为大多数情况提供解决方案，但在某些情况下会失败，因此无法使用，但您可以使用伪多项式时间算法和贪婪算法的组合来获得解决所有问题的有效算法最好的情况下具有高速解决方案的情况。
Pseudo polynomial time solution using knapsack analogy :-
使用背包类比的伪多项式时间解决方案：-
- knapsack capacity :- Amount needed for example 110
- items available:- x1*10,x2*20....xn*100. Cost and weight of items as same.
- Solve Knapsack for max profit using DP solution
- If max profit == knapsack capacity then you have a solution so retrace it using DP matrix.
- else there is no way you can get the amount using current available coins.
- 背包容量：- 所需的数量，例如 110
- 可用物品：- x1*10,x2*20....xn*100。物品的成本和重量相同。
- 使用 DP 解决方案解决背包以获得最大利润
- 如果最大利润 == 背包容量，那么你有一个解决方案，所以使用 DP 矩阵回溯它。
- 否则，您无法使用当前可用的硬币获得金额。
Time complexity:-O(Amount*Items)
时间复杂度：-O(Amount*Items)
Combination of greedy and DP solution :-
贪婪和DP解决方案的结合：-
boolean greedysolve = false, DPsolve = false;
greedysolve = YourSolution();
if(!greedysolve) {
DPsolve = KnapsackSolution();
}
else {
return(greedy_solution);
}
if(!DPsolve) {
return(DPsolution);
}
return(null); // No solution
