Choose a combination of elements from an array whose sum is the 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 for selecting N elements from an array, so 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 need to select any 5 elements so that their sum is the smallest possible positive number.

Answer 1

Structure

For i = 1, ..., M :

• Let a_i be the i th digit in your candidate list
• Let x_i denote whether the i th number is in your set of N selected 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 the integer software out-of-box solver to this problem to find the optimal solution or sub-optimal solution with controlled accuracy.

Resources

• Target programming
• Explanation of integer solver in the form of branches and borders

Answer 2

I suppose the Cadanes algorithm could do the trick, although this is for the maximum amount, but I also implemented it to find the minimum amount, although it cannot find the code right now.

Answer 3

If you want to find the best possible solution, you can just use brute force, i.e. try all possible combinations of number numbers.

Something like this very fast 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 a really fast and dirty algorithm, it can be done more elegantly. I can provide a cleaner algorithm, for example. using recursion.

It can also be optimized. For instance. You can remove similar numbers from the input list as a first step.

Answer 4

Suppose the initial array is already short-circuited, or I think it will work, even if it is not short-circuited.
N → Array Length
M → Element req.
R [] → Answer
TEMP [] → For calculations
minSum → minSum
A [] → Initial Input

All of the 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[] (ie 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); } } 

// I did it in a hurry, so maybe there will be some error.

Ideon working solution: http://ideone.com/YN8PeW

Answer 5

Here, something is not optimal in Haskell, which (as in many of my ideas) is likely to be even more optimized. This happens something like this:

• Array sorting (I have interesting results, trying both ascending and descending)
• BN = first N elements of the array
• B (i), for i> N = the best candidate; where (assuming integers), if they are less than 1, the candidates are compared by the absolute value of their sums; if they are equal to 1 or more, by their sum; and if only one candidate is greater than 0, then that candidate is selected. If the candidate’s sum is 1, return that candidate as an 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] ++ [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 sorting) or positive (in the case of descending sorting), step 3 can be performed immediately without calculation.

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 (\ab -> 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 6

Assumption: M is the source 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; } }