银行取款机有限张数发钞算法

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);
    }
}

- Yoda

Answer 1

这可以相对容易地完成，您只需不断尝试添加剩余在每种可能性中的钞票，然后丢弃已经超过您尝试实现的数量的可能性。

以下是可行的代码，"bank notes"代表钞票面值，"ammounts"代表您拥有的钞票数量：

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]

- libik

Answer 2

给定一组硬币，求得到某个金额的方案是一个n-p完全问题，因为它可以归约为子集和问题或背包问题。但是你有一个伪多项式时间算法用于背包问题，它对你的目的来说足够高效。

在这里，你使用了一种贪心算法，它可以给出大多数情况下的解决方案，但在某些情况下会失败，因此不能使用，但你可以结合伪多项式时间算法和贪心算法，得到一种高效的算法，它可以解决所有情况，并且在最佳情况下具有高速解决方案。

使用背包类比的伪多项式时间解决方案：

1. 背包容量：所需金额，例如110 2. 可用物品：x110,x220....xn*100。物品的成本和重量相同。 3. 使用DP解决方案，解决最大利润的背包问题 4. 如果最大利润==背包容量，则你有一个解决方案，因此使用DP矩阵回溯它。 5. 否则，你无法使用当前可用的硬币获得该金额。

时间复杂度：O(Amount*Items)。

贪心和动态规划的组合解法：

boolean greedysolve = false, DPsolve = false;

greedysolve = YourSolution();

if(!greedysolve) {

   DPsolve = KnapsackSolution(); 
}

else {

   return(greedy_solution);
}

if(!DPsolve) {

   return(DPsolution);

}

return(null);  // No solution

- Vikram Bhat

---

没有人需要最大值或任何利润。问题是使用一组不同的纸币支付一笔款项。 - Gangnus

@Gangnus 我知道，仔细阅读我的回答，我已经提到价值和重量是相同的，因此基本上填满背包将会给出最大的利润，这也是预期的。 - Vikram Bhat