Coin Changing Problem (Greedy Strategy)

The greedy algorithm always adopts the best solution at the given time, with no regard for how that choice will affect to future choices. Using a greedy algorithm generally indicates that the implementer hopes that the series of “best” local choices made will lead to a final “best” choice. If so, that the algorithm has produced an optimal solution. If not sub optimal solution has been found.

This coin changing problem is following a greedy algorithm strategy. Let’s say some one buy some items at the store and change from his purchase is 103. This 103 can give minimum units of denominators of that particular country. To solve such kind of problems we can use greedy strategy, 100’s > 1, 2’s > 1, 1’s > 1. That is the smallest number of units of coins that will equal to 103.

It has been proven that optimal solutions for coin changing can always current denominations of coins. However if we introduce some other denomination to the mix, the greedy algorithm doesn’t produce an optimal solution.

According to the software implementation minimumChanges subroutine starts with highest denomination 100, and tries to make as much change with them as possible. Once the original amount is less than 100, then algorithm moves to 50, again trying to make as much change with 50 as possible. Then algorithm proceeds to 25, and then 10, 5, 2, 1 respectively.

This greedy algorithm does not always find the optimal solution using the standard coins of the given country. But we must have to find the optimal solution to compare that greedy strategy output. As a result we compare final outcome of greedy strategy and Dynamic programming answer. In dynamic programming it always give optimal answer.

e.g.: coins {1, 2, 5, 10, 20, 25, 50, and 100}

When we find a minimum number of number of coins for 40. The out visible on the console as following.

Dynamic Programming:

No of 20’s: 2

Greedy Strategy:

No of 5’s: 1
No of 10’s: 1
No of 25’s: 1

According to above example we can justify Dynamic approach always give optimal solution for us and Greedy strategy does not give optimal solution always. Because we always choose best available choice for each moment through the greedy algorithm. (Best greedy choice select respectively).

Implementation in C#

GreedyStrategy.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CoinsDenominations
{
    class GreedyStrategy
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Console.Write("User Input of Amount : ");
                string number = Console.ReadLine();//Take the Console input
                int realAmount;
                bool parsed = Int32.TryParse(number, out realAmount);//Parse th input to double
                if (!parsed)//Check whether the output cannot parse to the double
                {
                    Console.WriteLine("\nWARNING : Could not parse '{0}' to an Integer\n", number);
                    if (number.Equals("exit") || number.Equals("EXIT")) {
                        Environment.Exit(0);//Exit from the system
                    }
                }
                else
                {
                    int[] denominations = { 7, 1, 2, 5, 10, 25, 50, 100 };//1 st => size of the list
                    int[] coins = new int[denominations.Length];//Store the # of coins that each denominator
                           
                    Console.WriteLine("\n.....................Result.........................\n");
                    Console.WriteLine("\nDynamic changing values : \n");
                    //Calculate the minimum # of units in dynamic
                    dynamicChanges(realAmount, coins, denominations);
                    //Show the final output of dynamic algorithm
                    showdynamicResult(denominations, coins);
                    Console.WriteLine("\nGreedy changing values : \n");
                    //Calculate the minimum # of units in greedy
                    greedyChanges(realAmount, coins, denominations);
                    //Show the final output of greedy algorithm
                    showgreedyResult(denominations, coins);              
                    Console.WriteLine("\n....................................................\n");
                }
            }
        }

        //Calculate the minimum number of units for given amount (Greedy Strategy)
        private static void greedyChanges(int amount, int[] coin, int[] denomination) {
            int counter;
            Array.Sort(denomination, 1, denomination.Length-1);
            for (int i = 0; i < coin.Length; i++) {
                coin[i] = 0;
            }
            for (counter = coin.Length - 1; counter >= 0 & amount > 0; counter--) {
                coin[counter] = amount / denomination[counter];
                amount -= coin[counter] * denomination[counter];
            }
        }

        //Display the final output on the Console (Greedy Results)
        private static void showgreedyResult(int[] denominations, int[] coins)
        {
            for (int i = 1; i < coins.Length; i++)
            {
                if (coins[i] > 0)
                    Console.WriteLine("Number of " + denominations[i] + "s : " + coins[i]);
            }
        }
  
        //Calculate the minimum number of units for given amount (Dynamic Strategy)
        public static void dynamicChanges(int amount, int[] coin, int[] denomination)
        {
            int n = denomination.Length-1;
            int [][] table = new int[n+1][]; //Tabular format (Table for dynamic approach)
            for (int counter = 0; counter < table.Length; counter++)
                table[counter] = new int[amount + 1];
            int j, k;
            //base case for tabular format
            for ( k = 0; k <= amount; k++ )
                table[0][k] = 0;
            //Tabular Format generating
            for ( j = 1; j <= n; j++ )
            {
                coin[j] = 0; // zeroes in the coins-used vector
                table[j][0] = 0; // column 0 holds zeroes.
                for ( k = 1; k <= amount; k++ )
                    if ( j == 1 )
                        if ( k < denomination[j] )
                            table[j][k] = Int32.MaxValue / 2; // restrict the overflow
                        else
                            table[j][k] = 1 + table[j][k - denomination[j]];
                    else
                        if ( k < denomination[j] )
                            table[j][k] = table[j - 1][k];
                        else//Take the min value
                            table[j][k] = Math.Min(table[j - 1][k], 1 + table[j][k - denomination[j]]);
            }
      
            // Start out walking the table
            j = n; k = amount;
            //Get the coins used from the table
            while ( k > 0 && j > 0 )
                if (table[j][k] == table[j - 1][k]) // denomination not used
                    j = j - 1;
                else // denomination was used
                { ++coin[j]; k = k - denomination[j]; }
        }

        //Display the final output on the Console (Dynamic Results)
        public static void showdynamicResult(int[] denominations, int[] coins) {
            for (int i = 1; i < coins.Length; i++) {
                if(coins[i]>0)
                    Console.WriteLine("Number of " + denominations[i] + "s : " + coins[i]);
            }
        }
    }
}