将人们分成团队以获得最大的满意度

Question

只是一个好奇的问题。记得在课堂上进行小组作业时，教授会将人们分成一定数量的小组（n)?

我的一些教授会列出一份清单 n 想要与之合作的人以及 n 每个学生中都有一个不想与之共事的人，然后神奇地变成了一群 n 学生将与他们喜欢的人匹配，并避免与他们不喜欢的人一起工作。

对我来说，这个算法听起来很像背包问题，但我想我应该问问大家解决这类问题的方法是什么。

编辑:成立 ACM 文章 描述与我的问题完全相同的东西。读第二段有似曾相识的感觉。

Answer 1

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

我看待问题的方式，我会设置以下 图形:

• 顶点就是学生
• 如果以下两个条件成立，两个学生将通过一条边连接：
  1. 两名学生中至少有一名想要与另一名一起工作。
  2. 两个学生中没有一个不想和另一个一起工作。

然后就是将图划分为大小为 n 的派系的问题。（假设学生人数能被n整除）

如果这是不可能的，我可能会放弃对边缘的第一个约束，并在两个人之间建立边缘，只要他们都没有明确表示他们不想与另一个人一起工作。

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

Answer 2

您可以很容易地作为聚类问题建模这一点，你甚至不会真的需要定义一个空间，你可以实际上只是定义的距离：

请两个人很接近，如果他们都希望一起工作。 关闭如果他们中的一个人想与其他工作。 中等距离，如果有只是冷漠。 远，如果一方不希望工作与其他。

然后，你可以随便找群，耶。然后分手了过大的大小的任何集群，有信心，在集群的人都会被罚款一起工作。

Answer 3

此问题可能是暴力强制，因此我的做法是先蛮力，然后解决它，当我得到一个更好的主意。

Answer 4

有几个你可以使用的算法。一个很好的例子就是所谓的“稳定婚姻问题”，其中有一个完美的解决方案。你可以在这里阅读更多关于它：

http://en.wikipedia.org/wiki/Stable_marriage_problem

在稳定的婚姻问题只有两组人的工作（男性/女性在婚姻中的情况下）。如果要形成对可以使用的变化，稳定的室友问题。在这种情况下，您创建对但每个人都来自于一个单一的池中。

但是，你问一个团队（这是我翻译成每队> 2人）。在这种情况下，你可以对自己最让大家填到最差的比赛，然后运行