# The Coin Changing Problem!

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
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!. 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 CoinChangingProblem.zip(remove the .doc extension).