CODEWITHSUNDEEP
pythondynamic-programming
Eleanor
Eleanor

Reputation: 2847

Change money with python dynamic programming

Here are two programs for change money problem. The first one is only a recursion program that get all combinations and the second one is using dynamic programming. HOWEVER, i get into trouble when I am working on second one. It is supposed to be faster than the first one, but my program runs FOREVER to do it. I am pretty sure that I am using the dynamic programming, but i don't know what's the problem in it?

Notes: Total is the money going to be changed, units is a list with different values and stored is a dictionary to store the value of a step.

First:

def changeMoney(total, units):
    if ( total == 0 ): 
        return [{}]
    elif ( total < 0 ):
        return []
    else:
        n = len(units)
        ret = []
        for i in range(0,n):
            sols = changeMoney(total-units[i],units[i:n])
            for sol in sols:
                if ( units[i] in sol ):
                    sol[units[i]] += 1
                else:
                    sol[units[i]] = 1
            ret.append(sol)
        return ret
print(dpChangeMoney(300,[100,50,20,10,5,2,1],{}))

Second:

import copy
def dpChangeMoney(total, units, stored):
    key = ".".join(map(str,[total] + units))
    if key in stored:
        return stored[key]
    else:
        if ( total == 0 ):
            return [{}]
        elif ( total < 0 ):
            return []
        else:
            n = len(units)
            for i in range(0,n):
                sols = copy.deepcopy(dpChangeMoney(total-
units[i],units[i:n], stored))
                for sol in sols:
                    if ( units[i] in sol ):
                        sol[units[i]] += 1
                    else:
                        sol[units[i]] = 1
                    if key in stored:
                        if sol not in stored[key]:
                            stored[key] += [sol]
                    else:
                        stored[key] = [sol]
        return stored[key]
print(dpChangeMoney(300,[100,50,20,10,5,2,1],{}))

Upvotes: 0

Views: 1132

Answers (2)

Tom Karzes
Tom Karzes

Reputation: 24052

Here's a much faster way to do this:

def dpChangeMoney(total, units, stored, min_ix=0):
    if total < 0:
        return []

    if total == 0:
        return [{}]

    if min_ix == len(units):
        return []

    key = (total, min_ix)
    if key in stored:
        return stored[key]

    sol_list = []
    u = units[min_ix]
    for c in range(total // u + 1):
        sols = dpChangeMoney(total - c*u, units, stored, min_ix + 1)
        for sol in sols:
            if c > 0:
                sol2 = sol.copy()
                sol2[u] = c
            else:
                sol2 = sol
            sol_list.append(sol2)

    stored[key] = sol_list
    return sol_list

If invoked as follows, it prints the number of solutions for the specified case:

print(len(dpChangeMoney(300, [100,50,20,10,5,2,1], {})))

The result is:

466800

On my system this took well under a second to run. (Of course, you could print the actual solutions, but there are a lot!)

To see the actual solutions for a total of 10:

print(dpChangeMoney(10, [100,50,20,10,5,2,1], {}))

The result is:

[{1: 10}, {1: 8, 2: 1}, {1: 6, 2: 2}, {1: 4, 2: 3}, {1: 2, 2: 4}, {2: 5}, {1: 5, 5: 1}, {1: 3, 2: 1, 5: 1}, {1: 1, 2: 2, 5: 1}, {5: 2}, {10: 1}]

Upvotes: 1

Eleanor
Eleanor

Reputation: 2847

i just figure out what is the problem in my algorithm. I will update a much faster algorithm after the due date. Thanks for your suggestions and instructions. E

Upvotes: 0

Related Questions