pythonalgorithmdynamic-programmingcoin-change

Finding shortest combinations in array/sequence that equals sum


I'm totally stuck and have no idea how to go about solving this. Let's say I've an array

arr = [1, 4, 5, 10]

and a number

n = 8

I need shortest sequence from within arr which equals n. So for example following sequences within arr equals n

c1 = 5,1,1,1
c2 = 4,4
c3= 1,1,1,1,1,1,1,1

So in above case, our answer is c2 because it's shortest sequences in arr that equals sum.

I'm not sure what's the simplest way of finding a solution to above? Any ideas, or help will be really appreciated.

Thanks!

Edited:

  • Fixed the array
  • Array will possibly have postive values only.
  • I'm not sure how subset problem fixes this, probably due to my own ignorance. Does sub-set algorithm always give the shortest sequence that equals sum? For example, will subset problem identify c2 as the answer in above scenario?

Solution

  • As has been pointed before this is the minimum change coin problem, typically solved with dynamic programming. Here's a Python implementation solved in time complexity O(nC) and space complexity O(C), where n is the number of coins and C the required amount of money:

    def min_change(V, C):
        table, solution = min_change_table(V, C)
        num_coins, coins = table[-1], []
        if num_coins == float('inf'):
            return []
        while C > 0:
            coins.append(V[solution[C]])
            C -= V[solution[C]]
        return coins
    
    def min_change_table(V, C):
        m, n = C+1, len(V)
        table, solution = [0] * m, [0] * m
        for i in xrange(1, m):
            minNum, minIdx = float('inf'), -1
            for j in xrange(n):
                if V[j] <= i and 1 + table[i - V[j]] < minNum:
                    minNum = 1 + table[i - V[j]]
                    minIdx = j
            table[i] = minNum
            solution[i] = minIdx
        return (table, solution)
    

    In the above functions V is the list of possible coins and C the required amount of money. Now when you call the min_change function the output is as expected:

    min_change([1,4,5,10], 8)
    > [4, 4]