Java : Changemaking

import java.util.*;
import java.util.Map.Entry;
import java.io.*;
public class ChangeMaking {
    static int[] denoms = new int[] {10, 7, 6, 1};
    public static void main(String[] args)
    {
        getDenoms();
        int change = getTotalChange();
        info greedy = getGreedyHeuristic(change);
        start(change, greedy);
    }
    public static void getDenoms()
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("What denominations would you like to use?");
        System.out.println(" *note: answer in this format (any order is okay)");
        System.out.println("  1, 6, 7, 10");
        List<Integer> denomsL = new ArrayList<Integer>();
        denomsL.clear();
        try {
            String input = br.readLine();
            String delim = ",";
            if(!input.contains(","))
            {
                delim = " ";
            }
            for(String s : input.split(delim))
            {
                s = s.trim();
                denomsL.add(Integer.parseInt(s));
            }
            java.util.Collections.sort(denomsL);
            java.util.Collections.reverse(denomsL);
            denoms = new int[denomsL.size()];
            String out = " Using denominations: {";
            for(int i = 0; i < denomsL.size(); i++)
            {
                int in = denomsL.get(i);
                denoms[i] = in;
                out += in + ", ";
                if(in <= 0)
                {
                    throw new NumberFormatException();
                }
            }
            out = out.substring(0, out.length()-2)+"}";
            System.out.println(out);
        } catch (IOException e) {
            e.printStackTrace();
        } catch (NumberFormatException nfe) {
            System.out.println("Invalid entry. Using default values instead.\n {1, 6, 7, 10}");
        }
    }
    public static int getTotalChange()
    {
        int totalChange = 0;
        System.out.println("How much change do we begin with?");
        try {
            Scanner in = new Scanner(System.in);
            totalChange = in.nextInt();
            if(totalChange <= 0)
            {
                throw new NumberFormatException();
            }
        } catch (NumberFormatException nfe) {
            System.out.println("Invalid entry. Using default values instead.\n {49}");
            totalChange = 49;
        } catch (InputMismatchException ime) {
            System.out.println("Invalid entry. Using default values instead.\n {49}");
            totalChange = 49;
        }
        return totalChange;
    }
    public static info getGreedyHeuristic(int change)
    {
        info greedy = new info();
        int leftover = 0;
        int coinsUsed = 0;
        for(int i = 0; i < denoms.length; i++)
        {
            int coinsUsedThisIteration = 0;
            coinsUsedThisIteration = change/denoms[i];
            greedy.uses(coinsUsedThisIteration, denoms[i]);
            coinsUsed += coinsUsedThisIteration;
            leftover = change = change%denoms[i];
        }
        System.out.println("=======================================================");
        System.out.println("We use attempt to use the Greedy Method as a heuristic.");
        if(leftover != 0)
        {
            System.out.println(" Greedy Method fails to return valid answer.");
            greedy.clear();
            greedy = null;
        }
        else
        {
            System.out.println(" Greedy Method uses a total of "+greedy.size+" coins:");
            greedy.show();
        }
        System.out.println("=======================================================");
        System.out.println();
        return greedy;
    }
    public static void start(int change, info greedy) throws IllegalArgumentException
    {
        try
        {
            if(change <= 0)
            {
                throw new IllegalArgumentException("Your input ["+change +"] is not an integer greater than 0.\n Please try again with a valid argument.");
            }
            getChange(denoms, change, greedy);
        }
        catch(IllegalArgumentException iae)
        {
            System.out.println(iae.getMessage());
        }
    }
    public static int getChange(int[] d, int c, info greedy)
    {
        info[][] infoArr = new info[denoms.length][];
        for(int i = d.length-1; i >= 0; i--)
        {
            infoArr[i] = new info[c];
            for(int j = 1; j <= c; j++)
            {
                info currentBest = null;
                int val = 1; //the amount of coins we're using with the current method.
                infoArr[i][j-1] = new ChangeMaking.info(greedy);
                if(d[i] > j)
                {
                    System.out.println("Current Denom {"+d[i]+" c} is higher than the value of "+j+".");
                    if(i+1 < denoms.length)
                    {
                        if(infoArr[i+1][j-1].size != Integer.MAX_VALUE)
                            infoArr[i][j-1].uses(infoArr[i+1][j-1].coins);
                        else
                            infoArr[i][j-1].size = Integer.MAX_VALUE;
                        System.out.println(" Use previous denom's coins ("+(infoArr[i+1][j-1].size==Integer.MAX_VALUE?"n/a":infoArr[i+1][j-1].size)+").");
                    }
                    else
                    {
                        infoArr[i][j-1].size = Integer.MAX_VALUE;
                    }
                    System.out.println();
                    continue;
                }
                int leftover = j-d[i];
                boolean isValid = infoArr[i][j-1].uses(1, d[i]);

                System.out.println("To make "+j+"c when highest denom {"+d[i]+" c}.");
                print("Use 1x  "+d[i]+"c coins to make "+(d[i])+" cents. Leaves "+leftover+"c left over.\n");

                //We just used the highest denomination as much as possible.
                // Is there anything left over (are we done)?
                if(leftover > 0)
                {
                    //I guess there is some left over.

                    if(infoArr[i][leftover-1] != null && !infoArr[i][leftover-1].isEmpty() && infoArr[i][leftover-1].isValid())
                    {
                        print("Use leftovers from this row.\n");
                        infoArr[i][j-1].uses(infoArr[i][leftover-1].coins);
                    }
                    //if we're working with the smallest denomination,
                    // we're unable to look up the chart for previous answers.
                    else if(i+1 == denoms.length)
                    {
                        //Hence, we're unable to make change.
                        print(" We cannot make change with coins up to this denomination. ([Not Optimal]/[No] Previous Answer).\n\n");
                        infoArr[i][j-1].size = Integer.MAX_VALUE;
                        continue;
                    }
                    //if the previous denom's answer is blank,
                    // we can assume that it isn't correct.
                    else if(infoArr[i+1][leftover-1] == null || infoArr[i+1][leftover-1].isEmpty() || !infoArr[i+1][leftover-1].isValid())
                    {
                        print(" We cannot make change with coins up to this denomination.\n");
                        print("  We try using the last denom's info:\n");
                        //we now backtrack, throwing out current algorithm out the window.
                        // therefore, try to use the previous denom's answer.
                        //does it exist?
                        if(!infoArr[i+1][j-1].isEmpty() && infoArr[i+1][j-1].isValid())
                        {
                            //the previous answer had no valid way to make the change. We'll use that.
                            print("   Success!\n");
                            //this arr copies the previous denom's.
                            infoArr[i][j-1] = infoArr[i+1][j-1];
                            infoArr[i][j-1].show();
                            print("\n");
                        }
                        else
                        {
                            //the previous answer had no valid way to make the change.
                            print("   Failure.\n");
                            print(" We cannot make change with coins up to this denomination (optimally?).\n\n");
                            infoArr[i][j-1].size = Integer.MAX_VALUE;
                        }
                        continue;
                    }
                    //if the previous denom's answer is not blank,
                    // and the previous answer exists,
                    // then we combine our greedy answer with the previous leftover answer.
                    else
                    {
                        print(" To get the extras, add "+infoArr[i+1][leftover-1].size+" coins.\n");
                        //we'll combine all of the leftover's coins with our current answer.
                        infoArr[i][j-1].uses(infoArr[i+1][leftover-1].coins);
                    }
                }
                //if the previous answer is valid AND
                // the previous answer's size is smaller than our current+leftover answer AND
                // the previous answer was legitimate (non-zero).
                if(i+1 < denoms.length &&
                        infoArr[i][j-1].size > infoArr[i+1][j-1].size &&
                        infoArr[i+1][j-1].isValid())
                {
                    //then we use the smaller answer (the previous overwrites the current).
                    infoArr[i][j-1] = infoArr[i+1][j-1];
                    print(" However, this method is worse than the previous one,\n  so we're going to not use this denom.\n");
                }
                if(!infoArr[i][j-1].isValid())
                {
                    print(" We cannot make change with coins up to this denomination (optimally?).\n\n");
                    continue;
                }
                print(" We use "+infoArr[i][j-1].size+" coins in total.\n");
                infoArr[i][j-1].show();
                System.out.println();

                if(currentBest == null || currentBest.size > infoArr[i][j-1].size)
                {
                    currentBest = infoArr[i][j-1];
                }
                infoArr[i][j-1] = currentBest;
            }
            print("\n\n");
        }
        if(infoArr[0][c-1].isValid() && !infoArr[0][c-1].isEmpty())
        {
            System.out.println("========================================================");
            System.out.println("It takes "+infoArr[0][c-1].size+" coin"+(infoArr[0][c-1].size>1?"s":"")+" to make "+c+"c.");
            System.out.println("========================================================");
        }
        else
        {
            System.out.println("==================================================================================");
            System.out.println("We cannot make change with coins up to these denominations and change amount of "+c+".");
            System.out.println("==================================================================================");
        }
        return infoArr[0][c-1].size;
    }
    static boolean debug = true;
    public static void print(String str)
    {
        if(debug)
        {
            System.out.print(str);
        }
    }
    public static class info
    {
        public info(){};
        public info(info _greedy){ greedy = _greedy;};
        info greedy;
        HashMap<Integer, Integer> coins = new HashMap<Integer, Integer>();
        int size = 0;

        //Adds information to hashmap.
        // {n: number
        // {c: coins
        //  10x 5c coins would be n=10, c=5
        public boolean uses(int n, int c)
        {
            if(n != 0)
            {
                int previous = 0;
                if(coins.get(c) != null)
                {
                    previous = coins.get(c);
                }
                coins.put(c, n+previous);
                updateSize();
            }
            return isValid();
        }
        //Copies parameter's hashmap.
        public boolean uses(HashMap<Integer, Integer> hm)
        {
            for(Entry<Integer, Integer> e : hm.entrySet())
            {
                int previous = 0;
                if(coins.get(e.getKey()) != null)
                {
                    previous = coins.get(e.getKey());
                }
                coins.put(e.getKey(), e.getValue()+previous);
            }
            updateSize();
            return isValid();
        }
        public void updateSize()
        {
            size = 0;
            for(Entry<Integer, Integer> entry : coins.entrySet())
            {
                size += entry.getValue();
            }
            if(greedy != null && greedy.size < size)
            {
                //If at this point, the greedy algorithm is better, then we disregard this iteration entirely
                // as it will _never_ lead to an optimal answer.
                clear();
                size = Integer.MAX_VALUE;
            }
        }
        public void show()
        {
            for(Entry<Integer, Integer> entry : coins.entrySet()) {
                Integer key = entry.getKey();
                Integer value = entry.getValue();
                if(entry.getValue() != 0)
                    System.out.println("  "+String.format("%3s", key)+"c ("+String.format("%3s", "x"+value)+")");
            }
        }
        public boolean isValid()
        {
            return size != Integer.MAX_VALUE;
        }
        public boolean isEmpty()
        {
            return size == 0;
        }
        public void clear()
        {
            coins.clear();
            updateSize();
        }
    }
}