method for finding balanced sums?

All;

Say I have a list of positive integers, and I sum them up.
Is there a method for assigning signs to them so their sum
is as close to zero (either positive or negative) as possible?

-Carl

Carl wrote:
>Say I have a list of positive integers, and I sum them up.
>Is there a method for assigning signs to them so their sum
>is as close to zero (either positive or negative) as possible?

This is a kind of knapsack problem, which I think is NP-complete.
Do you have so many that brute force takes too long a time?
With the mail delays, perhaps an answer from Gene is already
coming.

Manuel

--- In tuning-math@y..., manuel.op.de.coul@e... wrote:
> Carl wrote:

> >Say I have a list of positive integers, and I sum them up.
> >Is there a method for assigning signs to them so their sum
> >is as close to zero (either positive or negative) as possible?
>
> This is a kind of knapsack problem, which I think is NP-complete.
> Do you have so many that brute force takes too long a time?
> With the mail delays, perhaps an answer from Gene is already
> coming.

I didn't have anything to say beyond that it looked like a -1/1 knapsack, and so should be NP hard in general. I'd just brute force it.

>>>Say I have a list of positive integers, and I sum them up.
>>>Is there a method for assigning signs to them so their sum
>>>is as close to zero (either positive or negative) as possible?
>>
>>This is a kind of knapsack problem, which I think is NP-complete.
>>Do you have so many that brute force takes too long a time?
>>With the mail delays, perhaps an answer from Gene is already
>>coming.
>
>I didn't have anything to say beyond that it looked like a -1/1
>knapsack, and so should be NP hard in general. I'd just brute force
>it.

I saw knapsack on mathworld last night, but didn't think it
applied because of the business about weights.

What if I order the elements from largest to smallest and then
recursively subtract them in pairs, applying absolute value at
the end of each round. So like

(define kpsk
(lambda (ls)
(if (null? (cdr ls))
(car ls)
(kpsk (cons (abs (- (cadr ls) (car ls))) (cddr ls))))))

Tests:
(5 4 3 2 1) => 1
(10 8 6 4 2) => 2
(16 8 4 2) => 2
(92 91 90 1) => 88
(11 7 5 3 2) => 0
(25 16 9 4 1) => 3

Now, I don't know how hard sorting is. I've got a version of
mergesort here that is nlog(n), and IIRC quicksort is often,
but not always, better.

This doesn't tell you the signs. An extra test at each round
might be able to write those out, but all I want is the total,
so...

This measure doesn't seem to do what I want (see #4 at
lumma.org/gd3.txt), since cases like (3 3) will be low
(as they should) while (3 3 3) will be high. Back to the
drawing board.

-Carl