# Solve a linear equation with many variables using only 1 and -1

For a program I am writing, I would find it useful to find the least possible positive solution to a linear equation, using only -1 and 1 for roots.

For example...

0.25a + 0.5b + 0.75c + 1d + 2e = 0


When

a = -1, b = 1, c = 1, d = 1, e = -1


However, if we take the example

3a + 1b + 5c


It is still beneficial to know that

a = -1, b = -1, c = 1


Provides the least possible positive solution (1)

How can I algorithmically find these solutions? I would rather not use a brute force technique, my goal is to optimize the program by finding the solutions.

Forgive me for the lack of tags, I have no idea what kind of math this relates to, if any at all.

• This is something like zero-one linear programming which in general is NP-complete. – Qiaochu Yuan Dec 9 '13 at 20:43
• In particular, this is the partition problem: en.wikipedia.org/wiki/Partition_problem – Yoav Kallus Dec 9 '13 at 21:22
• You probably want to read the answers to this closely related question: mathoverflow.net/questions/123670/… – Yoav Kallus Dec 9 '13 at 21:33
• What do you mean by "positive" solution, when you allow the variables to take on the value $-1$? – Gerry Myerson Dec 9 '13 at 23:01
• @GerryMyerson: judging by OP's example, they mean the least positive value that the left-hand side can take. – Yoav Kallus Dec 10 '13 at 0:00