将人们分成团队以获得最大的满足感

Question

只是一个好奇的问题.还记得在课堂小组中,教授会把人分成一定数量的小组(n)吗？

我的一些教授会列出n一个想要与之合作的n人和一个不想与每个学生一起工作的人的名单,然后神奇地将n学生与他们喜欢的人匹配的小组变成一组,避免与他们一起工作他们不喜欢的人.

对我来说,这个算法听起来很像背包问题,但我想我会问你对这类问题的解决方法是什么.

编辑:找到一篇描述与我的问题完全相同的ACM文章.为了似曾相识,请阅读第二段.

Answer 1

对我而言,这听起来更像某种集团问题.

我看到问题的方式,我将设置以下图表:

• 顶点是学生
• 如果以下两个方面都存在,则两个学生将通过边缘连接:
  1. 这两个学生中至少有一个想和另一个学生一起工作.
  2. 这两个学生都不想与另一个学生一起工作.

然后将图形划分为大小为n的集团.(假设学生人数可以被n整除)

如果这是不可能的,我可能会让边缘上的第一个约束滑动,并且在两个人之间有边缘,只要它们都没有明确表示他们不想与另一个人合作.

至于有效解决这个问题的方法,我不知道,但这有望让你更接近对这个问题的一些见解.