ATM algorithm of giving money with limited amount of bank notes

Issue

All the change-making problem in the web talk only about ideal situation where we have unlimited amount of coins/banknotes of every kind.

I want to deal with situation when ATM has limited amount of: 10, 20, 50, 100, 200 bank notes and it has to find way to make change.

I've done something like that but I cannot deal with for example demand of 110 dollars. The Whole algorithm is in method withdrawCash() - it compiles and works.

Output for 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

Code:

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

Solution

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, 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]

Answered By - libik