ATM算法，可使用有限数量的钞票进行付款 [英] ATM algorithm of giving money with limited amount of bank notes
问题描述
网络上的所有更改问题都仅讨论理想情况，在这种情况下，我们可以无限量装满各种硬币/纸币。
All the change-making problem in the web talk only about ideal situation where we have unlimited ammount of coins/banknotes of every kind.
我想处理ATM的额度有限的情况：10,20,50,100,200张钞票，并且必须找到进行找零的方法。
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.
我已经做了类似的事情，但是例如，我无法处理110美元的需求。整个算法都在方法 withdrawCash（）中 您可以复制其编译和运行的代码。
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 $：
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);
}
}
推荐答案
它可以相对容易地完成，您只需要继续尝试添加所有可能存在的钞票，然后丢弃可能已经超出您想实现的可能性。
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;
}
}
此代码具有此输出（输出为10 ，20,50,100,200张钞票，每张钞票中有10张，您希望总共获得180张）
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, 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]
这篇关于ATM算法，可使用有限数量的钞票进行付款的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
