Click here to Skip to main content
Click here to Skip to main content

The Coin Changing Problem!

, 1 May 2011
Rate this:
Please Sign up or sign in to vote.
The coin changing problem is a known problem in the field of algorithms and a famous example in Dynamic Programming which is one of the good ways for making a good coin change.

The coin changing problem is a known problem in the field of algorithms and a famous example in Greedy Algorithms which is one of the good ways for a making a good coin change. The problem states that “given a set of coins with several values, it is required to make a change using those coins for a particular amount of cents using the minimum number of coins”.

As we mentioned earlier, a greedy algorithm solution is known which is, in fact, how millions of people change money every day. That is, start changing with the largest coin available until the remaining amount to change is less than the largest coin value, then start changing with the next possible coin(the coin with the lower value). Continue with repeated changing until there are no more cents left to change. Below is the VB.NET implementation of a simple coin changer using the above algorithm:

Private Function SetAvailableCoins(ByVal strCoins As String, _
                               ByRef Coins() As Int64) As Boolean
    Dim coinsstr() As String = strCoins.Split(","c)
    ReDim Coins(coinsstr.Length - 1)
    For i As Int64 = 0 To coinsstr.Length - 1
        If Not IsNumeric(coinsstr(i)) Then
            Erase Coins
            Return False
        Else
            Coins(i) = coinsstr(i)
        End If
    Next
    Return True
End Function

Private Function MakeChange(ByVal Amount As Int64, _
                            ByRef Coins() As Int64) As String
    Dim value As Int64 = Amount
    Dim str As String = String.Empty
    Dim count As Int64 = 0
    While value > 0
        Dim maxCoin As Int64 = 0
        For Each c As Int64 In Coins
            If c  maxCoin Then
                maxCoin = c
            End If
        Next
        Dim change As Int64 = Math.Floor(value / maxCoin)
        value -= change * maxCoin
        str &= change & " Coin(s) of value " & maxCoin & _
                 " (Remaining = " & value & ")" & vbCrLf
        count += change
    End While
    str &= vbCrLf & "Total number of coins = " & count
    Return str
End Function

Private Sub btnChange_Click(ByVal sender As System.Object, _
            ByVal e As System.EventArgs) Handles btnChange.Click
    Dim coins(0) As Int64
    If txtCoins.Text  "" AndAlso SetAvailableCoins(txtCoins.Text, _
                                                     coins) Then
        txtChange.Text = MakeChange(txtAmount.Value, coins)
    End If
End Sub

The functions above assume you have created the form below and added the appropriate controls:

In the example shown in the form above, we have 4 coins with values: 1,5,10 and 25. The amount we would like to change is 36. When we click on the change button the result is displayed in the Change Textbox. Notice the result consists of 1 coin of value 25,1 coin of value 10 and 1 coin of value 1. This is in fact the optimal solution to the given amount of cents. Lets consider another for the value 30, as we would expect, the results will be 1 coin of value 25 and 1 coin of value 5 which is also the optimal solution. Now lets suppose we had only 3 coins instead of 4 by removing the coin of value 5 and we want to make change for 30 cents again. The results are displayed below:

As you can see, the change is 1 coin of value 25 and 5 coins of value 1 giving a sum of 6 coins!. Of course, this is not an optimal solution because a human would have suggested to use 3 coins of value 10!. The reason for the error here is because greedy algorithms do not guarantee an optimal solution although they guarantee to find a solution in a reasonable amount of time. Assume we have millions of coin values and we want to make a change for an extremely large amount, it is not possible to be done by a human being! here is where the greedy algorithm we discussed comes into play.

The project is downloadable here here (remove the .doc extension).

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Ali Tarhini
Software Developer (Senior) Microgen
Lebanon Lebanon
For more articles and extreme topics please check out my personal website www.alitarhini.com

Comments and Discussions

 
GeneralMy vote of 3 Pinmemberwtwhite11-May-11 5:18 
GeneralSeveral errors [modified] PinmemberKP Lee9-May-11 22:47 
GeneralMy vote of 1 Pinmemberkarabax2-May-11 5:49 
GeneralImages... PinmemberJohnny J.2-May-11 0:53 
QuestionError:( Pinmemberhitesh140726-Jan-10 20:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140721.1 | Last Updated 2 May 2011
Article Copyright 2010 by Ali Tarhini
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid