从数组中选择元素的组合,其总和是最小可能的正数

Question

假设我有一个M元素数组,所有数字,负数或正数或零.

任何人都可以建议一种算法N从数组中选择元素,这样这些N元素的总和是最小的正数吗？

以此数组为例:

-1000,-700,-400,-200,-100,-50,10,100,300,600,800,1200

现在我必须选择任何5个元素,使得它们的总和是可能的最小正数.

Answer 1

公式

用于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}

您可以将"开箱即用"的整数程序求解器应用于此问题,以找到最佳解决方案或具有可控精度的次优解决方案.

资源

• 整数编程
• 分支定界整数程序求解器的解释

Answer 2

我想Kadane\xe2\x80\x99s 算法可以解决这个问题，虽然它是为了最大和，但我也实现了它来找到最小和，尽管现在找不到代码。

\n