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

人员分组问题

  •  
  •   n0th1ng · 2021-12-13 17:28:25 +08:00 · 1070 次点击
    这是一个创建于 836 天前的主题,其中的信息可能已经有所发展或是发生改变。

    自己想到的一个问题

    把 m 个人分到有顺序的 n 个组 g1,g2,g3...gn 里,要求

    • 每个组至少有 1 人
    • 尽量往前面组里分

    例如

    • 把 10 个人分到 3 个组里,可分成(4,3,3),但根据要求,要分成(4,4,2)
    • 把 13 个人分到 4 个组里,可分成(4,3,3,3),但根据要求,要分成(4,4,4,1)
    • 把 11 个人分到 4 个组里,可分成(3,3,3,2),但根据要求,要分成(4,4,2,1)

    一般算法是怎样的?

    第 1 条附言  ·  2021-12-13 18:03:30 +08:00
    是尽量平均分到前面的组里
    第 2 条附言  ·  2021-12-13 18:25:29 +08:00
    要求

    每个组至少有 1 人
    尽量平均分
    尽量多的往前面组里分
    gstqc
        1
    gstqc  
       2021-12-13 17:44:56 +08:00 via Android
    10 个人分 3 组为什么不是 8,1,1 ?
    n0th1ng
        2
    n0th1ng  
    OP
       2021-12-13 17:46:39 +08:00 via Android
    @gstqc 少写了个条件,尽量平均分给前面的组
    GuuJiang
        3
    GuuJiang  
       2021-12-13 18:06:38 +08:00 via iPhone
    “尽量分到前面”缺乏准确的定义,(3,3,3,2)难道不是比(4,4,2,1)更“平均”?
    jmc891205
        4
    jmc891205  
       2021-12-13 18:11:47 +08:00
    找到比 m 小的最大的能被 n-1 整除的数字 k
    然后答案就是 k/(n-1), k/(n-1), ..., k/(n-1), m-k
    n0th1ng
        5
    n0th1ng  
    OP
       2021-12-13 18:14:38 +08:00 via Android
    @GuuJiang 那就再加一个条件,尽可能多的分给前面的组
    GuuJiang
        6
    GuuJiang  
       2021-12-13 18:28:54 +08:00
    @n0th1ng
    如果按“尽可能多的分给前面的组”,那么 11 就应该是(8,1,1,1)
    如果是“平均的部分占比最多”,那么(3,3,3,2)应该是比(4,4,2,1)更优

    你还是先把定义想清楚吧,或者如果你是想解决某个实际中的场景,不妨说下原始问题,以免成为一个 XY 问题
    mxT52CRuqR6o5
        7
    mxT52CRuqR6o5  
       2021-12-13 18:30:22 +08:00
    你把 [尽量多的往前面组里分] 讲明白了不就自然能写出来了
    你这属于猜产品经理想法题,而不是算法题
    zhuangjia
        8
    zhuangjia  
       2021-12-13 18:35:01 +08:00
    尽量多的往前面组里分:
    把 13 个人分到 4 个组里,可分成(4,3,3,3),但根据要求,要分成(4,4,4,1) ==> (5,5,2,1) 看起来更符合条件
    wolfie
        9
    wolfie  
       2021-12-13 18:35:36 +08:00
    16 分 4 组,是 [5, 5, 5, 1] 还是 [5, 5, 4, 2]
    这就没有标准答案,同样地参数,你扔给产品 2 次,都不一定有相同结果。
    n0th1ng
        10
    n0th1ng  
    OP
       2021-12-13 21:21:53 +08:00 via Android
    @GuuJiang 你说的对,11 分 4 组的最优解是( 3,3,3,2 )
    n0th1ng
        11
    n0th1ng  
    OP
       2021-12-13 21:22:40 +08:00 via Android
    谢谢各位,我再捋捋
    GuuJiang
        12
    GuuJiang  
       2021-12-13 21:38:55 +08:00   ❤️ 1
    @n0th1ng
    如果是这样的话就非常简单了,前面 n-1 组是 ceil(m/n),剩下的放最后一组

    PS:如果不想使用浮点运算及 ceil 函数,可以使用(m+n-1)/n 来代替
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3424 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 11:14 · PVG 19:14 · LAX 04:14 · JFK 07:14
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.