给定一组 A
包含 N
正整数,我怎么能找到在最小整数> = 0 的,可以使用可获得的集合中的所有的元素。每个元素可以是可以是的加或减以总。
几个例子来说明这一点。
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]
结果= 0
(2 + 1 - 3)
Result = 0
(2 + 1 - 3)
A = [1,2,0]
结果= 1
(1 + 2 + 0)
Result = 1
(-1 + 2 + 0)
A = [1,2,1,7,6]
结果= 1
(1 + 2 - 1 - 7 + 6)
Result = 1
(1 + 2 - 1 - 7 + 6)
您可以通过使用布尔整数规划解决这个问题。有几种算法(如戈莫里或分支定界)和自由库(例如LP-解决)可用。
You can solve it by using Boolean Integer Programming. There are several algorithms (e.g. Gomory or branch and bound) and free libraries (e.g. LP-Solve) available.
计算列表的总和,并调用它第双冠王列表中的号码。再说了一倍数字是A,B,C。然后你有以下方程组:
Calculate the sum of the list and call it s. Double the numbers in the list. Say the doubled numbers are a,b,c. Then you have the following equation system:
Boolean x,y,z
a*x+b*y+c*z >= s
Minimize ax+by+cz!
布尔变量指示相应数量应该增加(如果真)或相减(当假的)。
The boolean variables indicate if the corresponding number should be added (when true) or subtracted (when false).
我要指出的转化问题,可以被看作是背包问题还有:
I should mention that the transformed problem can be seen as "knapsack problem" as well:
Boolean x,y,z
-a*x-b*y-c*z <= -s
Maximize ax+by+cz!