人员分组问题

V2EX = way to explore

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

现在注册

已注册用户请登录

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

自己想到的一个问题

把 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 人
尽量平均分
尽量多的往前面组里分

分成

要求

组里分

个人

12 条回复

0ZXYDDu796nVCFxq

2021-12-13 17:44:56 +08:00 via Android

10 个人分 3 组为什么不是 8,1,1 ？

n0th1ng

2021-12-13 17:46:39 +08:00 via Android

@gstqc 少写了个条件，尽量平均分给前面的组

GuuJiang

2021-12-13 18:06:38 +08:00 via iPhone

“尽量分到前面”缺乏准确的定义，(3,3,3,2)难道不是比(4,4,2,1)更“平均”？

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

2021-12-13 18:14:38 +08:00 via Android

@GuuJiang 那就再加一个条件，尽可能多的分给前面的组

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

2021-12-13 18:30:22 +08:00

你把 [尽量多的往前面组里分] 讲明白了不就自然能写出来了
你这属于猜产品经理想法题，而不是算法题

zhuangjia

2021-12-13 18:35:01 +08:00

尽量多的往前面组里分:
把 13 个人分到 4 个组里，可分成(4,3,3,3),但根据要求，要分成(4,4,4,1) ==> (5,5,2,1) 看起来更符合条件

wolfie

2021-12-13 18:35:36 +08:00

16 分 4 组，是 [5, 5, 5, 1] 还是 [5, 5, 4, 2]
这就没有标准答案，同样地参数，你扔给产品 2 次，都不一定有相同结果。

n0th1ng

2021-12-13 21:21:53 +08:00 via Android

@GuuJiang 你说的对，11 分 4 组的最优解是（ 3,3,3,2 ）

n0th1ng

2021-12-13 21:22:40 +08:00 via Android

谢谢各位，我再捋捋

GuuJiang

2021-12-13 21:38:55 +08:00

@n0th1ng
如果是这样的话就非常简单了，前面 n-1 组是 ceil(m/n)，剩下的放最后一组

PS：如果不想使用浮点运算及 ceil 函数，可以使用(m+n-1)/n 来代替