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).