我目前正在编写一个将学生映射到课程的程序。目前，我正在使用 SAT-Solver，但我正在尝试实现一个多项式时间/非贪婪算法来解决以下子问题：
- 有学生（50-150）
- 有科目（10-20），例如“数学”、“生物学”、“艺术”
- 每个科目有课程（至少一门），例如'math-1'、'math-2'、'biology-1'、'art-1'、'art-2'、'art-3'
- 学生选择一些（固定）科目（10-12），并且对于每个科目，学生必须被分配到现有课程中的一门（如果可能）。选择“math-1”或“math-2”这门课程并不重要。
- 课程有最大允许学生人数（20-34）
- 每门课程都在一个固定的块中（= 时隙 1 到 13）
- 不得将学生分配到同一块中的课程
我现在描述我到目前为止所做的事情。
(1) 忽略 course-student-limit
我能够用匈牙利算法/二分匹配解决这个问题。每个学生可以通过如下建模来单独计算：
- 左节点代表科目“数学”、“生物学”、“艺术”（学生的）
- 右节点代表块'1'，'2'，....'13'
- 为从“主题”到“块”的每门课程插入一条边
这样，学生被分配到每个科目的课程，而不参加同一块中的课程。但是 course-limits 被忽略了。
(2) 忽略学生选择的科目
我能够用最大流量算法解决这个问题。为每个学生建模以下内容：
- 第 1 层：从源到每个学生，流量为 13
- 第 2 层：从每个学生到他/她的个人区块，流量为 1
- 第 3 层：从每个学生块到该块中的每个课程，流程为 1
- 第 4 层：从每门课程到具有“最大学生限制”的接收器
这样，学生可以选择任意课程并且课程限制已满。但他/她可能不走运，被分配到'math-1'、'math-2'和'math-3'，忽略了'生物学'和'艺术'科目。
(3) 贪婪的匈牙利语
我的另一个想法是一次将一个学生与匈牙利算法匹配并调整权重，以便首选“更多空课程”。例如，可以建模：
- 左节点是学生的主题
- 右节点是块
- 为每门课程插入一条从主题到课程块的边，权重 = 空闲座位数
然后计算最大权重匹配。
我真的很感激任何建议/帮助。
谢谢！