algorithm - Subset sum problem where each number can be added or subtracted

Question

Given a set A containing n positive integers, how can I find the smallest integer >= 0 that can be obtained using all the elements in the set. Each element can be can be either added or subtracted to the total. Few examples to make this clear.

A = [ 2, 1, 3]

Result = 0 (2 + 1 - 3)

A = [1, 2, 0]

Result = 1 (-1 + 2 + 0)

A = [1, 2, 1, 7, 6]

Result = 1 (1 + 2 - 1 - 7 + 6)

Answer 1

您可以使用布尔整数编程来解决它。有几种算法（例如 Gomory 或分支定界）和免费库（例如 LP-Solve）可用。

计算列表的总和并将其称为 s。将列表中的数字加倍。假设加倍的数字是a，b，c。然后你有以下方程组：

Boolean x,y,z 

a*x+b*y+c*z >= s

Minimize ax+by+cz!

布尔变量指示是否应该添加相应的数字（如果为真）或减去（如果为假）。

[编辑]

我应该提一下，转换后的问题也可以看作是“背包问题”：

Boolean x,y,z 

-a*x-b*y-c*z <= -s

Maximize ax+by+cz!