I have a set $X = \{x_1, x_2, \dots x_N\} \in [0;1]^N$ containing $N$ elements, initially all positive. My goal is to find a vector of signs $S = \{s_1, s_2, \dots s_N\} \in \{-1; 1\}^N$ such that:
$$\sum\limits_{i = 1}^{N} x_i s_i = 0$$
In other words, I want to be able to find the signs to associate to the various $x_i$ such that their sum is null. Do you know if there is a standard way to do that? Or to obtain the closest sum to $0$?
Thanks in advance!
Bastien
Precisions
I know for sure that the solution exists, or is very close to $0$ (in case of precision loss in previous computations).
I have already investigated the following ideas:
- Exhaustive search guided by a heuristic function (works up to $|X| \approx 30$).
- Simple genetic algorithm (works up to $|X| \approx 40$).
- Suggestion by Math1000: dynamic programming (I don't think it will work due to the exponential number of sums, but I may be wrong).