Optimizing Change Making Solution

Question

I have written a Python solution here which solves the following problem: how can a given amount of money n be made with the least number of coins of given the denominations d?

def min_coin_change(n, d):
    mini = float("inf")
    for den in d:
        diff = n - den
        if diff == 0:
            ans = 1
        elif diff < 0:
            ans = float("inf")
        else:
            ans = 1 + min_coin_change(n - den, d)
        mini = min(mini, ans)
    return mini

While my solution works, it takes a very long time when n is larger than 50 or when the length of d is larger than 5. How can I speed up my code so it will work for considerably larger inputs? Am I missing a trick or something which would drastically speed up my code?

Answer 1

Note that you should set up your function to start with the largest coin, loop through for the maximum possible number of largest coins, then repeat with the next largest coin.

Thus den should be sorted in decreasing order

def changecoin(d, denval)
  count = 0
  while d > denval:
    d -= denval
    count += 1
  return count, d

now call the recursion with the next lowest value of denval and the new d valueand increment the count appropriately.

newcount = 0
for denval in den:
    count, d = changecoin(d, denval)
    newcount += count

Actually, looking at the code, the changecoin function can be somewhat fixed by eliminating the while so that the inline code can be written

count = 0
for denval in den
  count += d//denval
  d = d % denval

This returns the count and whatever value is left in d. If d is less than denval, the count increment would be 0 and the remaining d is unchanged. While the for loop is unbroken when d becomes 0, there are few enough entries in den that the test can be left out

  if d < 1:
    break

Answer 2

Can we assume that the coin denominations are sensible? The general case of this problem would allow for strange coin denominations like [100, 90, 1] and a simple "greedy" algorithm won't find optimal solutions (e.g. for 180 the optimal solution is two 90-cent pieces, while the simple greedy algorithm would suggest one 100-cent piece and 80 pennies).

If we can assume sensible currency (like any real currency) then I suggest you use a combination of integer division and modulus to find how many of each coin to use.

If we cannot assume sensible currency, then this problem is ideal for a dynamic programming solution. In dynamic programming, you build a table that memoizes intermediate results, which saves a lot of time compared to the simple recursive solution.

There is a nice explanation of dynamic programming in the Skiena book The Alogorithm Design Manual.

http://www.algorist.com/

Here are some links I found online:

http://www.avatar.se/molbioinfo2001/dynprog/dynamic.html

http://www.codechef.com/wiki/tutorial-dynamic-programming

Answer 3

This is because it is recursive

Read this What is memoization and how can I use it in Python? (and the top 2 answers)

"memoization" remembers things you have calculated already (eg 10 cents) so you don't recalculate them an exponential number of times.

You can copy the Mwmoize class as is, and just "decorate" your function, as explained in the second answer

---

FOR THE LAZY

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]

then add the decorator before the definition

@Memoize
def min_coin_change(n,d)......

the rest of the function is the same

then you call it

min_coin_change(30,(25,10,5,1))

Answer 4

Here is a faster version of your program. I've changed two things:

• Implementation detail: all recursive programs can be re-written as equivalent iterative programs (in this case, using a for and a while loop). In most languages, the iterative version is faster as there is no need to maintain a stack.

• Algorithm: I am using a greedy algorithm that starts off with the largest-value coins first, and then tries the smaller coins. This is not guaranteed to be optimal, as pointed out in other answers, but runs very fast (linear in the number of coins in the returned solution). Have a look at this page for an optimal (but slower) dynamic programming solution.

def min_coin_change2(n, d):
    current_amount = 0
    used_coins = []

    for coin_value in sorted(d, reverse=True):
        while n - current_amount >= coin_value:
            current_amount += coin_value
            used_coins.append(coin_value)

    excuse = '' if current_amount == n else ', but that is not what you asked for'
    return 'I can get to %d using %s%s' % (current_amount, used_coins, excuse)

Let's try it out:

print min_coin_change2(101, [50, 20, 10, 1])
Out[25]: 'I can get to 101 using [50, 50, 1]'

and again, when it is impossible to get the desired amount

print min_coin_change2(101, [50, 20, 10])
Out[26]: 'I can get to 100 using [50, 50], but that is not what you asked for'

and again, when the greedy algorithm finds a sub-optimal solution

print min_coin_change2(180, [100, 90, 20])
Out[2]: 'I can get to 180 using [100, 20, 20, 20, 20]'

but the optimal solution would have been [90, 90]