算法题：均衡分组

Question

有一个组数 ，比如 a=10, b=5, c=2, e=12,f=6, g=17,h=3,i=10。现在给这组数重新分成3组，只能按顺序分割，比如m=(a=10, b=5, c=2)。n=(e=12,f=6)。k=(g=17,h=3,i=10)。 得到m=17,n=18,k=30。依次类推有n组数，a1=b1, a2=b2, a3=b3 … an=bn。分成m组 k1=(a1=b1, a2=b2…) k2=(a100=b100, a101=b101…) … km=(an-10, an-9 … an)。 设定m的值，如何分组让k1, k2 … km 的值 最接近。

Answer 1

如果是非负数的序列，可以证明下述方法可以使其每个分组和的最大值最小。(准确说是，没有任何其他解比这个解更优，因为可能不止一个最优解)

首先，把每个值单独一个分组，即分为 n 组。然后求所有相邻分组的和，选择和最小的那两个分组合并，如果和相同的,可选任意两个，直到分为m组。

比如，第一次5+2的和最小，将其合并10,(5,2)=7,12,6,17,3,10
然后是3+10和最小,将其合并10,(5,2)=7,12,6,17,(3,10)=13
然后是10+7和最小,将其合并(10,5,2)=17,12,6,17,(3,10)=13
然后是12+6和最小,将其合并(10,5,2)=17,(12,6)=18,17,(3,10)=13
然后是17+13和最小,将其合并(10,5,2)=17,(12,6)=18,(17,3,10)=30

如果平衡性定义为，sum[a_i/s*Log(s/a_i),i](熵定义)其中a_i表示这个序列(非负序列)，s为所有数的和，可以证明，下述分组方法可以达到最优的平衡性。
定义H(x,y) = x/(x+y)*Log((x+y)/x)+y/(x+y)*Log((x+y)/y)。
首先，把每个值单独一个分组，即分为 n 组。然后分别求每个分组的和，设相邻分组的和分别为x,y，选择(x+y)/s*H(x,y)最小的那两个相邻分组合并。如果相同的,可选任意两个，直到分为m组。

Answer 2

问题规模不大的话穷举能得到最优解。n个数保持顺序分成g组，就是在n-1个空隙上插入g-1个挡板，有(n-1) choose (g-1)种方案，每种方案对应一个“平衡值”（比如方差），选出最好的一个或几个。

不需要最优解的话 @zonxin 的相邻合并法就很棒。

update

这里有一个类似问题，答案中有最优解法。