algorithm - 需要一种算法来拆分一系列数字

Question

经过几个忙碌的夜晚后，我的头不太好，但昨天需要解决这个问题，所以我问更新鲜的 SO 社区。

我有一系列数字。例如:

1, 5, 7, 13, 3, 3, 4, 1, 8, 6, 6, 6

我需要将这个系列分成三个部分，以便所有部分的数字总和尽可能接近。需要保持数字的顺序，因此第一部分必须由前 X 个数字、第二个 - 下一个 Y 数字和第三个 - 剩下的任何数字组成。

执行此操作的算法是什么？

(注意:实际问题是将不同高度的文本段落排列成三列。段落必须保持顺序(当然)，并且不能分成两半。列应尽可能等高。)

Answer 1

首先，我们需要更好地定义目标:

假设部分和是 A1,A2,A3，我们试图最小化 |A-A1|+|A-A2|+|A-A3|。 A 是平均值:A=(A1+A2+A3)/3。

因此，我们试图最小化 |A2+A3-2A1|+|A1+A3-2A2|+|A1+A2-2A3|。

让 S 表示总和(它是常数):S=A1+A2+A3，所以 A3=S-A1-A2。

我们正在尝试最小化:

|A2+S-A1-A2-2A1|+|A1+S-A1-A2-2A2|+|A1+A2-2S+2A1+2A2|=|S-3A1|+|S-3A2| +|3A1+SA2-2S|

将此函数表示为 f，我们可以做两个循环 O(n^2) 并跟踪最小值:

类似:

for (x=1; x<items; x++)
{
    A1= sum(Item[0]..Item[x-1])
    for (y=x; y<items; y++)
    {
        A2= sum(Item[x]..Item[y-1])
        calc f, if new minimum found -keep x,y
    }
}