Solving coin denomination problem using Greedy Approach

Suppose we have coins of the following denominations : 100, 50, 25, 10, 5, 2, 1. Our task is to devise an algorithm for paying a given amount to a customer using the smallest possible number of coins.  For example the minimum possible number of coins to pay 289/- would be 7.

 i.e 2x100+1x50+1x25+1x10+2x2

Greedy approach

Naive way of doing this is to follow a greedy approach. That is by choosing the largest possible coin at every step, without worrying whether this will lead to a sound decision at the end. Thus choosing the largest coin denomination is the greedy choice.   

My Java implementation for this looks like below.

    

1:     Stack find(int amount){      
2:      // initially we considering the largest available coin      
3:      int largestSelectedCoin = coins.length-1;     
4:      Stack stack = new Stack(); // to track coins being selected      
5:      // loop until the amount exists  
6:      while(amount>0){        
7:      // if the amount is greater than or equals to the largest coin under consideration, we can make a denomination using the largest coin        
8:      if(coins[largestSelectedCoin]<=amount){        
9:        // how many of the largest coin under consideration can use at maximum   
10:        int numberOfSelectedCoins = (int) Math.floor(amount/coins[largestSelectedCoin]);        
11:        // remainder to be changed  
12:        int remainder = amount%coins[largestSelectedCoin];        
13:        // push the coins to stack  
14:        for(int i=0;i<numberOfSelectedCoins;i++){  
15:          stack.push(coins[largestSelectedCoin]);          
16:        }        
17:        // adjust the amount to remainder  
18:        amount =remainder;        
19:        //let the largest coin under consideration to be the next lowest coin  
20:        largestSelectedCoin--;        
21:      }else{  
22:        // if the value of largest coin under consideration is greater than the amount go for the next available largest coin  
23:        largestSelectedCoin--;  
24:      }  
25:      }      
26:      return stack;      
27:    }  

Above method takes the amount to be checked and find the coin denomination to resolve that amount and put the output sequence of the coins to a stack. In order to test the code I wrote a simple console application which take the amount from the user and out put the sequence of coins that result the minimum number of coins. Here I’m assuming that the coin denomination is stored in an array named coins.

1:   public static void main(String[] args) {  
2:       System.out.println("Available coin denomination : ");  
3:       for(int i = 0 ; i < coins.length;i++){  
4:            System.out.print(coins[i] + ", ");  
5:       }      
6:     System.out.println("\nEnter the amount to be changed : ");  
7:     Scanner scanner = new Scanner(System.in);  
8:     int amount =scanner.nextInt();  
9:     CoinDenominator coinDenominator = new CoinDenominator();  
10:     Stack stack= coinDenominator.find(amount);  
11:     System.out.println("Number of coins = " + stack.size());  
12:     Iterator i= stack.iterator();  
13:     System.out.println("change for " + amount+" : ");  
14:     while(i.hasNext()){       
15:       System.out.println("  " + i.next());       
16:     }  
17:    }  

Execution of this program for the coin denomination {1, 2 , 5, 10, 25, 50, 100} gave the below result.

However it is noteworthy that the greedy approach is solving this coin denomination problem only for certain coin denominations. For example an attempt to use a greedy approach under the coin denomination of {1,5,12}would yield an incorrect result as below. 

Hence we can conclude that the Greedy approach is not giving the optimal solution for all sort of coin denominations.