The Coin Changing Problem!

Greedy algorithm change diagram

Image via Wikipedia

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 chaning 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
            Coins(i) = coinsstr(i)
        End If
    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
        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!. Offoucrse, 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 becuase 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 the .doc extension).


One Response to The Coin Changing Problem!

  1. jimjam aris says:

    mr please reupload the program thanks

Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: