我正在寻找一种算法,将n名学生分配到m门课程中,其中每个学生定义三个优先级,每门课程都有最小和最大计数以及介于最小和最大之间的最佳计数。
到目前为止,我所拥有的是:
- 一系列课程
- 一系列学生拥有适合他们三个优先事项的属性
1)随机课程;随机播放学生
2)循环学生并暂时将他们分配到他们的首选。
如果他们的第一选择是满的,比如 10 名学生,我们需要确定 11 名学生中的哪一个要放弃。 由于我们没有课程的学生优先级来找到最弱的学生,因此我们希望找到一个优先级为 2 且有空位的学生
这可以针对优先级 2 和 3 重做,但最终它并不总是得到最好的结果。
最接近的类似问题可能是稳定婚姻问题和医院/居民匹配问题。
您可能正在寻找最佳解决方案,这意味着,给定分配,没有学生和课程都喜欢的其他作业(学生=>课程)。
这个问题看起来与广义赋值问题非常相似,这是一个NP-hard优化问题。
如果创建变量 Xij,其中 Xij = 1 如果学生 i 被分配到课程 j,则可以将约束写为线性等式和不等式: 0 <= Xij <= 1,SUM_j Xij = 1 对于所有 i - 每个学生只分配到一门课程,最小 <= SUM_i Xij <= 最大 - 每门课程都有最小和最大学生人数。学生幸福感的总和是 Xij Pij SUM_ij,其中 Pij 可能是 3、2、1 或 0,具体取决于课程 j 是学生 i 的 1、2、3 还是其他选择。
然后,您可以使用线性规划来最大限度地提高学生的幸福感。如果您遵循 https://en.wikipedia.org/wiki/Integer_programming#Using_total_unimodularity 并 https://en.wikipedia.org/wiki/Unimodular_matrix#Common_totally_unimodular_matrices 我认为您可以假设生成的解决方案将具有 Xij 的整数值,因此必须是 0 或 1。
为了尝试找到每门课程接近其最佳大小的解决方案,我建议您还尝试找到减少每门课程的最大值和增加最小值的解决方案,以使它们更接近最佳大小。例如,您可以在津贴 s 上进行二进制切碎以找到有解决方案的最小 s,并且为每门课程选择的最小值和最大值都不再是该课程最佳规模的学生。