把 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
kingmo888 2017-05-26 09:47:02 +08:00
哇,感觉彼此联动性好高啊。这个必须有个超棒的算法才行
|
2
lechain 2017-05-26 09:48:29 +08:00 via Android 1
求和,取平均,以平均值为背包容量动归,
好久没做算法训练了,不知道对不对(;´∀`) |
3
SYP 2017-05-26 09:50:42 +08:00
m*n 个相同的数怎么算?
|
4
kingmo888 2017-05-26 09:51:01 +08:00
需要几个假设条件吧,比如元素都大于 0,什么的。
假设组内各元素均大于 0. 求均值,超过 N 倍标准差的记作异常值然后先放一边,将剩余的部分在有限数量下(必须得够 k 组)的和是否能最贴近异常值,如果能就先按照这个来,不能异常值就放一边单独一组。 只想到这。。。 学渣献丑 |
5
xxlong 2017-05-26 10:35:45 +08:00
条件不够吧? k 的值有没有什么要求?否则结果不唯一的
|
6
timle1029 2017-05-26 11:07:45 +08:00
可以用 HashMap 来记录 k 个不同的组,如果元素大于 0,把当前的元素加到和最小的那组里去,如果小于 0 就加到和最大的那组去。
|
7
palmers 2017-05-26 11:12:49 +08:00
记录每个元素的方差和元素的映射然后再进行分组是不是可以
|
8
lrxiao 2017-05-26 11:17:23 +08:00
|
10
hxsf 2017-05-26 11:32:48 +08:00
1. 从大到小排序。初始化 k 个组。
2. 将最大的放到和最小的组里去。 3. 重复 2 直到放完。 感觉这样能过 楼主的 3 个 case |
11
hxsf 2017-05-26 11:34:09 +08:00
|
13
geelaw 2017-05-26 11:35:36 +08:00
你这个问题不是 well-asked,什么叫“尽量接近”?
|
14
mutelog OP @geelaw “尽量接近”的精确定义:最小化 max(sum(Mi)) Mi 是得到的 K 个分组
|
15
am241 2017-05-26 11:42:45 +08:00 via Android
这不就是 k 近邻算法吗??
|
16
am241 2017-05-26 11:46:47 +08:00 via Android
sorry 看错题目了
|
17
kaifeii 2017-05-26 11:50:23 +08:00
和尽量接近是按方差算吗?还是差值的和?这个要说清楚吧
|
19
GtDzx 2017-05-26 11:54:53 +08:00
这种实际工程不需要最优解随便乱搞一下就能有不错的效果
|
21
yalanaika 2017-05-26 11:56:59 +08:00
元素倒排,用平均数向上取整作为初始容量限制,K 个容器,用贪心放元素,贪容器余量不是总量,贪不出上限加 1 重来直到完成
感觉上贪心是最优,没有证明 |
22
GtDzx 2017-05-26 11:57:48 +08:00
比如先把 N 个数从大到小排序,依次放进当前和最小的组里。最后再把组内 shuffle 一下,使得最终效果看上去不是从大到小的。 觉得还不够还可以模拟退火(随机调整)。
|
23
reus 2017-05-26 11:59:04 +08:00 1
每次都把最大的数字,放到总和最小的组里
|
24
geelaw 2017-05-26 12:00:54 +08:00 3
@mutelog
这个问题是 NP 困难的,考虑 K 是 2 的情况,这个问题的答案给出 partition problem 的答案。这个问题还是强 NP 困难的,考虑 K 是 3 的情况,这个问题的答案给出 3-partition problem 的答案。 这个问题可以很容易写成 0-1 规划:搞一个 N*K 的矩阵,要求每行的总和等于 1,然后让 X 不小于每列和输入数组的数量积,最后最小化 X。然后可以用标准的分支定界法解决。(第一次得到的松弛解将会是每个元素都是 1/K ) 还可以用枚举所有 K^N 种分组方式的方法得到答案。 |
25
bugcat 2017-05-26 12:01:46 +08:00
第一步,将 N 从大小到自然排序;
第二步,将 N 的前 K 个,分别作为首个元素生成子数组,增加到新数组中 第三步,遍历 N 剩下的数,每遍历一个数,都统计一下新数组中每一个子数组的和,取最小的那个,将遍历 N 出来的这个数插入进去 …… |
27
grayon 2017-05-26 12:06:57 +08:00
Case #2 [6], [6], [5, 1], [2, 1] 这样是不是也满足 max(sum(Mi))最小
|
28
yalanaika 2017-05-26 12:08:13 +08:00 via Android
算了算,贪心不是最优= =
|
30
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]
|
31
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) |
32
kaifeii 2017-05-26 12:27:43 +08:00
步骤 4 写错了,是两数之差小于平均值差的一半。
对于这样做的结果是不是最优解,暂时还没法做完全的论证。 |
33
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] 这两种返回,哪种才算尽量接近? |
36
zhengjian 2017-05-26 15:55:52 +08:00
这是一维的 KMeans 算法么?
|
37
Vinty 2017-05-26 16:43:21 +08:00
这明显是个 NP 问题啊,遗传算法做比较快吧
某类确定性算法对数组的分布肯定有要求的,比如楼上提到有最大和最小匹配,或者排序二分这种,随机优化的话没有这种麻烦的 |
39
weyou 2017-05-26 17:03:18 +08:00 1
|
40
af463419014 2017-05-26 17:21:27 +08:00
虽然我也不会,不过找到个链接,可以看看
https://en.wikipedia.org/wiki/Partition_problem#The_k-partition_problem |
42
ruoyu0088 2017-05-26 19:27:05 +08:00 1
可以用 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。 |
43
geelaw 2017-05-26 20:06:35 +08:00
|
45
kinglisky 2019-03-24 23:57:35 +08:00
少了个吗
|