import java.util.Arrays

You should not change name of the class or any other function already defined in the class or the package name. You just need to complete the code specified in the constructor and the makeChange() funcion.

import java.util.Arrays;

public class CashRegister {

private int [] denominations;

/** * Constructor * @param denominations values of coin types not in any order * @throws Exception when a coin of denomination 1 does not exist */ public CashRegister(int [] denominations) throws Exception { /** * Complete code here */ }

/** * Make change for value * @param value * @return array of same length as denominations array that specifies * coins of each denomination to use in making given change * with minimum number of coins */ public int [] makeChange(int value) { /** * Complete code here */ }

/** * Specifies description of change in coins * @param coins * @return */ public void printValues(int [] coins) { StringBuilder builder = new StringBuilder(); int totalCoins = 0; for (int i=0; i 0) { if (builder.length() > 0) { builder.append(","); } builder.append(coins[i] + " coins of value " + denominations[i]); totalCoins += coins[i]; } } builder.append(" for a total of " + totalCoins + " coins"); System.out.println(builder.toString()); }

public static void main(String [] args) throws Exception { CashRegister reg = new CashRegister(new int [] {50, 25, 10, 5, 1}); System.out.println("Change for " + 48 + ":"); // should have a total of 6 coins reg.printValues(reg.makeChange(48)); System.out.println("Change for " + 56 + ":"); // should have a total of 3 coins reg.printValues(reg.makeChange(56)); reg = new CashRegister(new int [] {25, 10, 1}); System.out.println("Change for " + 33 + ":"); // should have a total of 6 coins reg.printValues(reg.makeChange(33)); reg = new CashRegister(new int [] {1, 7, 24, 42}); System.out.println("Change for " + 48 + ":"); // should have a total of 2 coins reg.printValues(reg.makeChange(48)); reg = new CashRegister(new int [] {50, 1, 3, 16, 30}); System.out.println("Change for " + 35 + ":"); // should have a total of 3 coins reg.printValues(reg.makeChange(35)); } }

It's supposed to return the fewest amount of coins you can use to make any cent value. Only using the available denominations (coin value) that they give for each one.

In this assignment, you will be implementing a program for solving coin change problem using recursion. Imagine you are working for a company called Cash Register Advanced Products (the company strongly prefers not using the acronym for the company name!!). This company builds electronic cash registers to be employed in many countries with different coin systems similar to dollars, dimes, quarters, pennies etc. Your program will be used to make change for a value given an array of coin types (denominations) that are allowed in making the change. To make the problem simple. we will assume that there is an infinite supply of coins of each denomination. Since customers prefer to get smallest number of coins for the change, the problem is to determine minimum number of coins using the giving denominations to make the change. For example, in U.S., if we want to make change for 48 cents from quarters, dimes. nickels and pennies, we can give out 1 quarter, 2 dimes and 3 pennies. Using the greedy approach of using as many coins of higher denomination as possible before making remaining change for lower denominations will not always work. Consider making change for 33 cents from quarters, dimes and cents only, if you use greedy approach, we will use 1 quarter and 8 pennies for a total of 9 coins while using 3 dimes and 3 pennies will yield the best solution of 6 coins. You need to complete the following in Cash Register.java file: (a) constructor CashRegister(). You need to make sure coin denomination value of 1 always exists in the denominations array which may not be in ascending order of denomination values. If it does not exist you need to throw an exception. (b) function makeChange. This function should call a recursive function to make change for the given amount. public class CashRegister { private int ( denominations; * Constructor * @param denominations values of coin types not in any order * @throws Exception when a coin of denomination 1 does not exist public Cash Register(int i) denominations) throws Exception { /* * * Complete code here /** * Make change for value * @param value f same length as denominations array that specifies coins of each denomination to use in making given change with minimum number of coins */ public int ( makeChange(int value) { * Complete code here * Specifies description of change in coins * @param coins * @return public void printValues(int Ucoins) { StringBuilder builder = new StringBuilder(); int totalCoins = 0; for (int i=0; i 0) { if (builder.length() > 0) { builder.append(","); builder.append(coins[i] + " coins of value " + denominations[i]); totalCoins += coins[i]; builder.append(" for a total of " + totalCoins + " coins"); System.out.println(builder.toString()); public static void main(String [] args) throws Exception { CashRegister reg = new Cash Register(new int [] {50, 25, 10, 5, 1}); System.out.println("Change for " + 48 + ":"); // should have a total of 6 coins reg.printValues (reg.makeChange (48)); System.out.println("Change for " + 56 + ":"); // should have a total of 3 coins reg.printValues (reg.makeChange (56)); reg = new CashRegister (new int [ {25, 10, 1}); System.out.println("Change for " + 33 + ":"); // should have a total of 6 coins reg.printValues (reg.makeChange (33)); reg = new CashRegister (new int [ {1, 7, 24, 42}); System.out.println("Change for " + 48 + ":"); // should have a total of 2 coins denominations) throws Exception public CashRegister(int * Complete code here /** /** * Make change for value * @param value * @return array of same length as denominations array that specifies coins of each denomination to use in making given change with minimum number of coins * / public int makeChange(int value) { /** * Complete code here * Specifies description of change in coins * @param coins * @return public void printValues(int coins) { StringBuilder builder = new StringBuilder(); int totalCoins = 0; for (int i=0; i 0) { if (builder.length() > 0) { builder.append(", "); builder.append(coins[i] + " coins of value " + denominations[i]); totalCoins += coins[i]; builder.append(" for a total of " + totalCoins + " coins"); System.out.println(builder.toString()); public static void main(String [] args) throws Exception { CashRegister reg = new CashRegister(new int [ {50, 25, 10, 5, 1}); System.out.println("Change for " + 48 + ":"); // should have a total of 6 coins reg.printValues (reg.makeChange (48)); System.out.println("Change for " + 56 + ":"); // should have a total of 3 coins reg. printValues (reg.makeChange (56)); reg = new CashRegister (new int [ {25, 10, 1}); System.out.println("Change for " + 33 + ":"); // should have a total of 6 coins reg.printValues (reg.makeChange (33)); reg - new CashRegister (new int [ {1, 7, 24, 42}); System.out.println("Change for " + 48 + ":"); // should have a total of 2 coins reg.printValues (reg.makeChange (48)); reg - new CashRegister (new int [ {50, 1, 3, 16, 30}); System.out.println("Change for " + 35 + ":"); // should have a total of 3 coins reg.printValues (reg.makeChange (35))