这是一个创建于 1598 天前的主题，其中的信息可能已经有所发展或是发生改变。
现在在主持一个公司的视频迎新会，主要目的是让新人跟更多人见见面聊聊天。规则如下：
有 N 个人参加（比如 30 人）。把所有人分配到为几个小房间里，每个房间不超过 6 个人。（为了方便聊天）
每次聊完 30 分钟后把所有人重新分配房间，这个步骤重复 T 次（比如说 3 次）。
如何求每次分组的最优解？
目标是让每一个人见到更多的人。举一个反例，最差的例子是所有的人每次分组都固定在同一个组，这样无论轮多少次，每个人也最多只能见到 6 个人。
像这种问题可以用什么算法解？
因为是实际的例子，下周就要出名单，不是最优解也无所谓，所以随机暴力求解也行。比如说排列组合模拟 10 万次，取里面最好的组合。
但是这个例子实在是长得太像动态规划的算法题了，望大神给点思路。
有 N 个人参加（比如 30 人）。把所有人分配到为几个小房间里，每个房间不超过 6 个人。（为了方便聊天）
每次聊完 30 分钟后把所有人重新分配房间，这个步骤重复 T 次（比如说 3 次）。
如何求每次分组的最优解？
目标是让每一个人见到更多的人。举一个反例，最差的例子是所有的人每次分组都固定在同一个组，这样无论轮多少次，每个人也最多只能见到 6 个人。
像这种问题可以用什么算法解？
因为是实际的例子，下周就要出名单，不是最优解也无所谓，所以随机暴力求解也行。比如说排列组合模拟 10 万次，取里面最好的组合。
但是这个例子实在是长得太像动态规划的算法题了，望大神给点思路。
 |
1
littlepoem 2020-07-10 09:36:48 +08:00  1
抛砖引玉一下。
假设 30 个人，5 个房间，房间可容纳 6 人，重复 3 次。 可以看成在纸上画了一个 5*6 矩阵，把 30 个人任意排列 3 次。 解题开始： 随意排列矩阵。首先横着看，每一行都是一个分组，因为是第一次排列，每个分组得分都是 5，总得分 30 ；接着再竖着看，因为与第一次排列没有重复项，每个分组得分也是 5，总得分 30 。最后就是求第三次排列，怎么在前 2 次排列的前提下，计算出最大的得分值。 此方案局限性较强，仅简化一下思路，要是 T 的值大一点，就没啥意义了。 |
 |
2
RJH 2020-07-10 10:15:41 +08:00 1
这个题目感觉就是握手问题的变种啊
|
 |
3
remarrexxar 2020-07-10 10:57:41 +08:00 1
不求最优的话考虑贪心。
每次分配先取剩余人员中见过不同人最多的人 X，之后剩余每个成员取 X 没见过的人中见过不同的人最多的人。 或者每次分配先取剩余人员中见过不同人最多的人 X，之后每次取已成组成员都没见过的人，如果不存在则取见过已成组成员次数最少的人。 |
Select Language