From: rusin@math.niu.edu (Dave Rusin)
Subject: Re: question on minimizing the sum of reals
Date: 30 Dec 1999 17:01:23 GMT
Newsgroups: sci.math.research
Keywords: subset-sum problem

In article <386A7A80.39187B69@altavista.net>,
Eric Anderholm  <eja@altavista.net> wrote:
>If you are given  "n" real positive numbers, each unique,  what is the
>minimum sum possible, greater than zero found by addition and/or
>subtraction.
>
>Example if given n=3 and {3.5,2.0,1.0}  the answer is 3.5-2.0-1.0=.5;
>any other combination of +/- gives you a greater sum....or a negative
>result which is not allowed (such as -3.5+2.0+1.0=-.5).

It's not clear to me whether you intended all  n  of the numbers to be
used in the sum, but certainly you would need to consider the possibility
that all  n  of them are used if it is critical that the absolutely
minimal sum is found. In that case, you are looking for a collection
of the  x_i  whose sum is as close as possible to (1/2)*Sum(x_i, i=1 to n).
(Add these  x_i  and subtract the others to get the signed sum closest
to zero. Swap signs if necessary.)

But now what I've described is the Subset Sum problem, which I thought
was NP-complete -- no algorithm is presumed to exist which will always find
the answer rapidly. On the other hand, there are methods of getting
_pretty good_ answers quickly. See e.g. 97/knapsack

dave