调度优化

Question

（我已经为以下内容编写了一个蛮力解决方案，但我想知道是否有更优雅的路径。）

我高中的学生有 8 门选修课。他们选择了第一、第二、第三和第四个选择。由于将有两个选修课，每个人都可以参加他们选择的两个选修课。

然而，尚未确定哪些选修课将安排在这两个期间中的哪一个期间。调度问题是，在了解偏好的情况下，优化这两天的选修课分配，以便尽可能多的学生能够参加他们喜欢的两门选修课。

比如我报了IT和Art，如果时间不同，我只能同时报。当然，您可能已经注册了艺术和法语，而其他人则注册了法语和 IT。

由于只有两个时段，不可能每个人的选择都在不同的时段。我们如何才能找到选修课的最佳分配日期，让尽可能多的人获得他们的两个最佳选择？

我的蛮力解决方案是创建所有可能分配的列表（使用组合包）并测试每个分配。这很好用，因为数据集很小，但肯定有一个更优雅的图论或矩阵解决方案——并且不会与 n 成比例地增加资源！ （n 是提供的课程数量）！

Answer 1

无需测试两个插槽中所有可能的课程组合。您只需要存在于学生选择中的测试组合。每个学生选择 4 门课程会创建 6 对，让学生可以参加两门课程

A,B,C,D => AD,AB,AD,BC,BD,CD

因此，枚举满足至少一个学生的课程配对，并为每个配对计算有多少学生包括该对。学生最多的一对就是答案。

- Construct empty map M, keyed by course pair, value count of students
- LOOP S over students
  - LOOP P over the pairs that let S take two courses
     - IF P in M 
          -increment value of P in map
     - ELSE 
         - add P to M with value 1
- SET PMAX to first pair in M
_ SET VMAX to value of first pair in M
- LOOP P over pairs in M
   - SET V to value of P in M
   - IF V > VMAX
        SET PMAX to P
        SET VMAX to V
- OUTPUT PMAX