Search for shortest combinations in an array / sequence that equals the sum

Question

I am completely stuck and have no idea how to solve this. Say I have an array

arr = [1, 4, 5, 10] 

and number

 n = 8 

I need the shortest sequence from inside arr equal to n. So, for example, the following sequences within arr are n

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

So, in the above case, our answer is c2, because these are the shortest sequences in arr equal to the sum.

I'm not sure the easiest way to find the solution above? Any ideas or help would be really appreciated.

Thanks!

Edited by:

• Array fixed
• An array may only have post values.
• I'm not sure how a problem with a subset corrects this, perhaps due to my own ignorance. Does the subset algorithm always give the shortest sequence equal to the sum? For example, would a subset problem identify c2 as an answer in the above scenario?

Answer 1

As already mentioned, this is a problem with a minimal change in the coin , usually solved by dynamic programming. Here, the Python implementation is solved in time complexity O (nC) and spatial complexity O (C), where n is the number of coins and C 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 has a list of possible coins and C required amount of money. Now, when you call the min_change function, the output looks as expected:

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

Answer 2

In the interest of people who find this question in the future -

As Oscar Lopez and Priyank Bhatnagar note, this is a problem of changing coins (change, change).

In general, the dynamic programming that he offers is an optimal solution - both in terms of (provable!), Always creating the required amount using the smallest elements, and in terms of speed of execution. If your base numbers are arbitrary, then use a dynamic programming solution.

If your base numbers are “nice,” however, a simpler greedy algorithm will be used.

For example, the Australian currency system uses the denominations of $100, $50, $20, $10, $5, $2, $1, $0.50, $0.20, $0.10, $0.05 . The optimal change can be set for any amount by repeatedly providing the largest unit of change until the remaining amount is zero (or less than five cents).

Here is an instructive implementation of a greedy algorithm illustrating the concept.

 def greedy_give_change (denominations, amount): # Sort from largest to smallest denominations = sorted(denominations, reverse=True) # number of each note/coin given change_given = list() for d in denominations: while amount > d: change_given.append(d) amount -= d return change_given australian_coins = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05] change = greedy_give_change(australian_coins, 313.37) print (change) # [100, 100, 100, 10, 2, 1, 0.2, 0.1, 0.05] print (sum(change)) # 313.35 

For a specific example, in the original message ( denominations = [1, 4, 5, 10] and amount = 8 ), the greedy solution is not optimal - it will give [5, 1, 1, 1] . But the greedy solution is much faster and simpler than the dynamic programming solution, so if you can use it, you should!

Answer 3

This problem is known as a problem with minimal coin change.

You can solve this problem with dynamic programming. Here is the pseudo code:

 Set MinCoin[i] equal to Infinity for all of i MinCoin[0] = 0 For i = 1 to N // The number N For j = 0 to M - 1 // M denominations given // Number i is broken into i-Value[j] for which we already know the answer // And we update if it gives us lesser value than previous known. If (Value[j] <= i and MinCoin[i-Value[j]]+1 < MinCoin[i]) MinCoin[i] = MinCoin[i-Value[j]]+1 Output MinCoin[N] 

Answer 4

This is a variant of the problem of a subset of sums. In your problem, you can select an item multiple times. You can still use a similar idea to solve this problem using the prorgamming dynamic technique. The main idea is to design a function F (k, j) such that F (k, j) = 1 means that there exists a sequence of arr whose sum is j and length k.

Formally, the basic case is that F (k, 1) = 1 if there exists i such that arr [i] = k. For the inductive case, F (k, j) = 1 if there exists i such that arr [i] = m and F (k-1, jm) = 1.

The smallest k with F (k, n) = 1 is the length of the shortest sequence you want.

Using the dynamic programming method, you can calculate the function F without using recursion. By tracking additional information for each F (k, j), you can also restore the shortest sequence.

Answer 5

What you are trying to solve is a variant of the coin change problem. Here you are looking for the smallest number of changes or the minimum number of coins summed up to a given amount.

Consider the simple case when your array

 c = [1, 2, 3] 

you write 5 as a combination of elements from C and want to know what is the shortest such combination. Here C is a set of coin values, and 5 is the amount for which you want to receive changes.

Record all possible combinations:

 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 2 + 2 1 + 1 + 3 2 + 3 

Please note that the two combinations coincide before reordering, therefore, for example, 2 + 3 = 3 + 2.

There is an amazing result here that is not obvious at first glance, but it is very easy to prove. If you have any sequence of coins / values, which is a sequence of minimum length that sums up to a given value, regardless of how you divide this sequence, the two parts will also be sequences of minimum length for the corresponding amounts.

For example, if c[3] + c[1] + c[2] + c[7] + c[2] + c[3] add to S , and we know that 6 is a sequence of the minimum length of elements from c which adds up to S , then if you split

  | S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3] | 

you have that 4 is the minimum length for sequences that add up to c[3] + c[1] + c[2] + c[7] and 2 is the minimum length for sequences that add up to c[2] + c[3] .

  | S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3] | = S_left + S_right 

How to prove it? Contradiction, suppose that the length of S_left not optimal, that is, a shorter sequence that is added before S_left . But then we could write S as the sum of this shorter sequence and S_right , which contradicts the fact that the length of S minimal. □

Since this is true no matter how you split the sequence, you can use this result to create a recursive algorithm that follows the principles of the dynamic programming paradigm (solving smaller problems, possibly skipping calculations that won't be used, memoization or tracking the calculated values ​​and finally, combining the results).

OK, therefore, in the small example above, we will consider how we will solve the problem using the dynamic programming approach: suppose we want to find the shortest sequence of elements from c = [1, 2, 3] to write the sum 5 . We solve the subtasks obtained by subtracting one coin: 5 - 1 , 5 - 2 and 5 - 3 , we take the smallest solution to these subtasks and add 1 (the missing coin).

So we can write something like

 shortest_seq_length([1, 2, 3], 5) = min( shortest_seq_length([1, 2, 3], 5-1), shortest_seq_length([1, 2, 3], 5-2), shortest_seq_length([1, 2, 3], 5-3) ) + 1 

It is convenient to write the algorithm from the bottom up, starting with lower values ​​of the sums that can be saved and used to generate large sums. We simply solve the problem for all possible values, starting from 1 and rising to the desired amount.

Here's the code in Python:

 def shortest_seq_length(c, S): res = {0: 0} # res contains computed results res[i] = shortest_seq_length(c, i) for i in range(1, S+1): res[i] = min([res[ix] for x in c if x<=i]) + 1 return res[S] 

Now this works, except when we cannot fill the memoization structure for all i values. This is the case when we do not have a value of 1 in c , therefore, for example, we cannot form the sum 1 if c = [2, 5] and with the above function we get

 shortest_seq_length([2, 3], 5) # ValueError: min() arg is an empty sequence 

So, to take care of this problem, one could, for example, use try / catch:

 def shortest_seq_length(c, S): res = {0: 0} # res is the dictionary containing results for each sum res[i] = shortest_seq_length(c, i) for i in range(1, S+1): try: res[i] = min([res[ix] for x in c if x<=i and res[ix] is not None]) +1 except: res[i] = None # takes care of error when [res[ix] for x in c if x<=i] is empty return res[S] 

Try:

 print(shortest_seq_length([2, 3], 5)) # 2 print(shortest_seq_length([1, 5, 10, 25], 37)) # 4 print(shortest_seq_length([1, 5, 10], 30)) # 3 print(shortest_seq_length([1, 5, 10], 25)) # 3 print(shortest_seq_length([1, 5, 10], 29)) # 7 print(shortest_seq_length([5, 10], 9)) # None 

One of the small improvements of the algorithm is to skip the step of calculating the minimum when the sum is equal to one of the values ​​/ coins, but this can be done better if we write a cycle to calculate the minimum. However, the implementation of Thsi does not improve the overall complexity of O(mS) , where m = len(c) .