假设我有一个包含 M 元素的数组，所有元素均为负数、正数或零。
谁能建议一种算法从数组中选择 N 元素，使得这些 N 元素的总和是可能的最小正数？
以这个数组为例:
-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200
现在我必须选择任意 5 个元素，使得它们的总和是可能的最小正数。
最佳答案
配方
对于 i = 1, ..., M:
- 让
a_i成为候选人列表中的第i个数 - 让
x_i表示第i个数字是否包含在您选择的N个数字中
然后你想解决下面的整数规划问题。
minimize: sum(a_i * x_i)
with respect to: x_i
subject to:
(1) sum(a_i * x_i) >= 0
(2) sum(x_i) = N
(3) x_i in {0, 1}
您可以将“开箱即用”的整数规划求解器应用于此问题，以找到精度可控的最优解或次优解。
资源
关于arrays - 从数组中选择其和为最小可能正数的元素组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17349268/