For n integers, we find m whose absolute value is minimal

Question

I have n integers; both positive and negative values. What is a good algorithm for finding m integers from this list, so that the absolute value of the sum of these m integers is the smallest possible?

Answer 1

The problem is NP-hard, since its effective solution effectively solves the problem of solving the problem of a subset of sums .

Given that you will not find an effective algorithm to solve it, if you do not think that P = NP.

You can always come up with some heuristics to direct your search, but in the worst case, you will need to check every subset of m integers.

Answer 2

If “good” means “right,” just try every opportunity. This will lead you to n choose m time. Very slow. Unfortunately, this is the best thing you can do as a whole, because for any set of integers you can always add another one that is negative from the sum of m-1 others - and everyone else can have the same sign, therefore You do not have the ability to search.

If “good” means “fast and usually works fine,” then there are various ways to continue. For instance:.

Suppose you can solve the problem for m=2 , and suppose that later you can solve it for both positive and negative answers (and then take the smaller of the two). Now suppose you want to solve m=4 . Decide for m=2 , then discard these two numbers and decide again ... it should be obvious what to do next! Now, what about m=6 ?

Now suppose you can solve the problem for m=3 and m=2 . Think you can get a decent answer for m=5 ?

Finally, note that if you sort numbers, you can solve for m=2 in one pass, and for m=3 you have an annoying quadratic search, but at least you can do it in just a quarter of the list twice (small halves of positive and negative numbers) and look for several opposite signs to cancel.