In this article, we will discuss an optimal solution to solve Coin change problem using Greedy algorithm. We will solve the problem in C# Console App.
Given a set of coins, and an amount of change we need to return, we are asked to calculate the number of ways we can return the correct change, given our set of coins.
For an example, Let’s say you buy some items at the store and the change from your purchase is 63 cents. How does the clerk determine the change to give you? If the clerk follows a greedy algorithm, he or she gives you two quarters, a dime, and three pennies. That is the smallest number of coins that will equal 63 cents.
C# Console Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | class Program { static void Main(string[] args) { int[] coins = {25, 10, 5, 1 }; int amount, count, i; Console.Write("Enter the amount you want to change : "); amount = Convert.ToInt32(Console.ReadLine()); Console.WriteLine("=========================="); for (i = 0; i <coins.Length; i++) { count = amount / coins[i]; if (count != 0) Console.WriteLine("Count of {0} cent(s) :{1}",coins[i],count); amount %= coins[i]; } Console.ReadLine(); } } |
Output:
