java - ATM限额钞票给钱算法

Question

网络上所有的找零问题都只讨论我们拥有无限数量的各种硬币/纸币的理想情况。

我想处理 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);
    }
}

Answer 1

这可以相对容易地完成，您只需要不断尝试添加存在各种可能性的钞票，然后丢弃可能已经比您尝试实现的更多的可能性。

这是工作代码，值是“钞票”值，“金额”是您拥有的钞票数量:

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]