基于能力与偏好的师生班级分配算法需求问询

核心约束梳理 #

先明确所有必须满足的规则，避免后续逻辑冲突：

• 每名教师最终仅教授1门科目，且必须是其胜任列表中的科目
• 学生优先分配第一志愿科目，其次为第二志愿
• 已开设的所有科目，班级规模需保持一致（允许±1的误差，保证总人数匹配）
• 每门科目的班级数量，不得超过能胜任该科目的教师总数

分步实现流程 #

1. 基础数据统计 #

先把原始数据转化为可计算的统计值：

• 学生志愿统计：统计每个科目的第一志愿总人数（记为P1_k）、第二志愿总人数（记为P2_k），k为科目编号
• 教师胜任统计：统计每个科目对应的可用教师列表及人数（记为T_k，即能教科目k的教师总数）

2. 确定各科目班级数量 #

目标是让所有科目班级规模统一，设目标班级规模为S，步骤如下：

• 初始估算S：先取S = 整数部分(n / 所有科目T_k的总和)，保证总班级数不超过教师总量
• 迭代调整班级数：
  对每个科目k：
  • 最小班级数：ceil(P1_k / S)（必须满足所有第一志愿学生的基本容量）
  • 最大班级数：min(ceil((P1_k + P2_k)/S), T_k)（受限于教师数量和志愿总需求）
  • 若最小班级数 > 最大班级数，说明该科目教师不足以覆盖第一志愿，需缩小S（比如S减1），重新计算，直到所有科目满足最小班级数 ≤ 最大班级数
• 最终确定每个科目的班级数C_k：优先取满足第一志愿的最小班级数，若有剩余教师且能容纳更多第二志愿学生，可适当增加（但需保证所有科目班级规模一致）

3. 教师分配 #

• 对每个科目k，从其可用教师列表中随机选取C_k名教师（若教师有自主授课偏好，可给偏好科目加权，按权重排序优先分配）
• 给选中的教师标记唯一授课科目，确保一名教师只被分配一次

4. 学生分配到班级 #

• 第一志愿优先分配：
  对每个科目k，将第一志愿为k的学生随机分配到C_k个班级中，每次把学生加到当前人数最少的班级，保证同科目班级人数差≤1
• 第二志愿补位：
  收集未被第一志愿分配的学生，按第二志愿科目分组
  对每个科目k，计算班级剩余容量（C_k*S - 第一志愿已分配人数），将第二志愿为k的学生填充到剩余位置，同样保持班级人数平衡
• 无志愿兜底：
  若仍有未分配学生，将其分配到还有剩余容量的班级中，优先选择人数最少的班级，尽量维持整体规模一致

优化细节 #

• 班级规模平衡：分配学生时始终采用「填最少人数班级」的逻辑，确保同科目班级人数差异不超过1
• 志愿满足率优化：若第一志愿满足率过低，可在教师充足的前提下，增加热门科目的班级数，或调整S值（比如减小S，增加总班级数）
• 教师意愿优先：如果有教师的授课偏好数据，可在分配时加入权重，比如给教师偏好的科目加1分，排序后优先分配到高分科目

内容的提问来源于stack exchange，提问作者Emmett Bicker