Select combination of elements from array whose sum is smallest possible positive number

Question

Suppose I have an array of M elements, all numbers, negative or positive or zero.

Can anyone suggest an algorithm to select N elements from the array, such that the sum of these N elements is the smallest possible positive number?

Take this array for example:

-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200

Now I have to select any 5 elements such that their sum is the smallest possible positive number.

Answer 1

Formulation

For i = 1, ..., M:

• Let a_i be the ith number in your list of candidates
• Let x_i denote whether the ith number is included in your set of N chosen numbers

Then you want to solve the following integer programming problem.

minimize: sum(a_i * x_i)
with respect to: x_i
subject to:
    (1) sum(a_i * x_i) >= 0
    (2) sum(x_i) = N
    (3) x_i in {0, 1}

You can apply an integer program solver "out of the box" to this problem to find the optimal solution or a suboptimal solution with controllable precision.

Resources

• Integer programming
• Explanation of branch-and-bound integer program solver