未分類
19 7 月 2020

实际生活中遇到的 [WEB 迎新会上和最多人见面的小组分配] 的算法问题 求思路

实际生活中遇到的 [WEB 迎新会上和最多人见面的小组分配] 的算法问题 求思路

資深大佬 : daweii 11

现在在主持一个公司的视频迎新会，主要目的是让新人跟更多人见见面聊聊天。规则如下：

有 N 个人参加（比如 30 人）。把所有人分配到为几个小房间里，每个房间不超过 6 个人。（为了方便聊天）
每次聊完 30 分钟后把所有人重新分配房间，这个步骤重复 T 次（比如说 3 次）。
如何求每次分组的最优解？
目标是让每一个人见到更多的人。举一个反例，最差的例子是所有的人每次分组都固定在同一个组，这样无论轮多少次，每个人也最多只能见到 6 个人。
像这种问题可以用什么算法解？

因为是实际的例子，下周就要出名单，不是最优解也无所谓，所以随机暴力求解也行。比如说排列组合模拟 10 万次，取里面最好的组合。
但是这个例子实在是长得太像动态规划的算法题了，望大神给点思路。

大佬有話說 (3)

  • 資深大佬 : littlepoem

    抛砖引玉一下。
    假设 30 个人，5 个房间，房间可容纳 6 人，重复 3 次。
    可以看成在纸上画了一个 5*6 矩阵，把 30 个人任意排列 3 次。
    解题开始：
    随意排列矩阵。首先横着看，每一行都是一个分组，因为是第一次排列，每个分组得分都是 5，总得分 30 ；接着再竖着看，因为与第一次排列没有重复项，每个分组得分也是 5，总得分 30 。最后就是求第三次排列，怎么在前 2 次排列的前提下，计算出最大的得分值。
    此方案局限性较强，仅简化一下思路，要是 T 的值大一点，就没啥意义了。

  • 資深大佬 : RJH

    这个题目感觉就是握手问题的变种啊

  • 資深大佬 : remarrexxar

    不求最优的话考虑贪心。
    每次分配先取剩余人员中见过不同人最多的人 X，之后剩余每个成员取 X 没见过的人中见过不同的人最多的人。
    或者每次分配先取剩余人员中见过不同人最多的人 X，之后每次取已成组成员都没见过的人，如果不存在则取见过已成组成员次数最少的人。