Coin Problem

[steve65]

Is there a way to mathmatically figure out how many different combinations of coins it would take to make $0.66 cents? and what those combinations are?

I was told it would be 93 different combinations.

Thanks!

[beachbum]

The answer is dead easy in Australia... 0 !! No 1 or 2 cent coins here. I guess if u want foreign devils to answer u might want to list ur coin denominations.

[Nucleus]

I get 87 if you are in the US and paying someone to open the mail for you:

Quarters: 2, Nickles: 1, Dimes: 1, Pennies: 1; Counter: 1
Quarters: 2, Nickles: 1, Dimes: 0, Pennies: 6; Counter: 2
Quarters: 2, Nickles: 0, Dimes: 3, Pennies: 1; Counter: 3
Quarters: 2, Nickles: 0, Dimes: 2, Pennies: 6; Counter: 4
Quarters: 2, Nickles: 0, Dimes: 1, Pennies: 11; Counter: 5
Quarters: 2, Nickles: 0, Dimes: 0, Pennies: 16; Counter: 6
Quarters: 1, Nickles: 4, Dimes: 0, Pennies: 1; Counter: 7
Quarters: 1, Nickles: 3, Dimes: 2, Pennies: 1; Counter: 8
Quarters: 1, Nickles: 3, Dimes: 1, Pennies: 6; Counter: 9
Quarters: 1, Nickles: 3, Dimes: 0, Pennies: 11; Counter: 10
Quarters: 1, Nickles: 2, Dimes: 4, Pennies: 1; Counter: 11
Quarters: 1, Nickles: 2, Dimes: 3, Pennies: 6; Counter: 12
Quarters: 1, Nickles: 2, Dimes: 2, Pennies: 11; Counter: 13
Quarters: 1, Nickles: 2, Dimes: 1, Pennies: 16; Counter: 14
Quarters: 1, Nickles: 2, Dimes: 0, Pennies: 21; Counter: 15
Quarters: 1, Nickles: 1, Dimes: 6, Pennies: 1; Counter: 16
Quarters: 1, Nickles: 1, Dimes: 5, Pennies: 6; Counter: 17
Quarters: 1, Nickles: 1, Dimes: 4, Pennies: 11; Counter: 18
Quarters: 1, Nickles: 1, Dimes: 3, Pennies: 16; Counter: 19
Quarters: 1, Nickles: 1, Dimes: 2, Pennies: 21; Counter: 20
Quarters: 1, Nickles: 1, Dimes: 1, Pennies: 26; Counter: 21
Quarters: 1, Nickles: 1, Dimes: 0, Pennies: 31; Counter: 22
Quarters: 1, Nickles: 0, Dimes: 8, Pennies: 1; Counter: 23
Quarters: 1, Nickles: 0, Dimes: 7, Pennies: 6; Counter: 24
Quarters: 1, Nickles: 0, Dimes: 6, Pennies: 11; Counter: 25
Quarters: 1, Nickles: 0, Dimes: 5, Pennies: 16; Counter: 26
Quarters: 1, Nickles: 0, Dimes: 4, Pennies: 21; Counter: 27
Quarters: 1, Nickles: 0, Dimes: 3, Pennies: 26; Counter: 28
Quarters: 1, Nickles: 0, Dimes: 2, Pennies: 31; Counter: 29
Quarters: 1, Nickles: 0, Dimes: 1, Pennies: 36; Counter: 30
Quarters: 1, Nickles: 0, Dimes: 0, Pennies: 41; Counter: 31
Quarters: 0, Nickles: 6, Dimes: 1, Pennies: 1; Counter: 32
Quarters: 0, Nickles: 6, Dimes: 0, Pennies: 6; Counter: 33
Quarters: 0, Nickles: 5, Dimes: 3, Pennies: 1; Counter: 34
Quarters: 0, Nickles: 5, Dimes: 2, Pennies: 6; Counter: 35
Quarters: 0, Nickles: 5, Dimes: 1, Pennies: 11; Counter: 36
Quarters: 0, Nickles: 5, Dimes: 0, Pennies: 16; Counter: 37
Quarters: 0, Nickles: 4, Dimes: 5, Pennies: 1; Counter: 38
Quarters: 0, Nickles: 4, Dimes: 4, Pennies: 6; Counter: 39
Quarters: 0, Nickles: 4, Dimes: 3, Pennies: 11; Counter: 40
Quarters: 0, Nickles: 4, Dimes: 2, Pennies: 16; Counter: 41
Quarters: 0, Nickles: 4, Dimes: 1, Pennies: 21; Counter: 42
Quarters: 0, Nickles: 4, Dimes: 0, Pennies: 26; Counter: 43
Quarters: 0, Nickles: 3, Dimes: 7, Pennies: 1; Counter: 44
Quarters: 0, Nickles: 3, Dimes: 6, Pennies: 6; Counter: 45
Quarters: 0, Nickles: 3, Dimes: 5, Pennies: 11; Counter: 46
Quarters: 0, Nickles: 3, Dimes: 4, Pennies: 16; Counter: 47
Quarters: 0, Nickles: 3, Dimes: 3, Pennies: 21; Counter: 48
Quarters: 0, Nickles: 3, Dimes: 2, Pennies: 26; Counter: 49
Quarters: 0, Nickles: 3, Dimes: 1, Pennies: 31; Counter: 50
Quarters: 0, Nickles: 3, Dimes: 0, Pennies: 36; Counter: 51
Quarters: 0, Nickles: 2, Dimes: 9, Pennies: 1; Counter: 52
Quarters: 0, Nickles: 2, Dimes: 8, Pennies: 6; Counter: 53
Quarters: 0, Nickles: 2, Dimes: 7, Pennies: 11; Counter: 54
Quarters: 0, Nickles: 2, Dimes: 6, Pennies: 16; Counter: 55
Quarters: 0, Nickles: 2, Dimes: 5, Pennies: 21; Counter: 56
Quarters: 0, Nickles: 2, Dimes: 4, Pennies: 26; Counter: 57
Quarters: 0, Nickles: 2, Dimes: 3, Pennies: 31; Counter: 58
Quarters: 0, Nickles: 2, Dimes: 2, Pennies: 36; Counter: 59
Quarters: 0, Nickles: 2, Dimes: 1, Pennies: 41; Counter: 60
Quarters: 0, Nickles: 2, Dimes: 0, Pennies: 46; Counter: 61
Quarters: 0, Nickles: 1, Dimes: 11, Pennies: 1; Counter: 62
Quarters: 0, Nickles: 1, Dimes: 10, Pennies: 6; Counter: 63
Quarters: 0, Nickles: 1, Dimes: 9, Pennies: 11; Counter: 64
Quarters: 0, Nickles: 1, Dimes: 8, Pennies: 16; Counter: 65
Quarters: 0, Nickles: 1, Dimes: 7, Pennies: 21; Counter: 66
Quarters: 0, Nickles: 1, Dimes: 6, Pennies: 26; Counter: 67
Quarters: 0, Nickles: 1, Dimes: 5, Pennies: 31; Counter: 68
Quarters: 0, Nickles: 1, Dimes: 4, Pennies: 36; Counter: 69
Quarters: 0, Nickles: 1, Dimes: 3, Pennies: 41; Counter: 70
Quarters: 0, Nickles: 1, Dimes: 2, Pennies: 46; Counter: 71
Quarters: 0, Nickles: 1, Dimes: 1, Pennies: 51; Counter: 72
Quarters: 0, Nickles: 1, Dimes: 0, Pennies: 56; Counter: 73
Quarters: 0, Nickles: 0, Dimes: 13, Pennies: 1; Counter: 74
Quarters: 0, Nickles: 0, Dimes: 12, Pennies: 6; Counter: 75
Quarters: 0, Nickles: 0, Dimes: 11, Pennies: 11; Counter: 76
Quarters: 0, Nickles: 0, Dimes: 10, Pennies: 16; Counter: 77
Quarters: 0, Nickles: 0, Dimes: 9, Pennies: 21; Counter: 78
Quarters: 0, Nickles: 0, Dimes: 8, Pennies: 26; Counter: 79
Quarters: 0, Nickles: 0, Dimes: 7, Pennies: 31; Counter: 80
Quarters: 0, Nickles: 0, Dimes: 6, Pennies: 36; Counter: 81
Quarters: 0, Nickles: 0, Dimes: 5, Pennies: 41; Counter: 82
Quarters: 0, Nickles: 0, Dimes: 4, Pennies: 46; Counter: 83
Quarters: 0, Nickles: 0, Dimes: 3, Pennies: 51; Counter: 84
Quarters: 0, Nickles: 0, Dimes: 2, Pennies: 56; Counter: 85
Quarters: 0, Nickles: 0, Dimes: 1, Pennies: 61; Counter: 86
Quarters: 0, Nickles: 0, Dimes: 0, Pennies: 66; Counter: 87

[steve65]

Thank you for your answer Nucleus. I get the idea now. It looks as though your dimes and nickle labels are backwords. To get the 93 combinations you need to add a half dollar.

May I ask how you coded this?

Thanks Again

[Nucleus]

Here is the function:

Sub PossibleChange(ByVal amount As Double, Optional quarters& = -1, Optional nickles&, Optional dimes&)
 
    Dim change$
    Static counter&
    
    If quarters = -1 Then
        counter = 0
        quarters = Int(amount / 0.25)
        nickles = Int(((amount - quarters * 0.25) / 0.1) + 0.0000001)
        dimes = Int(((amount - quarters * 0.25 - nickles * 0.1) / 0.05) + 0.0000001)
    End If
    
    counter = counter + 1
    change = change & "Quarters: " & quarters & ", "
    change = change & "Nickles: " & nickles & ", "
    change = change & "Dimes: " & dimes & ", "
    change = change & "Pennies: " & Int(((amount - quarters * 0.25 - nickles * 0.1 - dimes * 0.05) / 0.01) + 0.0000001)
    Debug.Print change; "; Counter: " & counter
    
    If dimes > 0 Then
        dimes = dimes - 1
        Call PossibleChange(amount, quarters, nickles, dimes)
    Else
        If nickles > 0 Then
            nickles = nickles - 1
            dimes = Int(((amount - quarters * 0.25 - nickles * 0.1) / 0.05) + 0.0000001)
            Call PossibleChange(amount, quarters, nickles, dimes)
        Else
            If quarters > 0 Then
                quarters = quarters - 1
                nickles = Int(((amount - quarters * 0.25) / 0.1) + 0.0000001)
                dimes = Int(((amount - quarters * 0.25 - nickles * 0.1) / 0.05) + 0.0000001)
                Call PossibleChange(amount, quarters, nickles, dimes)
            End If
        End If
    End If
    
End Sub

[Nucleus]

You don't have to use recursion. Here is the change if you were in Australia:

Function PossibleChangeAus(ByVal amnt As Currency)
 
Dim i@, j@, k@, l@, m@, n@, counter&
Dim runningTot1@, runningTot2@, runningTot3@, runningTot4@, runningTot5@, runningTot6@
 
amnt = RoundTo(amnt, 0.05)
Debug.Print amnt
 
i = amnt@ / 2@
For i = Int(i) To 0 Step -1
    runningTot1 = amnt@ - i * 2@
    
    j = runningTot1@ / 1@
    For j = Int(j) To 0 Step -1
        runningTot2 = runningTot1@ - j * 1@
        
        k = runningTot2@ / 0.5@
        For k = Int(k) To 0 Step -1
            runningTot3 = runningTot2@ - k * 0.5@
            
            l = runningTot3@ / 0.2@
            For l = Int(l) To 0 Step -1
                runningTot4 = runningTot3@ - l * 0.2@
                
                m = runningTot4@ / 0.1@
                For m = Int(m) To 0 Step -1
                    runningTot5 = runningTot4@ - m * 0.1@
                            
                    counter = counter + 1
                    
                    n = runningTot5@ / 0.05@
                    Debug.Print "2$: " & i, "1$: " & j, "50c " & k, "20c " & l, _
                        "10c " & m, "5c: " & Fix(n), "Counter:" & counter
                    
                Next m
                
            Next l
        
        Next k
         
    Next j
 
Next i
 
End Function
 
Function RoundTo(ByVal Number@, ByVal Interval@) As Currency
    RoundTo = Sgn(Number) * (Fix((Abs(Number) + Interval / 2) * (1 / Interval)) / (1 / Interval))
End Function

[steve65]

Thanks!

[AbsolutFDM]

For US currentcy, do not forget the Half-Dollar coin!