algorithm - 找到将序列拆分为 2 以最小化总和差异的算法

Question

问题来了：给定一个数字序列，将这些数字分成 2 个序列，使两个序列之间的差异最小。例如，给定序列： [5, 4, 3, 3, 3] 解为：
[5, 4] -> sum is 9
[3, 3, 3] -> sum is 9
差为 0

换句话说，你能找到一种算法（首选 C 语言），给定一个整数的输入向量（可变大小），可以输出两个向量，其中两个和之间的差异最小吗？
应避免使用暴力算法。

为确保获得正确的解决方案，最好在基准测试中比较您的算法和粗暴算法之间的结果。

Answer 1

这听起来像是一个子数组问题（这是我对“序列”的解释）。

这意味着唯一的可能性5, 4, 3, 3, 3是：

| 5, 4, 3, 3, 3  =>  0 - 18 => 18
 5 | 4, 3, 3, 3  =>  5 - 13 => 8
 5, 4 | 3, 3, 3  =>  9 -  9 => 0
 5, 4, 3 | 3, 3  => 12 -  6 => 6
 5, 4, 3, 3 | 3  => 15 -  3 => 12
 5, 4, 3, 3, 3 | => 18 -  0 => 18 (same as first)

它就像比较每个索引两侧的总和一样简单。

代码：（未经测试）

int total = 0;
for (int i = 0; i < n; i++)
  total += arr[i];
int best = INT_MAX, bestPos = -1, current = 0;
for (int i = 0; i < n; i++)
{
  current += arr[i];
  int diff = abs(current - total);
  if (diff < best)
  {
    best = diff;
    bestPos = i;
  }
  // else break; - optimisation, may not work
}

printf("The best position is at %d\n", bestPos);

以上是O(n)，从逻辑上讲，你不能做得比这更好。

您可以通过对序列执行类似二进制搜索的过程来稍微优化上述内容，以降低到n + log n而不是2n，但两者都是O(n). 基本伪代码：

sum[0] = arr[0]
// sum[i] represents sum from indices 0 to i
for (i = 1:n)
  sum[i] = sum[i-1] + arr[i]
total = sum[n]
start = 0
end = n
best = MAX
repeat:
  if (start == end) stop
  mid = (start + end) / 2
  sumFromMidToN = sum[n] - sum[mid]
  best = max(best, abs(sumFromMidToN - sum[mid]))
  if (sum[mid] > sumFromMidToN)
    end = mid
  else if (sum[mid] < sumFromMidToN)
    start = mid
  else
    stop

如果它实际上是子集，那么，如前所述，它似乎是分区问题的优化版本，这要困难得多。