如何将m个数尽量平均分成n组

1 背景

在具体的项目中，经常会碰到稍微复杂一点的算法，很多问题都涉及到资源分配，如何将m个自然数尽可能平均分成n组便是其中一个经常会碰到的问题，很多游戏项目中作资源分配时都可能碰到这样的问题。

2 解决方案

针对这个问题，有两种典型的方法，如下分别进行介绍

2.1 暴力法

最简单直接的方法是暴力法，将m个数分成n组，就是对m进行n划分，找出所有的划分，看哪一种最平均。

显然，这是一种最笨的方法，随着m的增长，这些组合的数量会变得极为庞大，如m=10000， n=100时，光把这些组合计算出来都是一件极其费力的事。这种方法显然行不通。

2.2 动态规划算法

为描述方便，以一个具体例子进行分析，假设m个数为：28, 25, 19, 18, 10, 9, 6, 4, 3, 1，如果分成3组，该如何分？分成4组呢？分成5组呢？

在继续分之前，需要明确什么是“尽可能平均”，假设上例中分成三组数据，每组数据之和为sum1, sum2, sum3，m个数的平均值为：mean，则length = [(sum1-mean)² + (sum2-mean)² + (sum3-mean)²]^1/2，length值最小的分组，分组最平均。

另外一个问题是：是否能找到最优解或者次有解？这个问题有点棘手，但是如果降低要求，能否找到一个并不离奇的解，则很简单。下面介绍一个能找到次优解的方法，在本文中未证明是否是最优解。

• 首先计算m个数的n平均值，如上例中所有数的和为123，分成3组的平均值mean为41；

• 将这m个数按从大到小的顺序进行排序，得到（28, 25, 19, 18, 10, 9, 6, 4, 3, 1）；

• 从最大的数max开始选择，如果max >= mean，则直接将max单独分成一组；否则，将max纳入一组g，并为g继续选择是否有新的数可以加入，这是这一算法中最关键的部分：

  (1). 首先计算假设不再有新的数纳入g，则计算delta₀ = mean - max和sqrt₀ = (mean - max)²；
  (2). 然后从剩下的数中寻找最接近delta₀的数，此时，按照(1)继续计算delta₁和sqrt₁，再按照（2）继续，直至不能继续；
  (3). 比较上述过程中可能组合最终的sqrt_i，选择一个最小的，其核心问题是是否加入一个数到当前组以及加入哪一个数。（这一部分可能描述有些不清楚，请看后面的描述，并在后面的图上动手分组理解）

这个问题说起来有些绕，下面以上面具体的例子进行描述：

1 由计算得10个数的总和为123，分成3组的平均值为41；
2 从大到小开始进行分组，首先将28纳入一个组g，因为28 < 41，所以在剩余的数中继续寻找与delta₀ =（41 - 28）=13最接近的数；从大到小遍历的过程中，寻找离13最近的数，得到18和10，显然(18-13)² > (13-10)²，因此将10纳入g；接着，继续再剩余的数中寻找与(13 - 10)等于3最接近的数，最后得到一个分组(28, 10, 3)
同理，按照此方法，可以得到另外的几个组（25，9，6，1），（19，18，4）

在描述例子的过程当中，最核心的问题是寻找与delta_i最接近的数时，到底是加入比delta_i大的最近的数p还是加入比delta_i小的最近的数q？

• 如果(delta_i - p)² > (delta_i - q)²，则将q加入分组，继续探索delta_i+1 = delta_i - q；
• 如果(delta_i - p)² <= (delta_i - q)²，（此时还不能确定到底是加入p还是加入q），则将(delta_i - p)²保存，并且继续探索delta_i - q；递归地执行上述过程，选择差平方最小的数据加入分组。

显然，上述过程是一个动态规划算法，每个过程都能继续划分为更小的子过程。

在算法执行的过程中，需要频繁地寻找与delta_i最接近的数，当采用数组时，其时间复杂度为O(m)，当m较小时，还可以接受，当m变大后，则资源浪费严重；如果将原始数据以平衡二叉树的形式存储，其时间复杂度变为O(logm)，即使数据规模变大，依然可以接受。

在具体的实现时，在寻找与delta_i最接近的数时，如果记住上一时刻的q位置，则不必从头开始遍历二叉树，只需要q的前驱（中序遍历），而非整颗树，因此，划出一个分组，其时间复杂度为O(m*logm)，n个分组的时间复杂度为O(m*n*logm)

下面给出上例中涉及的二叉树，感兴趣的童鞋可以手动分析n=4，n=5的划分过程。

10个数分成n组

3 小结

这是一个典型的组合数学问题，通常情况下，类似的问题在第一时间应该想到的是贪心算法或者动态规划算法，想办法理解问题并划分成子问题。