Write a Java program that can "make change" using appropriate data structures?

Question

I have an assignment which I have no idea to solve the way it is asked so.

I am not asking you to solve the whole problem! So don't downvote as soon as you see the word "assignment".

This is Data Structures and Algorithms course and it says solve the problem using appropriate data structure. First, I'll copy the assignment here:

Write a Java program that can "make change." Your program should take two numbers as input, one that is a monetary amount charged and the other that is a monetary amount given. It should then return the number of each kind of bill and coin to give back as change for the difference between the amount given and the amount charged. The values assigned to the bills and coins can be based on the monetary system of any current or former government. Try to design your program so that it returns the fewest number of bills and coins as possible.

If I understood correctly, we must write a program which can calculate the amount of money to pay back in bills and coins with the least usage of them.

We only learned Stacks, Queues and Linked Lists so far, but I don't know how to solve this assignment using one of these data structures.

Which data structures is appropriate to solve such problem and why?

Answer 1

Here's an algorithm for finding the best solution. Basically it walks through all possible denominations looking for the shortest list of change values.

// How many cents in a dollar.
private static final int DOLLARS = 100;
// In cents.
private static final int[] denominations = {
    // $100
    100 * DOLLARS,
    // $50
    50 * DOLLARS,
    // $20
    20 * DOLLARS,
    // $10
    10 * DOLLARS,
    // $5
    5 * DOLLARS,
    // $2
    2 * DOLLARS,
    // $1
    1 * DOLLARS,
    // 50c
    50,
    // 25c
    25,
    // 5c
    5,
    // 1c
    1
};

private List<Integer> makeChange(int value) {
    // Null means none found so far.
    List<Integer> change = null;
    System.out.println("Make change for " + value);
    // For all denomination.
    for (int i : denominations) {
        // that is less than the value
        if (i <= value) {
            // Build a new candidate.
            List<Integer> newChange = new LinkedList<>();
            // Remember it.
            newChange.add(i);
            // If we are at zero we're done.
            if (i < value) {
                // Make change from the remaining value.
                List<Integer> theRest = makeChange(value - i);
                if (theRest != null) {
                    // Gode more.
                    newChange.addAll(theRest);
                }
            }
            // Is it shorter?
            if (change == null || newChange.size() < change.size()) {
                // Better.
                change = newChange;
                System.out.println("Better change for " + value + " = " + change);
            }
        }
    }
    return change;
}

Trying this with low numbers such as 26 will give you a good result within a reasonable length of time. Up around the $10+ dollar mark and it will struggle because it has to enumerate all possible sub-arrangements of every arrangement - even if it has seen them before.

If we are allowed to use a Map we can improve matters by remembering previous best calculations (called Memoisation). This one can handle much bigger numbers because it never has to recalculate the best change for any number.

// All the best lists I've seen so far.
Map<Integer, List<Integer>> memory = new HashMap<>();

private List<Integer> makeChangeUsingMap(int value) {
    // If we've seen this one before, use it.
    if (memory.containsKey(value)) {
        return memory.get(value);
    }
    // Null means none found so far.
    List<Integer> change = null;
    System.out.println("Make change for " + value);
    // For all denomination.
    for (int i : denominations) {
        // that is less than the value
        if (i <= value) {
            // Build a new candidate.
            List<Integer> newChange = new LinkedList<>();
            // Remember it.
            newChange.add(i);
            // If we are at zero we're done.
            if (i < value) {
                // Make change from the remaining value.
                List<Integer> theRest = makeChangeUsingMap(value - i);
                if (theRest != null) {
                    // Gode more.
                    newChange.addAll(theRest);
                }
            }
            // Is it shorter?
            if (change == null || newChange.size() < change.size()) {
                // Better.
                change = newChange;
                System.out.println("Better change for " + value + " = " + change);
                // Remember it.
                memory.put(value, change);
            }
        }
    }
    return change;
}

Answer 2

I would use a Map. For example, 75 Would be represented as:

100 -> 0
 50 -> 1
 20 -> 1
 10 -> 0
 5  -> 1
 ...
0.01 ->0

Meaning zero hundred bills, one of fifty bill and so on.