V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mutelog
V2EX  ›  程序员

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

  •  
  •   mutelog · 2017-05-26 09:43:45 +08:00 · 10970 次点击
    这是一个创建于 2739 天前的主题,其中的信息可能已经有所发展或是发生改变。

    把 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 个分组
    45 条回复    2019-03-24 23:57:35 +08:00
    kingmo888
        1
    kingmo888  
       2017-05-26 09:47:02 +08:00
    哇,感觉彼此联动性好高啊。这个必须有个超棒的算法才行
    lechain
        2
    lechain  
       2017-05-26 09:48:29 +08:00 via Android   ❤️ 1
    求和,取平均,以平均值为背包容量动归,

    好久没做算法训练了,不知道对不对(;´∀`)
    SYP
        3
    SYP  
       2017-05-26 09:50:42 +08:00
    m*n 个相同的数怎么算?
    kingmo888
        4
    kingmo888  
       2017-05-26 09:51:01 +08:00
    需要几个假设条件吧,比如元素都大于 0,什么的。

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

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

    只想到这。。。

    学渣献丑
    xxlong
        5
    xxlong  
       2017-05-26 10:35:45 +08:00
    条件不够吧? k 的值有没有什么要求?否则结果不唯一的
    timle1029
        6
    timle1029  
       2017-05-26 11:07:45 +08:00
    可以用 HashMap 来记录 k 个不同的组,如果元素大于 0,把当前的元素加到和最小的那组里去,如果小于 0 就加到和最大的那组去。
    palmers
        7
    palmers  
       2017-05-26 11:12:49 +08:00
    记录每个元素的方差和元素的映射然后再进行分组是不是可以
    mutelog
        9
    mutelog  
    OP
       2017-05-26 11:19:02 +08:00 via iPhone
    @lrxiao 分组不需要保持数组元素的原始顺序
    hxsf
        10
    hxsf  
       2017-05-26 11:32:48 +08:00
    1. 从大到小排序。初始化 k 个组。
    2. 将最大的放到和最小的组里去。
    3. 重复 2 直到放完。

    感觉这样能过 楼主的 3 个 case
    hxsf
        11
    hxsf  
       2017-05-26 11:34:09 +08:00
    @hxsf #10 前端的瀑布流布局的写法。。。
    http://www.ihxsf.cn/dynamic/ 最后结果看起来也挺正常。
    hxsf
        12
    hxsf  
       2017-05-26 11:34:58 +08:00
    @hxsf #11 对了,这个网页没做从大到小排序,所以可能结果看着不是很齐。
    geelaw
        13
    geelaw  
       2017-05-26 11:35:36 +08:00
    你这个问题不是 well-asked,什么叫“尽量接近”?
    mutelog
        14
    mutelog  
    OP
       2017-05-26 11:42:00 +08:00 via iPhone
    @geelaw “尽量接近”的精确定义:最小化 max(sum(Mi)) Mi 是得到的 K 个分组
    am241
        15
    am241  
       2017-05-26 11:42:45 +08:00 via Android
    这不就是 k 近邻算法吗??
    am241
        16
    am241  
       2017-05-26 11:46:47 +08:00 via Android
    sorry 看错题目了
    kaifeii
        17
    kaifeii  
       2017-05-26 11:50:23 +08:00
    和尽量接近是按方差算吗?还是差值的和?这个要说清楚吧
    mutelog
        18
    mutelog  
    OP
       2017-05-26 11:54:42 +08:00 via iPhone
    @kaifeii 抱歉啊描述的不准确 请参考附言 3
    GtDzx
        19
    GtDzx  
       2017-05-26 11:54:53 +08:00
    这种实际工程不需要最优解随便乱搞一下就能有不错的效果
    mutelog
        20
    mutelog  
    OP
       2017-05-26 11:55:46 +08:00 via iPhone
    @GtDzx 这是一道面试题 求最优解
    yalanaika
        21
    yalanaika  
       2017-05-26 11:56:59 +08:00
    元素倒排,用平均数向上取整作为初始容量限制,K 个容器,用贪心放元素,贪容器余量不是总量,贪不出上限加 1 重来直到完成
    感觉上贪心是最优,没有证明
    GtDzx
        22
    GtDzx  
       2017-05-26 11:57:48 +08:00
    比如先把 N 个数从大到小排序,依次放进当前和最小的组里。最后再把组内 shuffle 一下,使得最终效果看上去不是从大到小的。 觉得还不够还可以模拟退火(随机调整)。
    reus
        23
    reus  
       2017-05-26 11:59:04 +08:00   ❤️ 1
    每次都把最大的数字,放到总和最小的组里
    geelaw
        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 种分组方式的方法得到答案。
    bugcat
        25
    bugcat  
       2017-05-26 12:01:46 +08:00
    第一步,将 N 从大小到自然排序;
    第二步,将 N 的前 K 个,分别作为首个元素生成子数组,增加到新数组中
    第三步,遍历 N 剩下的数,每遍历一个数,都统计一下新数组中每一个子数组的和,取最小的那个,将遍历 N 出来的这个数插入进去

    ……
    GtDzx
        26
    GtDzx  
       2017-05-26 12:04:34 +08:00
    @mutelog 求最优解就是 NP 完全问题了,暴搜吧。
    grayon
        27
    grayon  
       2017-05-26 12:06:57 +08:00
    Case #2 [6], [6], [5, 1], [2, 1] 这样是不是也满足 max(sum(Mi))最小
    yalanaika
        28
    yalanaika  
       2017-05-26 12:08:13 +08:00 via Android
    算了算,贪心不是最优= =
    mutelog
        29
    mutelog  
    OP
       2017-05-26 12:17:18 +08:00 via iPhone
    @grayon 是的 这个 case 的解不唯一
    yalanaika
        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]
    kaifeii
        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)
    kaifeii
        32
    kaifeii  
       2017-05-26 12:27:43 +08:00
    步骤 4 写错了,是两数之差小于平均值差的一半。
    对于这样做的结果是不是最优解,暂时还没法做完全的论证。
    bugcat
        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]

    这两种返回,哪种才算尽量接近?
    weyou
        34
    weyou  
       2017-05-26 15:13:20 +08:00
    @bugcat 按照楼主的定义, 这两种都算对
    bugcat
        35
    bugcat  
       2017-05-26 15:19:44 +08:00
    @weyou 所以,我觉得每组的和,方差最小的才算最优
    zhengjian
        36
    zhengjian  
       2017-05-26 15:55:52 +08:00
    这是一维的 KMeans 算法么?
    Vinty
        37
    Vinty  
       2017-05-26 16:43:21 +08:00
    这明显是个 NP 问题啊,遗传算法做比较快吧
    某类确定性算法对数组的分布肯定有要求的,比如楼上提到有最大和最小匹配,或者排序二分这种,随机优化的话没有这种麻烦的
    doctorlai
        38
    doctorlai  
       2017-05-26 16:55:29 +08:00
    V 站有没有 “算法” 的标签? 没有的话是否加一个? @Livid
    weyou
        39
    weyou  
       2017-05-26 17:03:18 +08:00   ❤️ 1
    刚写了个基于平均数的贪心算法,肯定不是最优,只能做到大多数情况能用用。

    https://gist.github.com/weyou/d0fb3cf7d811afd9fdc555b528618154
    af463419014
        40
    af463419014  
       2017-05-26 17:21:27 +08:00
    虽然我也不会,不过找到个链接,可以看看
    https://en.wikipedia.org/wiki/Partition_problem#The_k-partition_problem
    ZhLTE
        41
    ZhLTE  
       2017-05-26 17:23:03 +08:00
    @reus 我觉得 你这个最稳也
    ruoyu0088
        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。
    geelaw
        43
    geelaw  
       2017-05-26 20:06:35 +08:00
    @kaifeii #31 没懂什么是“差值和”,你是指平均差么?无论怎么样,如果 K=2 的时候,假设数据可以分成和相等的两组时最优的情况总是返回两组相等的结果,那么目前没人发现多项式时间算法。

    @Vinty #37 最短路(判定版)也是 NP 问题,这样说没有增加什么有意思的内容。或许你想表达的不是“这个问题是 NP 问题”,而是“这个问题是 NPC 问题”。
    kinglisky
        44
    kinglisky  
       2019-03-24 23:50:49 +08:00
    @mutelog 所以有解决方法了,最近也在研究这个问题
    kinglisky
        45
    kinglisky  
       2019-03-24 23:57:35 +08:00
    少了个吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2702 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 03:57 · PVG 11:57 · LAX 19:57 · JFK 22:57
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.