The Coin Changing Problem!
October 31, 2010 1 Comment
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).