Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive change-making algorithm

Given a target amount and a list of coin denominations, my code is supposed to find the fewest coins needed to reach the target amount.

Examples:

  • C(78, [1, 5, 10, 25, 50]) = 6

    • we can make 78 from 3x25 + 3x1, so 6 coins are required
  • C(48, [1, 7, 24, 42]) = 2

    • 48 = 2x24, so 2 coins are sufficient
  • C(35, [1, 3, 16, 30, 50]) = 3

    • we can make 35 from 2x16 + 1x3, so 3 coins suffice

I made the code with for loops, but how do I make it recursive?

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1
        return cdict[i]
    else:
        min = 0
        for cj in coins:
            result = C(i - cj, coins)
            if result != 0:
                if min == 0 or (result + 1) < min:
                    min = 1 + result
        cdict[i] = min
        return cdict[i]
like image 842
user1681664 Avatar asked Sep 20 '12 20:09

user1681664


People also ask

What are examples of recursive algorithm?

The classic example of recursive programming involves computing factorials. The factorial of a number is computed as that number times all of the numbers below it up to and including 1. For example, factorial(5) is the same as 5*4*3*2*1 , and factorial(3) is 3*2*1 .

What is recursive algorithm?

What Is a Recursive Algorithm? A recursive algorithm calls itself with smaller input values and returns the result for the current input by carrying out basic operations on the returned value for the smaller input.

Why recursive algorithm is used?

More generally if a problem can be solved utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases, then one can use a recursive algorithm to solve that problem.

What are the three laws of recursion algorithm?

Like the robots of Asimov, all recursive algorithms must obey three important laws: A recursive algorithm must call itself, recursively. A recursive algorithm must have a base case. A recursive algorithm must change its state and move toward the base case.


2 Answers

It's the change-making problem. Here's the standard recursive solution, V is the list of coins and C the target amount of money:

def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

And this is an optimized version, using dynamic programming:

def min_change(V, C):
    m, n = len(V)+1, C+1
    table = [[0] * n for x in xrange(m)]
    for j in xrange(1, n):
        table[0][j] = float('inf')
    for i in xrange(1, m):
        for j in xrange(1, n):
            aC = table[i][j - V[i-1]] if j - V[i-1] >= 0 else float('inf')
            table[i][j] = min(table[i-1][j], 1 + aC)
    return table[m-1][n-1]

Both implementations will always return the optimal solution, but the second one will be much faster for large inputs. Notice that the greedy algorithm suggested in other answers gives an optimal solution only for certain combinations of currency - for instance, it works for the American coins.

like image 90
Óscar López Avatar answered Sep 29 '22 18:09

Óscar López


Try using a greedy algorithm (largest coins first). Remove the coin from the list after you apply to the total and call the function again from within.

like image 43
BeReal82 Avatar answered Sep 29 '22 18:09

BeReal82