[Programación dinamica] Problema de los billetes

Main.java

import java.util.*;

public class Main {
    static Scanner read = new Scanner(System.in);
    public static void main(String[] args) {
        System.out.print("Enter the amount of change to get: ");
        int change = read.nextInt();

        utilsBill algorithm = new utilsBill(new int[]{1,4,6}, change);
        algorithm.fillTables();
        ArrayList<Integer> bills = algorithm.getCantBill();
        algorithm.showChange(bills);
    }
}

class Utils{
    public static int getRand(){  return new Random(199).nextInt() + 25;  }
}

class utilsBill {
    private final Map<Integer, Integer> bills = new HashMap<>();
    private Boolean [][]tableBool;
    Scanner read = new Scanner(System.in);
    int change;

    public ArrayList<Integer> BillsReturned;

    public void fillBills(){
        bills.put(1,0);
        System.out.print("Random quantity? (Y:1 / N:0): ");
        int n;
        int decision = read.nextInt();
        if(decision == 1){
            do {
                System.out.print("Enter the denomination of the bill: ");
                n = read.nextInt();
                if(n == 0) break;
                bills.put(n,Utils.getRand());
            }while(true);
        }
        else{
            int quantity;
            do {
                System.out.print("Enter the denomination of the bill: ");
                n = read.nextInt();
                if(n == 0) break;
                System.out.print("Enter the denomination of the bill: ");
                quantity = read.nextInt();
                if(quantity == 0) quantity = Utils.getRand();
                bills.put(n,quantity);
            }while(true);
        }
    }

    public void fillBills(int []arr){
        bills.put(1,0);
        for (int element : arr){
            bills.put(element, Utils.getRand());
        }
    }

    public utilsBill(){ }
    public utilsBill(int change){
        this.change = change;
        fillBills();
    }

    public utilsBill(int []Arr, int change){
        this.change = change;
        fillBills(Arr);
    }

    public void fillTables(){
        System.out.println("\nTable of values: ");
        int n = bills.size(), v = change +1, j = 0;
        int[][] table = new int[n][v];
        tableBool = new Boolean[n][v];
        int[] keys = new int[bills.size()];

        for(Map.Entry<Integer, Integer> mapEntry : bills.entrySet()) {
            keys[j] = mapEntry.getKey(); j++;
        }

        System.out.print("$" + keys[0] + " |\t");
        for(j = 0; j < v; j++){
            table[0][j] = j;
            tableBool[0][j] = true;
            System.out.print( table[0][j] + " \t");
        }

        System.out.println();
        for(int i = 1; i < n; i++){
            int value = Math.min(change, keys[i]);
            System.out.print("$" + keys[i] + " |\t");
            for(j = 0; j < value; j++){
                table[i][j] = j;
                tableBool[i][j] = false;
                System.out.print(table[i][j] + " \t");
            }
            for(j = value; j < v; j++){
                int one = j/keys[i] + table[i-1][j%keys[i]];
                int two = table[i-1][j];
                table[i][j] = Math.min(one, two);
                tableBool[i][j] = one < two;
                System.out.print(table[i][j] + " \t");
            }
            System.out.println();
        }
    }

    public ArrayList<Integer> getCantBill(){
        BillsReturned = new ArrayList<>();
        int i = bills.size()-1, j = change, n = 0;
        int[] keys = new int[bills.size()];
        for(Map.Entry<Integer, Integer> mapEntry : bills.entrySet())
            keys[n++] = mapEntry.getKey();

        while(i >= 0){
            if(!tableBool[i][j]){
                i--;
            } else {
                int d = keys[i];
                int left = j - d;
                BillsReturned.add(d);
                if(left == 0) break;
                j = left;
            }
        }
        return BillsReturned;
    }

    public void showChange(ArrayList<Integer> changeReturned){
        System.out.println("\nReturned bills: ");
        for (Integer integer : changeReturned) {
            System.out.print("$" + integer + " \t");
        }
    }
}