August 1, 2010
HomeAlgorithms and Data StructuresMake Change Algorithm

Make Change Algorithm

By  Algorithms and Data Structures  0 Comments

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#

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);
        }
    }
}

More from my site

Tags:, ,

About Author

Mohammed Abualrob

Software Engineer @ Cisco

Add a Comment

Your email address will not be published. Required fields are marked *