QuestionQuestion

Coin Change Problem
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 CashRegister.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.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

package CashRegister;

//package;

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
         */

       Arrays.sort(denominations);
       if (denominations[0] !=1 )
            throw new Exception("Denomination 1 must always be presented");

       this.denominations = denominations;
    }

    /**
    * 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) {
       return makeChange(value, denominations.length-1);
    }

    public int [] makeChange...

By purchasing this solution you'll be able to access the following files:
CashRegister.java.

$16.10
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats