把 N 个数尽量分成 K 组，使每组数字的和尽量接近

[mutelog]

把 N 个数尽量分成 K 组，使每组数字的和尽量接近

例如：

Case #1

输入 N = [6, 6, 5, 2, 1, 1], K = 3; 返回[6, 1], [6, 1], [5, 2, 2]

Case #2

输入 N = [6, 6, 5, 2, 1, 1], K = 4; 返回[6], [6], [5], [2, 1, 1]

Case #3

输入 N = [9, 2, 1], K = 2; 返回[9], [2, 1]

[yalanaika]

元素倒排，用平均数向上取整作为初始容量限制，K 个容器，用贪心放元素，贪容器余量不是总量，贪不出上限加 1 重来直到完成
感觉上贪心是最优，没有证明

[GtDzx]

比如先把 N 个数从大到小排序，依次放进当前和最小的组里。最后再把组内 shuffle 一下，使得最终效果看上去不是从大到小的。 觉得还不够还可以模拟退火（随机调整）。

[reus]

每次都把最大的数字，放到总和最小的组里

[geelaw]

@mutelog

这个问题是 NP 困难的，考虑 K 是 2 的情况，这个问题的答案给出 partition problem 的答案。这个问题还是强 NP 困难的，考虑 K 是 3 的情况，这个问题的答案给出 3-partition problem 的答案。

这个问题可以很容易写成 0-1 规划：搞一个 N*K 的矩阵，要求每行的总和等于 1，然后让 X 不小于每列和输入数组的数量积，最后最小化 X。然后可以用标准的分支定界法解决。（第一次得到的松弛解将会是每个元素都是 1/K ）

还可以用枚举所有 K^N 种分组方式的方法得到答案。

[bugcat]

第一步，将 N 从大小到自然排序；
第二步，将 N 的前 K 个，分别作为首个元素生成子数组，增加到新数组中
第三步，遍历 N 剩下的数，每遍历一个数，都统计一下新数组中每一个子数组的和，取最小的那个，将遍历 N 出来的这个数插入进去

……

[GtDzx]

@mutelog 求最优解就是 NP 完全问题了，暴搜吧。

[grayon]

Case #2 [6], [6], [5, 1], [2, 1] 这样是不是也满足 max(sum(Mi))最小

[yalanaika]

算了算，贪心不是最优= =

[mutelog]

@grayon 是的 这个 case 的解不唯一

[yalanaika]

@bugcat 数组 [6 5 3 2 2] K = 2 按照你说的算出来是 [6 2 2] [5 3] 实际最小是 [6 3] [5 2 2]

[kaifeii]

如果是差值和就比较好做，对 K 组共 N 个数做类似快排的二分递归处理，举个 K 是奇数的例子：
f(N,K):
1.先分为三部分:[0,K/2)组集合, 第 K/2 组,[K/2+1,K)组集合，以及计算出平均值 R=N/K(浮点数)
2.每一部分用自身和除以自身组数得到部分平均值 r(浮点数)，每一部分得到平均值差值 r - R
3.进行循环：每次取平均值差值最大和最小的两个部分，做步骤 4，直到步骤 4 无操作
4.如果两个部分内各存在一个数，两数之差小于两组数和之差的一半，进行交换。持续交换直到平均值差值绝对值小于第三个部分或者不存在交换可能。
5.将第一部分和第三部分递归 f(N,K)直到 K=1。
时间复杂度的话：步骤 1，2 是 O(n)；步骤 4 简单做应该是 O(n^2)；回到步骤 3 总共还是 O(n^2)；最后二分递归合起来是 O(n^2logn)

[kaifeii]

步骤 4 写错了，是两数之差小于平均值差的一半。
对于这样做的结果是不是最优解，暂时还没法做完全的论证。

[bugcat]

突发奇想，当两极化比较严重的时候，怎么才算尽量接近？
例：N=[100, 101, 1, 2, 3, 4]，K=4
返回 1 [100], [101], [2,3], [1, 4]
返回 2 [100], [101], [1,2,3], [4]

这两种返回，哪种才算尽量接近？

[weyou]

@bugcat 按照楼主的定义， 这两种都算对

[bugcat]

@weyou 所以，我觉得每组的和，方差最小的才算最优

[zhengjian]

这是一维的 KMeans 算法么？

[Vinty]

这明显是个 NP 问题啊，遗传算法做比较快吧
某类确定性算法对数组的分布肯定有要求的，比如楼上提到有最大和最小匹配，或者排序二分这种，随机优化的话没有这种麻烦的

[doctorlai]

V 站有没有 “算法” 的标签？ 没有的话是否加一个？ @Livid

[weyou]

刚写了个基于平均数的贪心算法，肯定不是最优，只能做到大多数情况能用用。

https://gist.github.com/weyou/d0fb3cf7d811afd9fdc555b528618154

[af463419014]

虽然我也不会,不过找到个链接,可以看看
https://en.wikipedia.org/wiki/Partition_problem#The_k-partition_problem