Algorithm-finding-dedicated-sum-from-the-population-of-variables

Question

I need a way of finding an exact value made of the sum of variables chosen from the population. The algorithm can find just the first solution or all. So we can have 10, 20, or 30 different numbers and we will sum some of them to get a desirable number. As an example we have a population of the below numbers: -2,-1,1,2,3,5,8,10 and we try to get 6 - this can be made of 8 and -2, 1 + 5 etc. I need at least 2 decimal places to consider as well for accuracy and ideally, the sum of variables will be exact to the asking value.

Thanks for any advice and help on this:)

I build a model Using the simplex method in Excel but I need the solution in Python.

Answer 1

This is the subset sum problem, which is an NP Complete problem.

There is a known pseudo-polynomial solution for it, if the numbers are integers. In your case, you need to consider numbers only to 2nd decimal point, so you could convert the problem into integers by multiplying by 100¹, and then run the pseudo-polynomial algorithm.

It will works quite nicely and efficiently - if the range of numbers you have is quite small (Complexity is O(n*W), where W is the sum of numbers in absolute value).

Appendix:

Pseudo polynomial time solution is Dynamic Programming adaptation of the following recursive formula:

k is the desired number
n is the total number of elements in list.

// stop clause: Found a sum
D(k, i) = true   | for all 0 <= i < n
// Stop clause: failing attempt, cannot find sum in this branch.
D(x, n) = false  | x != k
// Recursive step, either take the current element or skip it.
D(x, i) = D(x + arr[i], i+1) OR D(x, i+1)

Start from D(0,0)

If this is not the case, and the range of numbers is quite high, you might have to go with brute force solution, of checking all possible subsets. This solution is of course exponential, and processing it is in O(2^n) .

---

_{(1) Consider rounding if needed, but that's a simple preprocessing that doesn't affect the answer.}