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