把 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]

[kingmo888]

哇，感觉彼此联动性好高啊。这个必须有个超棒的算法才行

[lechain]

求和，取平均，以平均值为背包容量动归，

好久没做算法训练了，不知道对不对(；´∀｀)

[SYP]

m*n 个相同的数怎么算？

[kingmo888]

需要几个假设条件吧，比如元素都大于 0，什么的。

假设组内各元素均大于 0.

求均值，超过 N 倍标准差的记作异常值然后先放一边，将剩余的部分在有限数量下（必须得够 k 组）的和是否能最贴近异常值，如果能就先按照这个来，不能异常值就放一边单独一组。

只想到这。。。

学渣献丑

[xxlong]

条件不够吧？ k 的值有没有什么要求？否则结果不唯一的

[timle1029]

可以用 HashMap 来记录 k 个不同的组，如果元素大于 0，把当前的元素加到和最小的那组里去，如果小于 0 就加到和最大的那组去。

[palmers]

记录每个元素的方差和元素的映射然后再进行分组是不是可以

[lrxiao]

https://www.quora.com/A-group-of-N-integer-numbers-need-to-be-divided-fairly-into-K-subgroups-A-fair-division-is-that-the-max-of-the-sums-of-K-subgroups-is-minimal

[mutelog]

@lrxiao 分组不需要保持数组元素的原始顺序

[hxsf]

1. 从大到小排序。初始化 k 个组。
2. 将最大的放到和最小的组里去。
3. 重复 2 直到放完。

感觉这样能过 楼主的 3 个 case

[hxsf]

@hxsf #10 前端的瀑布流布局的写法。。。
http://www.ihxsf.cn/dynamic/ 最后结果看起来也挺正常。

[hxsf]

@hxsf #11 对了，这个网页没做从大到小排序，所以可能结果看着不是很齐。

[geelaw]

你这个问题不是 well-asked，什么叫“尽量接近”？

[mutelog]

@geelaw “尽量接近”的精确定义：最小化 max(sum(Mi)) Mi 是得到的 K 个分组

[am241]

这不就是 k 近邻算法吗？？

[am241]

sorry 看错题目了

[kaifeii]

和尽量接近是按方差算吗？还是差值的和？这个要说清楚吧

[mutelog]

@kaifeii 抱歉啊描述的不准确 请参考附言 3

[GtDzx]

这种实际工程不需要最优解随便乱搞一下就能有不错的效果

[mutelog]

@GtDzx 这是一道面试题 求最优解