Write a program that implements change making solution. Assume that the cashier has currency notes in the denominations Rs. 100, Rs. 50, Rs. 20, Rs. 10, Rs. 5 and Rs. 1 in addition to coins . Program should include a method to input the purchase amount and the amount given by the customer as well as method to output the amount of change and a breakdown by denomination. Apply greedy algorithm at the cahier side that is give less number of coins if sufficient currency of that denomination available.

The change-making problem addresses the following question: how can a given amount of money be made with the least number of coins of given denominations?

It can be solved by dynamic  dynamic programming or greedy approach.we will see an example of solving making change problem using greedy approach.

So,lets see one example of making change problem;

Write a program that implements change making solution. Assume that the cashier has currency notes in the denominations Rs. 100, Rs. 50, Rs. 20, Rs. 10, Rs. 5 and Rs. 1 in addition to coins . Program should include a method to input the purchase amount and the amount given by the customer as well as method to output the amount of change and a breakdown by denomination. Apply greedy algorithm at the cahier side that is give less number of coins if sufficient currency of that denomination available.

import java.util.Scanner;
 
public class Change {
	private int[] denom;
	Change( int[] denom) {	
		this.denom = denom;
	}
	void giveChange(int changeRs) {	
		System.out.println("\nChange for " + changeRs + " in Rs " + ":");
		for(int i = 0; i < denom.length; ++i) { int nb = changeRs / denom[i]; if(nb > 0) 
				System.out.println(nb + " " + denom[i]);
			changeRs %= denom[i]; 
		}
	}
	public static void main(String[] args) { 
                 int[] Rs = {100,50,20,10,5,1};  
                Scanner input=new Scanner(System.in);
                System.out.println("Enter the purchase amount : ");
                int purchaseAmount=input.nextInt();
                System.out.println("Enter the amount given by customer : ");
                int AmountGivenByCusto=input.nextInt();
                if(AmountGivenByCusto<purchaseAmount){
                    System.out.println("Sorry! you paid less than purchase amount!  ");                    
                }else
{
                int result=AmountGivenByCusto-purchaseAmount;
		Change change1 = new Change( Rs);
		change1.giveChange(result);
                }			
	}
}

OUTPUT: