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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2749 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

第 1 条附言 · 2017-05-26 11:17:08 +08:00

更正：第一组用例结果应该是 [6,1],[6,1],[5,2]

数组元素均为正整数

数组 N 恰好分成 K 组 K 不大于 N 的长度

第 2 条附言 · 2017-05-26 11:18:43 +08:00

分组不需要保护数组元素的原始顺序

第 3 条附言 · 2017-05-26 11:41:27 +08:00

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

Case

个数

尽量

输入

45 条回复 • 2019-03-24 23:57:35 +08:00

kingmo888

2017-05-26 09:47:02 +08:00

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

lechain

2017-05-26 09:48:29 +08:00 via Android

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

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

SYP

2017-05-26 09:50:42 +08:00

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

kingmo888

2017-05-26 09:51:01 +08:00

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

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

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

只想到这。。。

学渣献丑

xxlong

2017-05-26 10:35:45 +08:00

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

timle1029

2017-05-26 11:07:45 +08:00

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

palmers

2017-05-26 11:12:49 +08:00

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

lrxiao

2017-05-26 11:17:23 +08:00

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

2017-05-26 11:19:02 +08:00 via iPhone

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

hxsf

2017-05-26 11:32:48 +08:00

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

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

hxsf

2017-05-26 11:34:09 +08:00

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

hxsf

2017-05-26 11:34:58 +08:00

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

geelaw

2017-05-26 11:35:36 +08:00

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

mutelog

2017-05-26 11:42:00 +08:00 via iPhone

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

am241

2017-05-26 11:42:45 +08:00 via Android

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

am241

2017-05-26 11:46:47 +08:00 via Android

sorry 看错题目了

kaifeii

2017-05-26 11:50:23 +08:00

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

mutelog

2017-05-26 11:54:42 +08:00 via iPhone

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

GtDzx

2017-05-26 11:54:53 +08:00

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

mutelog

2017-05-26 11:55:46 +08:00 via iPhone

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

yalanaika

2017-05-26 11:56:59 +08:00

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

GtDzx

2017-05-26 11:57:48 +08:00

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

reus

2017-05-26 11:59:04 +08:00

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

geelaw

2017-05-26 12:00:54 +08:00

@mutelog

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

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

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

bugcat

2017-05-26 12:01:46 +08:00

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

……

GtDzx

2017-05-26 12:04:34 +08:00

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

grayon

2017-05-26 12:06:57 +08:00

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

yalanaika

2017-05-26 12:08:13 +08:00 via Android

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

mutelog

2017-05-26 12:17:18 +08:00 via iPhone

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

yalanaika

2017-05-26 12:20:33 +08:00

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

kaifeii

2017-05-26 12:20:49 +08:00

如果是差值和就比较好做，对 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

2017-05-26 12:27:43 +08:00

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

bugcat

2017-05-26 15:10:44 +08:00

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

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

weyou

2017-05-26 15:13:20 +08:00

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

bugcat

2017-05-26 15:19:44 +08:00

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

zhengjian

2017-05-26 15:55:52 +08:00

这是一维的 KMeans 算法么？

Vinty

2017-05-26 16:43:21 +08:00

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

doctorlai

2017-05-26 16:55:29 +08:00

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

weyou

2017-05-26 17:03:18 +08:00

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

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

af463419014

2017-05-26 17:21:27 +08:00

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

ZhLTE

2017-05-26 17:23:03 +08:00

@reus 我觉得你这个最稳也

ruoyu0088

2017-05-26 19:27:05 +08:00

可以用 google 的 or-tools 解，下面是一个例子：

https://gist.github.com/ruoyu0088/d100e678718572f8d1378be8704e70fd

把[13, 41, 9, 21, 12, 36, 33, 35, 46, 29, 18, 11, 36, 6, 29, 32, 43, 5, 49, 33]分为 6 组
结果是
[[36, 5, 49], [29, 29, 32], [46, 43], [36, 35, 18], [12, 33, 11, 33], [13, 41, 9, 21, 6]]
每个分组的和为：
[90, 90, 89, 89, 89, 90]

运行程序时，需要选择合适的 cut_rate 和 max_time。

geelaw

2017-05-26 20:06:35 +08:00

@kaifeii #31 没懂什么是“差值和”，你是指平均差么？无论怎么样，如果 K=2 的时候，假设数据可以分成和相等的两组时最优的情况总是返回两组相等的结果，那么目前没人发现多项式时间算法。

@Vinty #37 最短路（判定版）也是 NP 问题，这样说没有增加什么有意思的内容。或许你想表达的不是“这个问题是 NP 问题”，而是“这个问题是 NPC 问题”。

kinglisky

2019-03-24 23:50:49 +08:00

@mutelog 所以有解决方法了，最近也在研究这个问题

kinglisky

2019-03-24 23:57:35 +08:00

少了个吗