(我已经为以下内容编写了一个蛮力解决方案,但我想知道是否有更优雅的路径。)
我高中的学生有 8 门选修课。他们选择了第一、第二、第三和第四个选择。由于将有两个选修课,每个人都可以参加他们选择的两个选修课。
然而,尚未确定哪些选修课将安排在这两个期间中的哪一个期间。调度问题是,在了解偏好的情况下,优化这两天的选修课分配,以便尽可能多的学生能够参加他们喜欢的两门选修课。
比如我报了IT和Art,如果时间不同,我只能同时报。当然,您可能已经注册了艺术和法语,而其他人则注册了法语和 IT。
由于只有两个时段,不可能每个人的选择都在不同的时段。我们如何才能找到选修课的最佳分配日期,让尽可能多的人获得他们的两个最佳选择?
我的蛮力解决方案是创建所有可能分配的列表(使用组合包)并测试每个分配。这很好用,因为数据集很小,但肯定有一个更优雅的图论或矩阵解决方案——并且不会与 n 成比例地增加资源! (n 是提供的课程数量)!
无需测试两个插槽中所有可能的课程组合。您只需要存在于学生选择中的测试组合。每个学生选择 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