z**********g
发帖数: 209 | 1 You're given N signed integers a[1..N].
You need to find N correct signs s[1..N] (that is, numbers s[i] = +/-1),
such that
a[1]*s[1] + a[2]*s[2] + .. + a[N]*s[N] = 0.
Assume that the solution always exists.
Example: a = {5, 7, 3, -8, 1};
then the signs are: s = {1, 1, -1, 1, -1}
because: 5 + 7 - 3 - 8 - 1 = 0
(or symmetric solution: s = {-1, -1, 1, -1, 1})
brute force 2^n. | a***9
发帖数: 364 | 2 这个是NP hard吧，reduce subset sum to this one
【在 z**********g 的大作中提到】
: You're given N signed integers a[1..N].
: You need to find N correct signs s[1..N] (that is, numbers s[i] = +/-1),
: such that
: a[1]*s[1] + a[2]*s[2] + .. + a[N]*s[N] = 0.
: Assume that the solution always exists.
: Example: a = {5, 7, 3, -8, 1};
: then the signs are: s = {1, 1, -1, 1, -1}
: because: 5 + 7 - 3 - 8 - 1 = 0
: (or symmetric solution: s = {-1, -1, 1, -1, 1})
: brute force 2^n.
| m*****g
发帖数: 226 | |
|
