methodology for making change

[JPicasso]

I need to program a methodology very similar to making change for a dollar.

Say I have a value to obtain, 100 cents.

I have 1 cent, 5 cent, 10 cent, 25 cent pieces to do it with.

What would be the best methodology to figure out how many differnt ways I could make change?

I need to program some thing like this and how it goes now takes forever.
Actually, someone else on my team needs to do this and he is stuck, so I'd like
to swoop in and rescue the whole thing, you know?

anyways. anyone got any suggestions?

[wossname]

Short of doing a brute force search, I can't think of a way of doing it.

[alkatran]

Well, think of it this way:

Make a few main groups. For example, make a "four quarters" dollar, etc. How many ways can you split a quarter? That number ^ 4. Do the same thing for dimes etc.

Now, loop through that and take out any doubles. (Does order matter?)

If order doesn't matter it gets a hell of a lot simpler.

[alkatran]

for a = 0 to 4
for b = 0 to 10
for c = 0 to 20
for d = 0 to 100
if 25*a+b*10+c*5+d = 100 then
   debug.print "Q:" & a & ", D:" & b & "N:" & c & "P:" & d
end if
next d
next c
next b
next a

Total loops: 4*10*20*100 = 40*2000 = 80 000

Time to execute: Took like half a second

[alkatran]

There, EVERYTHING.

Private Sub Form_Load()
Dim Ordered As Double
Dim Disordered As Long
Dim A As Long
Dim B As Long
Dim C As Long
Dim D As Long
 
    For A = 0 To 4
    For B = 0 To 10
    For C = 0 To 20
    For D = 0 To 100
        If 25 * A + B * 10 + C * 5 + D = 100 Then
            Disordered = Disordered + 1
            Ordered = Ordered + Fact(A + B + C + D) / (Fact(A) * Fact(B) * Fact(C) * Fact(D))
            Debug.Print "Q:" & A & ", D:" & B & ", N:" & C & ", P:" & D
        End If
    Next D
    Next C
    Next B
    Next A
    MsgBox "There are " & Disordered & " combinations and " & Ordered & " permutations.", vbOKOnly, "Results"
    Unload Me
End Sub
 
Private Function Fact(ByVal X As Long)
Dim A As Long
    
    Fact = 1
    For A = 2 To X
        Fact = A * Fact
    Next A
End Function

242 combinations, 8 577 828 731 901 permutations

[sql_lall]

hehe...where's the sophisticated algorithmic development?

I would recommend having a function that returns the number of ways to make X cents with the highest coin being the Yth in the series (25, 10, 5, 1) .

You then call it recursively, caching results.

For instance (in C++ pseudo-code for my convenience

int ways(int X, int Y)
{
    if(Y == 3)
        return 1; // 1 way of making X cents with 1 cent pieces

    int ret = 0;
    for(int a = 0; a <= X; a+=coin[Y]) // each number of current coin
        ret += ways(X - a, Y + 1);
    
    return ret;
}

As I said before, you would do some caching (i.e. saving results to array) to make it a bit quicker. The array would be two-dimensional, indexed by the X and Y parameters.
}

[alkatran]

My algorythm is fast enough to do the job in under a second (on my 1.2 .. or was it 1.8.. ghz system)... why would I want to make an overly complicated algo?

[alkatran]

Tell you what though, I'll optimize:

Private Sub Form_Load()
Dim Ordered As Double
Dim Disordered As Long
Dim A As Long
Dim B As Long
Dim C As Long
Dim D As Long
 
    For A = 0 To 4
    For B = int(A*2.5) To 10
    For C = A*5+B*2 To 20
        If 25 * A + B * 10 + C * 5 < 100 Then
            D = 100-25a-10b-5c
            Disordered = Disordered + 1
            Ordered = Ordered + Fact(A + B + C + D) / (Fact(A) * Fact(B) * Fact(C) * Fact(D))
            Debug.Print "Q:" & A & ", D:" & B & ", N:" & C & ", P:" & D
        End If
    Next C
    Next B
    Next A
    MsgBox "There are " & Disordered & " combinations and " & Ordered & " permutations.", vbOKOnly, "Results"
    Unload Me
End Sub
 
Private Function Fact(ByVal X As Long)
Dim A As Long
        Fact = 1
    For A = 2 To X
        Fact = A * Fact
    Next A
End Function

That should shrink the run time a very large amount since it reduces the length to at LEAST 1% of what it was.

[wossname]

OK does anyone have the algorithm to generate £50 notes?

[alkatran]

Now I'm embarrased. That code was awful. But I couldn't check it where I was. So here's the fixed one.

Private Sub Form_Load()
Dim Ordered As Double
Dim Disordered As Long
Dim A As Long
Dim B As Long
Dim C As Long
Dim D As Long
 
    For A = 0 To 4
    For B = 0 To 10 - Int(A * 2.5)
    For C = 0 To 20 - 5 * A - 2 * B
        If 25 * A + B * 10 + C * 5 <= 100 Then
            D = 100 - 25 * A - B * 10 - C * 5
            Disordered = Disordered + 1
            Ordered = Ordered + Fact(A + B + C + D) / (Fact(A) * Fact(B) * Fact(C) * Fact(D))
            Debug.Print "Q:" & A & ", D:" & B & ", N:" & C & ", P:" & D
        End If
    Next C
    Next B
    Next A
    MsgBox "There are " & Disordered & " combinations and " & Ordered & " permutations.", vbOKOnly, "Results"
    Unload Me
End Sub
 
Private Function Fact(ByVal X As Long)
Dim A As Long
    
    Fact = 1
    For A = 2 To X
        Fact = A * Fact
    Next A
End Function

[alkatran]

and by the way that algorythm takes 5 milliseconds to find the answer. I think that's acceptable.

[alkatran]

Haha, I changed the program so that it will generate the number for 50$ (including pennies, nickels.. all the way to twenties)

It's been running for awhile now.

It just did its first "10" iteration.


I have two longs set up.. when one gets over a billion it adds 1 to the second.. I was worried about overflow.

[alkatran]

Today I learned there's almost 4 billion ways to make change for a 50$ bill.
(3 9## ### ###)

and it only took 37.5 minutes.