为了获得最大的满意度，把人分成几个小组

Question

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

我的一些教授会从每个学生那里拿出一份清单，列出想和n一起工作的人和不想和他们一起工作的n人，然后神奇地找出一组n，在那里学生会与他们喜欢的人匹配，而避免与他们不喜欢的人合作。

对我来说，这个算法听起来很像一个背包问题，但是我想我会问一下你对这类问题的解决方法。

编辑：找到了描述与我问题完全相似的东西的ACM文章。阅读第二段以获得似曾相识的感觉。

Answer 1

对我来说，这听起来更像是某种小集团问题。

按照我对问题的看法，我设置了以下图表

• 顶点将是学生
• 如果这两种情况都成立，两个学生就会有一个边缘连接：
  1. 这两个学生中至少有一个想和另一个一起工作。
  2. 这两个学生中没有一个不想和另一个一起工作。

​

然后，将图划分为n个大小的团(假设学生人数可被n整除)。

如果这是不可能的，我可能会让边上的第一个约束溜走，并且在两个人之间有边，只要他们都不明确地说他们不想和另一个人一起工作。

至于有效解决这个问题的方法，我不知道，但希望这能让你更深入地了解这个问题。

Answer 2

您可以很容易地将其建模为集群问题，甚至不需要定义空间，只需定义距离：

如果两个人都想一起工作的话，两个人就很亲近了。如果其中一个想和另一个一起工作，就关闭。中距离如果只是冷漠的话。如果其中一个不想和另一个一起工作的话。

那你就能找到集群了，耶。然后将任何规模过大的集群分割开来，相信集群中的人都会很好地一起工作。

Answer 3

这个问题可能是蛮力的，所以我的方法是先用暴力强迫它，然后当我有了更好的想法时再修复它。