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

Question

<分区>

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

如果它实际上是子集，那么，如前所述，它似乎是the Partition problem 的优化版本。 , 这要困难得多。