特定分组算法

Question

我正在编写一个程序，根据学生和导师的可用性来组建辅导小组。可用性是用字母表示的阻塞时间列表给出的。例如，如果一个学生以[A， C， D]的形式给出他的可用性，那么他在一天的第一、第三和第四个小时都有空。你如何制作一个函数，它接受学生列表和导师列表，并给出一组列表，从而最大限度地增加一组中的学生数量？我在Java工作，但我对算法比对代码本身更感兴趣。更多细节：

小组必须包含3-6名学生和1名导师。

学生只能在一个组。

必须最大化满足学生人数（分组）。例如，假设我们有1-6名学生和两名导师，分别在A和B时间段提供。学生的导师在1:A、2:A、3:A、4:AB、5:AB、6:B时间段可用。算法应返回两组：[1，2，3，tutor1]和[4，5，6，tutor2]。这会将每个学生分配到某个组，最好是说，在一个组中放1-5人，不放6人。

Answer 1

你可以把这个问题看作一个图的问题:用一组不相交的子图覆盖一个二部图，同时尊重两个分区(学生，组)并最大化一个分区(学生)的覆盖

我在考虑这个启发：

• 从空溶液开始
• 虽然有未分配的学生和开放的（少于六名成员）小组：
  • 按空闲时段的顺序对未分配的学生进行排序
  • 从列表顶部挑选六名学生（从顶部阅读列表，直到找到一个六名学生可以参加的小组），并将他们作为一个小组使用
  • 如果你不能选择六个学生，请选择你能选择的最大数量
  • 如果你找不到三个学生组成一个小组，但你有两个：
    • 为该小组找第三个学生，该学生目前被分配到一个小组，你可以从中挑选（超过三个人），并用他来填补这个小组。首选可以从未分配集合中重新填充的组
    • 如果找不到第三个人，请从其他三人小组中选择一人。重复搜索该组中的替代者（或放弃）。您可以尝试并行地从不同的三个成员组中删除

    请注意，这可以归结为:

    快速找到一个能满足大多数人的解决方案（你可以停在这里）。然后尝试通过找到一系列配对来插入学生：

    • 在已用配对和未使用的配对之间交替
    • 从学生开始
    • 在一堂课上结束

    请注意，这与在二分图中寻找交替路径是同构的，并且可以这样优化。

    请注意，这可能仍然无法找到最佳解决方案，因为它永远不会在单个组中替换多个人员来满足一个人。

    上面的伪代码指示在每个步骤使用学生列表。相反，您可以跟踪对此列表的更改，并在进行更新时更新排序顺序。

    更新:我没注意到你也想分配老师。

    在这种情况下，您需要在将学生分配到小组时将教师分配到该小组。这将阻止创建某些组，但是如果没有免费的教师，则可以从不同的组中获取教师，如果您可以为该组分配其他教师。同样，它只是搜索一个交替的图表，这次是在教师小组子图中 - 让学生四处走动以释放教师似乎不可行。

    你现在要覆盖的整个图形有三个分区：学生，老师，组。老师和学生不互动，所以有两层：学生-组，组-老师。这两层是独立的，除了它们必须覆盖同一组组。

Answer 2

以下是帮助您入门的3个想法。

>

一个贪婪的算法。将列表中的第一个学生与列表中的第一个兼容导师匹配。将列表中的第二个学生与列表中的第一个兼容导师匹配。等。

找到最“受欢迎”的可用小时，并首先匹配该小时。然后是下一个最受欢迎的，等等。

找到最不“受欢迎”的可用小时，并首先匹配该小时。然后是下一个最不受欢迎的，等等。

免责声明:我假设你是为了学习/爱好/管理的方便而工作，换句话说，你的项目没有很多钱。如果我的假设是错误的，我会建议你需要多研究算法，或者聘请有专长的人。