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

Answer 2

Here's something sub optimal in Haskell, which (as with many of my ideas) could probably be further and better optimized. It goes something like this:

1. Sort the array (I got interesting results by trying both ascending and descending)
2. B N = first N elements of the array
3. B (i), for i > N = best candidate; where (assuming integers) if they are both less than 1, the candidates are compared by the absolute value of their sums; if they are both 1 or greater, by their sums; and if only one candidate is greater than 0 then that candidate is chosen. If a candidate's sum is 1, return that candidate as the answer. The candidates are:
     B (i-1), B (i-1)[2,3,4..N] ++ array [i], B (i-1)[1,3,4..N] ++ array [i]...B (i-1)[1,2..N-1] ++ array [i]
     B (i-2)[2,3,4..N] ++ array [i], B (i-2)[1,3,4..N] ++ array [i]...B (i-2)[1,2..N-1] ++ array [i]
     ...
     B (N)[2,3,4..N] ++ array [i], B (N)[1,3,4..N] ++ array [i]...B (N)[1,2..N-1] ++ array [i]

Note that for the part of the array where the numbers are negative (in the case of ascending sort) or positive (in the case of descending sort), step 3 can be done immediately without calculations.

Output:

*Main> least 5 "desc" [-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200]
(10,[-1000,600,300,100,10])
(0.02 secs, 1106836 bytes)

*Main> least 5 "asc" [-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200]
(50,[300,100,-200,-100,-50])
(0.02 secs, 1097492 bytes)

*Main> main -- 10000 random numbers ranging from -100000 to 100000
(1,[-106,4,-40,74,69])
(1.77 secs, 108964888 bytes)

Code:

import Data.Map (fromList, insert, (!))
import Data.List (minimumBy,tails,sort)
import Control.Monad.Random hiding (fromList)

array = [-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200]

least n rev arr = comb (fromList listStart) [fst (last listStart) + 1..m]
 where
  m = length arr
  r = if rev == "asc" then False else True
  sorted = (if r then reverse else id) (sort arr)
  listStart = if null lStart 
                 then [(n,(sum $ take n sorted,take n sorted))] 
                 else lStart
  lStart = zip [n..] 
         . takeWhile (all (if r then (>0) else (<0)) . snd) 
         . foldr (\a b -> let c = take n (drop a sorted) in (sum c,c) : b) [] 
         $ [0..]
  s = fromList (zip [1..] sorted)
  comb list [] = list ! m
  comb list (i:is)
    | fst (list ! (i-1)) == 1 = list ! (i-1)
    | otherwise              = comb updatedMap is 
   where updatedMap = insert i bestCandidate list 
         bestCandidate = comb' (list!(i - 1)) [i - 1,i - 2..n] where
           comb' best []     = best
           comb' best (j:js)
             | fst best == 1 = best
             | otherwise     =    
                 let s' = map (\x -> (sum x,x))
                        . (take n . map (take (n - 1)) . tails . cycle) 
                        $ snd (list!j)
                     t = s!i
                     candidate = minimumBy compare' (map (add t) s')
                 in comb' (minimumBy compare' [candidate,best]) js
  add x y@(a,b) = (x + a,x:b)
  compare' a@(a',_) b@(b',_) 
    | a' < 1    = if b' < 1 then compare (abs a') (abs b') else GT
    | otherwise = if b' < 1 then LT else compare a' b'

rnd :: (RandomGen g) => Rand g Int
rnd = getRandomR (-100000,100000)

main = do
  values <- evalRandIO (sequence (replicate (10000) rnd))
  putStrLn (show $ least 5 "desc" values)

Answer 3

I suppose Kadane’s Algorithm would do the trick, although it is for the maximum sum but I have also implemented it to find the minimum sum, though can't find the code right now.

Answer 4

Let initial array be shorted already, or i guess this will work even when it isnt shorted..
N -> Length of array
M -> Element req.
R[] -> Answer
TEMP[] -> For calculations
minSum -> minSum
A[] -> Initial input

All above variables are globally defined

int find(int A[],int start,int left)
{
    if(left=0)
    {
        //sum elements in TEMP[] and save it as curSum
        if(curSum<minSum)
        {
        minSum=curSum;
        //assign elements from TEMP[] to R[] (i.e. our answer)      
        }
    }

    for(i=start;i<=(N-left);i++)
    {
        if(left==M)
            curSum=0;
        TEMP[left-1]=A[i];
        find(A[],i+1,left-1);
    }
}

// Made it in hurry so maybe some error would be existing..

Working solution on ideone : http://ideone.com/YN8PeW

Answer 5

If you want to find the best possible solution, you can simply use brute force ie. try all posible combinations of fiwe numbers.

Something like this very quick and dirty algorithm:

public List<Integer> findLeastPositivSum(List<Integer> numbers) {
    List<Integer> result;
    Integer resultSum;
    List<Integer> subresult, subresult2, subresult3, subresult4, subresult5;
    for (int i = 0; i < numbers.size() - 4; i++) {
        subresult = new ArrayList<Integer>();
        subresult.add(numbers.get(i));
        for (int j = i + 1; j < numbers.size() - 3; j++) {
            subresult2 = new ArrayList<Integer>(subresult);
            subresult2.add(j);
            for (int k = j + 1; k < numbers.size() - 2; k++) {
                subresult3 = new ArrayList<Integer>(subresult2);
                subresult3.add(k);
                for (int l = k + 1; l < numbers.size() - 1; l++) {
                    subresult4 = new ArrayList<Integer>(subresult3);
                    subresult4.add(k);
                    for (int m = l + 1; m < numbers.size(); m++) {
                        subresult5 = new ArrayList<Integer>(subresult4);
                        subresult5.add(k);
                        Integer subresultSum = sum(subresult5);
                        if (subresultSum > 0) {
                            if (result == null || resultSum > subresultSum) {
                                result = subresult;
                            }
                        }
                    }
                }
            }
        }
    }
    return result;
}

public Integer sum(List<Integer> list) {
    Integer result = 0;
    for (Integer integer : list) {
        result += integer;
    }
    return result;
}

This is really quick and dirty algorithm, it can be done more elegantly. I can provide cleaner algorithm e.g. using recursion.

It can be also further optimized. E.g. you can remove similar numbers from input list as first step.

Answer 6

Assumption: M is the original array

Pesudocode

 S = sort(M);
 R = [];
 sum = 0;
 for(i=0, i < length(S); i++){
   sum = sum + S[i];
   if(sum < 1){
     R.push(S[i]);
   }else{
     return R;
   }
 }