August 1, 2010
Make Change Algorithm
Problem
Given an amount of money in US currency. Give an algorithm to make change of the given amount using the smallest possible number of coins. Recall that US coins are Dollars (100 cents), Quarters (25 cents), Dimes (10 cents), Nickels (5 cents) and Pennies (1 cent)
Solution
A greedy approach to solve this problem works by making the decision that seems most promising at any moment. We start with an empty set of coins then at every stage without passing the given amount we add the largest to the coins already chosen. For example if the amount is $2.88 then the solution contains 2 dollars, 3 quarters, 1 dime and 3 pennies
Code
Here is the solution in C#
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace MyChangeMaker { class ChangeMaker { //Those are simply counters private int dollar = 0; private int quarter = 0; private int dime = 0; private int nickel = 0; private int penny = 0; //Make change method public void MakeChange(float money) { //Convert amount to cents int m = (int) (money * 100); //Sum must not exceed amount int sum = 0; //Keep adding to the sum selecting the largest //coin until we exceed the amount needed while (sum != m) { if (sum + 100 <= m) { dollar++; sum += 100; } else if (sum + 25 <= m) { quarter++; sum += 25; } else if (sum + 10 <= m) { dime++; sum += 10; } else if (sum + 5 <= m) { nickel++; sum += 5; } else if (sum + 1 <= m) { penny++; sum += 1; } else { //Do nothing } } //Write output Console.WriteLine(money + " ="); Console.WriteLine(dollar + " dollars"); Console.WriteLine(quarter + " quarters"); Console.WriteLine(dime + " dimes"); Console.WriteLine(nickel + " nickels"); Console.WriteLine(penny + " pennies"); } } class Program { static void Main(string[] args) { float money = 2.88f; ChangeMaker cm = new ChangeMaker(); cm.MakeChange(money); } } } |