网络上所有的更改问题都仅讨论理想情况，在这种情况下，我们可以无限量装满各种硬币/纸币。
我想处理一下ATM的额度有限的情况:10、20、50、100、200张钞票，并且必须找到进行找零的方法。
我已经做了类似的事情，但是我无法应付例如110美元的需求。 整个算法都在withdrawCash() 方法中，您可以复制其编译和工作的代码。
产出或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);
}
}
最佳答案
它可以相对轻松地完成，您只需要继续尝试添加各种可能性中剩余的钞票，然后丢弃那些已经比您想实现的要多的可能性。
这是工作代码，值是“钞票”值，“金额”是您拥有的钞票量:
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张)
[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]