Coin change with limited coins complexity

Question

If there is an unlimited number of every coin then the complexity is O(n*m) where is n is the total change and m is the number of coin types. Now when the coins for every type are limited then we have to take into account the remaining coins. I managed to make it work with a complexity of O(n*m2) using another for of size n so I can track the remaining coins for each type. Is there a way-trick to make the complexity better? EDIT : The problem is to compute the least ammount of coins required to make the exact given change and the number of times that we used each coin type

Answer 1

There is no need for an extra loop. You need to:

• recurse with a depth of at most m (number of coins) levels, dealing with one specific coin per recursion level.
• Loop at most n times at each recursion level in order to decide how many you will take of a given coin.

Here is how the code would look in Python 3:

def getChange(coins, amount, coinIndex = 0):
    if amount == 0:
        return [] # success
    if coinIndex >= len(coins):
        return None # failure
    coin = coins[coinIndex]
    coinIndex += 1
    # Start by taking as many as possible from this coin
    canTake = min(amount // coin["value"], coin["count"])
    # Reduce the number taken from this coin until success
    for count in range(canTake, -1, -1): # count will go down to zero
        # Recurse to decide how many to take from the next coins
        change = getChange(coins, amount - coin["value"] * count, coinIndex)
        if change != None: # We had success
            if count: # Register this number for this coin:
                return change + [{ "value": coin["value"], "count": count }]
            return change


# Example data and call:
coins = [
    { "value": 20, "count":  2 },   
    { "value": 10, "count":  2 },
    { "value":  5, "count":  3 },
    { "value":  2, "count":  2 },
    { "value":  1, "count": 10 }
]

result = getChange(coins, 84)
print(result)

Output for the given example:

[
    {'value': 1, 'count': 5},
    {'value': 2, 'count': 2},
    {'value': 5, 'count': 3},
    {'value': 10, 'count': 2},
    {'value': 20, 'count': 2}
]

Minimising the number of coins used

As stated in comments, the above algorithm returns the first solution it finds. If there is a requirement that the number of individual coins must be minimised when there are multiple solutions, then you cannot return halfway a loop, but must retain the "best" solution found so far.

Here is the modified code to achieve that:

def getchange(coins, amount):
    minCount = None

    def recurse(amount, coinIndex, coinCount):
        nonlocal minCount
        if amount == 0:
            if minCount == None or coinCount < minCount:
                minCount = coinCount
                return [] # success
            return None # not optimal
        if coinIndex >= len(coins):
            return None # failure
        bestChange = None
        coin = coins[coinIndex]
        # Start by taking as many as possible from this coin
        cantake = min(amount // coin["value"], coin["count"])
        # Reduce the number taken from this coin until 0
        for count in range(cantake, -1, -1):
            # Recurse, taking out this coin as a possible choice
            change = recurse(amount - coin["value"] * count, coinIndex + 1, 
                                                             coinCount + count)
            # Do we have a solution that is better than the best so far?
            if change != None: 
                if count: # Does it involve this coin?
                    change.append({ "value": coin["value"], "count": count })
                bestChange = change # register this as the best so far
        return bestChange

    return recurse(amount, 0, 0)

coins = [{ "value": 10, "count":  2 },
         { "value":  8, "count":  2 },
         { "value":  3, "count": 10 }]

result = getchange(coins, 26)
print(result)

Output:

[
    {'value': 8, 'count': 2},
    {'value': 10, 'count': 1}
]

Answer 2

Here's an implementation of an O(nm) solution in Python.

If one defines C(c, k) = 1 + x^c + x^(2c) + ... + x^(kc), then the program calculates the first n+1 coefficients of the polynomial product(C(c[i], k[i]), i = 1...ncoins). The j'th coefficient of this polynomial is the number of ways of making change for j.

When all the ks are unlimited, this polynomial product is easy to calculate (see, for example: https://stackoverflow.com/a/20743780/1400793). When limited, one needs to be able to calculate running sums of k terms efficiently, which is done in the program using the rs array.

# cs is a list of pairs (c, k) where there's k
# coins of value c.
def limited_coins(cs, n):
    r = [1] + [0] * n
    for c, k in cs:
        # rs[i] will contain the sum r[i] + r[i-c] + r[i-2c] + ...
        rs = r[:]
        for i in xrange(c, n+1):
            rs[i] += rs[i-c]
            # This line effectively performs:
            # r'[i] = sum(r[i-j*c] for j=0...k)
            # but using rs[] so that the computation is O(1)
            # and in place.
            r[i] += rs[i-c] - (0 if i<c*(k+1) else rs[i-c*(k+1)])
    return r[n]

for n in xrange(50):
    print n, limited_coins([(1, 3), (2, 2), (5, 3), (10, 2)], n)