简介基于贪心算法的宿舍分配系统是一份完整的Vue.js前端源码项目面向需要完成课程设计、毕业设计或算法实践的高校学生和开发者通过贪心策略实现宿舍资源与学生需求的合理匹配。资源包共包含19个文件以4个Vue组件、7个JavaScript逻辑脚本和3个JSON配置文件为主体另有页面入口、图标与README说明文档压缩包整体约115KB轻量且结构清晰。项目遵循Vue标准目录组织涵盖components、router、views、store等模块方便快速理解单页应用的搭建思路。已有280人学习读者既能借鉴前端交互与状态管理的实现方式又能掌握贪心算法在分配问题中的具体编码流程适合作为算法结合前端开发的入门范例。1. 贪心算法做宿舍分配先把“谁优先”定明白再谈公平宿舍分配在高校、园区、实习基地里年年都要做最常见的做法是让辅导员拿Excel手工拖或者按报名顺序先到先得。这两条路都谈不上“算法”一旦涉及作息习惯、是否吸烟、院系隔离、床位朝向这些偏好手工方案就变成了一场靠人情和运气维持的博弈。贪心算法在这里的真正价值不是找到数学意义上的全局最优而是在可解释、可回溯的前提下用极低的计算成本产出一个局部最优且大概率够用的分配结果。它的核心动作只有三个把学生按优先级排序依次选择当前最佳宿舍选完之后不反悔。理解了这个“不反悔”也就理解了贪心算法在宿舍分配里的优点和代价。2. 宿舍分配的贪心建模先定义容量、偏好和优先级再谈算法2.1 把宿舍分配问题抽象成三个集合要做贪心第一步是把业务语言翻译成数据结构。宿舍分配至少涉及三类数据学生集合 S宿舍集合 D以及宿舍的床位容量 C(d)。每个学生 s 需要给出一个偏好列表 P(s)P(s) 是一个按志愿从高到低排列的宿舍编号序列例如[3, 1, 2]表示第一志愿住 3 号楼第二志愿住 1 号楼第三志愿住 2 号楼。容量 C(d) 不是单个数字而是一个多维向量。常见维度包括总床位数按性别区分的床位数按年级预留的床位数特殊床位如无障碍床位数量在建模阶段一个常见错误是把“宿舍还剩多少床”当成一个全局数字。实际上贪心分配过程中需要随时查询的是“某个宿舍在我这类学生身上还剩多少配额”而不是“这个宿舍有没有空床”。因此建议把容量定义成一个二维表capacity[宿舍][类别]类别可以是一组枚举值例如male_graduate、female_undergraduate。这样在贪心选择时判断条件就从“宿舍有没有空位”细化为“宿舍在满足我所属类别约束的前提下有没有空位”后续扩展校区、楼栋、楼层限流时也只是多一列的问题。2.2 优先级排序贪心算法的贪心选择性质贪心算法要求每一步都做出当前看起来最好的选择并且这个选择不会因为后续步骤而调整。在宿舍分配场景里“当前最好”的定义取决于排序键。我一般会用组合排序键而不是单一字段排序键 (年级权重, 提交时间, 特殊需求标志, 报名序号)其中年级权重的设定要能体现刚性需求差异例如博士生和交换生优先于新生新生优先于老生。特殊需求标志覆盖身体障碍、医疗隔离等必须满足的条件这类标志不能参与权重排序而应该作为硬过滤条件前置处理。在排序确定之后算法按顺序为每个学生分配宿舍。贪心选择的含义是该学生选择自己偏好列表中尚未满员的最高志愿宿舍选择后立即占用一个床位后续任何学生不允许把已分配的床位挤掉。这正是贪心算法中“贪心选择性质”在分配问题上的体现——局部最优选择一旦做出就不参与后续的重新决策。一个经典的问题是如果两个学生优先级相邻高优先级学生选了第二志愿而低优先级学生选了第一志愿看起来“不公平”。这是排序键设计不够细导致的。解决办法是在排序键里加入“第一志愿已被占满的学生优先”这一项即当学生 A 的第一志愿宿舍已满时A 在下一轮分配中比尚未分配且第一志愿还有空位的学生更优先。这仍然是一次遍历完成的贪心只是每轮循环都重新计算未分配学生的动态优先级。2.3 为什么贪心在这个场景是合理选择宿舍分配本质上是一个带容量限制的多对一匹配问题要找到最优解等价于求解一个整数规划问题规模稍大就变成 NP-hard。精确算法在 500 人以上的宿舍分配场景几乎不可用而贪心算法把复杂度从指数级降到了 O(n × m)其中 n 是学生数m 是宿舍数。贪心解虽然在理论上不能保证全局最优但其误差上界在“学生偏好列表较短、宿舍容量较大”时是可接受的。这里的直觉是宿舍数量通常只有几十个学生偏好列表长度通常 3 到 5 个志愿较高的宿舍容量给后续学生留下了缓冲空间。除非出现“热门宿舍容量过小 学生偏好高度集中”这两个条件同时成立否则贪心解与最优解的满意度差距不会拉开。为了能在分配结束后量化这个差距建议在建模阶段同时定义两个目标函数。第一个是分配率即成功分配到宿舍的学生数占总数的比例。第二个是偏好满意度采用加权命中位置倒数的方式学生 s 的满意度 score(s) 1 / rank(s)其中 rank(s) 是最终分配到的宿舍在其偏好列表中的位置如果分配到了偏好列表之外的保底宿舍score(s) 0。最终报告里同时输出两个指标任何一个指标异常都能快速反推问题是出在排序还是容量。3. 用 Python 写一个可运行的贪心宿舍分配器3.1 数据结构设计与输入格式先定义 Student 和 Dormitory 两个数据类。Student 中保存学生的偏好列表和属性标签Dormitory 中维护一个列表记录每个宿舍的剩余容量。为了保证后续调试方便每个学生分配成功后分配结果写回一个 result 字典。from dataclasses import dataclass, field dataclass class Student: sid: str gender: str # male / female grade: int # 年级数字越大越优先 prefer: list # 志愿宿舍 ID按优先级降序 assigned_dorm: str None dataclass class Dormitory: did: str capacity: int remaining: int field(initFalse) def __post_init__(self): self.remaining self.capacity数据读入之后按 2.2 节的排序键构建优先队列。这里不需要引入 heap直接用sorted()按元组排序即可元组的每一项对应一个维度。需要强调的是排序键的第一项如果是“逆序”Python 的sorted不支持按某一列方向混排因此需要把需要逆序的字段取负值或者分层排序。def build_order(students): # 排序维度年级逆、特殊需求逆、报名序号正 return sorted(students, keylambda s: (-s.grade, -has_special_need(s), s.sid))has_special_need可以是查询一个额外字段例如Student.need_accessibility布尔值。这样排序不需要侵入原有类定义。3.2 核心分配循环主循环的逻辑是用两个while嵌套实现的。外层遍历排序后的学生内层遍历该学生的偏好列表一旦找到剩余容量大于 0 的宿舍就落座并跳出内层循环。如果整个偏好列表都遍历完仍没找到空位则进入保底分配逻辑。def greedy_assign(students, dorms): result {} for stu in students: for did in stu.prefer: if dorms[did].remaining 0: stu.assigned_dorm did dorms[did].remaining - 1 result[stu.sid] did break else: # 所有志愿均满触发保底池 for did in dorms: if dorms[did].remaining 0: stu.assigned_dorm did dorms[did].remaining - 1 result[stu.sid] did break return result这段代码里有几个细节值得展开。内层for使用for...else结构else分支只在循环自然结束时触发也就是说该学生的所有志愿宿舍都满了才进入保底分配。第二个细节是保底分配遍历顺序固定为dorms的插入顺序这会带来一个隐蔽问题每次保底都优先塞进第一个有剩余容量的宿舍导致保底学生高度集中在某个楼栋。更稳妥的做法是把宿舍按剩余容量从大到小排序尽量避免把保底压力聚集在一栋楼。第三个细节是break的粒度。这里的break只跳出内层for外层排序后的for stu in students继续处理下一个学生。贪心算法的“不回溯”体现在一旦assigned_dorm被赋值该学生就不参与后续任何调整。3.3 输出分析与参数调节运行结束后需要输出分配报告。以 500 名学生、20 个宿舍为例输出指标包括总分配率、第一志愿命中率、前二志愿累计命中率、保底人数。from collections import Counter def report(result, students): first_hit sum(1 for s in students if result[s.sid] s.prefer[0]) second_hit sum(1 for s in students if len(s.prefer) 1 and result[s.sid] s.prefer[1]) fallback [s.sid for s in students if result[s.sid] not in s.prefer] print(分配率: %.2f%% % (len(result) / len(students) * 100)) print(第一志愿命中: %d, 第二志愿命中: %d % (first_hit, second_hit)) print(保底人数: %d % len(fallback))参数调节集中在两个地方一是排序键里每一项的权重二是每个宿舍的容量设定。容量设定不要直接填“实际床位数”建议留出 3% 到 5% 的余量给后续补录、调宿和临时变更。这些余量在分配完成后再人工锁定避免贪心分配阶段就把所有床位打满导致行政上没有任何腾挪空间。注意余量不是越小越好。如果余量设为 0一旦出现学生退宿或延期入学整个分配结果就要重跑。留 3% 余量的成本只是多几间空床收益是分配结果可以稳定使用一整个学期。4. 硬约束过滤与偏好冲突处理写清楚规则才能避免全盘重来4.1 硬约束与软偏好分开处理贪心算法只能对“排序”做优化无法对“合法性”做判断。像性别隔离、传染病隔离、行动障碍学生的一层宿舍这类硬约束必须在进入贪心循环之前用过滤条件处理而不是塞进权重里。硬约束处理的标准姿势是掩码过滤给每个学生预计算一个allowed_mask即该学生可选的宿舍 ID 集合然后遍历偏好列表时先检查did in allowed_mask不在则直接跳过。约束类型处理方式代码位置性别隔离掩码过滤不可跨性别宿舍构建 allowed_mask 时年级混合限制掩码过滤不允许该年级入住的宿舍构建 allowed_mask 时医疗/行动需求掩码过滤无障碍设施不满足的宿舍构建 allowed_mask 时作息习惯偏好软权重加入排序键排序键构建时是否吸烟软权重优先匹配同标签宿舍排序键构建时硬约束一旦在排序时漏掉后面不管算法跑得多完美结果都不能直接落地。常见的坑是在读数据时没有把“该宿舍是否允许某类学生入住”的表和宿舍表做关联导致掩码不生效。4.2 把软偏好因子的权重写成显式配置软偏好不应该硬编码在代码里。把每个因子对应的排序权重放在一个配置字典中这样调整策略时不需要改代码只改配置。priority_weights { grade: 100, smoke_pair: 10, sleep_time_pair: 5, special: 1000, }排序键的构造函数把学生属性映射到这些权重上。比如smoke_pair的值等于该学生与当前候选宿舍已有学生标签的匹配程度匹配则加 10不匹配不加。这里有一个关键点贪心算法的排序键是预计算好的当宿舍已有学生构成动态变化时预排序无法感知这种变化。所以“同宿舍匹配度”这类依赖上下文的信息不能放在排序键里而要放在内层选宿舍的打分环节。具体做法是在内层遍历偏好列表时不直接取第一个有剩余容量的宿舍而是取剩余容量大于 0 且“上下文匹配分”最高的宿舍。匹配分函数里可以读取该宿舍当前已有学生的属性分布。例如一个不吸烟学生看到两个志愿宿舍都有空位一个宿舍 4 人里 3 人吸烟另一个宿舍 4 人都不吸烟匹配分机制会让后者胜出。4.3 无解时的降级与失败回退即便硬约束配置正确依然可能出现某个学生无法分配给任何宿舍的情形常见原因包括宿舍楼栋剩余床位都是男生床位而当前学生是女生或者该学生的所有可选宿舍都满了。此时贪心算法的失败处理是整条链路的最后一道防线。保底策略按强度递增排列第一级是扩宿舍容量把 3% 的预留余量释放出来第二级是放宽志愿列表让学生在备选宿舍中做一次二次选择第三级是跨类型调剂比如原定两人间调剂到四人间。建议在代码里把三级策略串成顺序尝试而不是一开始就允许跨类型调剂。跨类型调剂会直接破坏分配报告里“宿舍类型符合预期”这一指标降低整体数据的可信度。4.4 验证排序变更对结果的影响运营一个宿舍分配系统最难判断的是“改了排序规则之后结果变好了还是变坏了”。因为两次分配的输入相同输出不同但两次输出都是合法的。评价标准只能回到 2.3 节定义的两个指标分配率和偏好满意度。做一个简单的对比实验把排序键中的年级权重从 100 改成 50其余不变跑两次记录第一志愿命中率和保底人数。如果第一志愿命中率下降但保底人数也下降说明原来的年级权重过度压缩了低年级学生的选择空间。如果两项指标都上升说明新权重在优先级和公平性之间取得了更好的平衡。这种对比实验不需要做成一个系统只要把分配函数固定输入权重作为参数传入每次跑完把结果序列化成 JSON用diff对比即可。5. 用双向交换修正贪心解的尾部损失一个可落地的后处理技巧5.1 找出损失集中在哪一批学生贪心分配完成后把学生的最终宿舍与其第一志愿比对。绝大多数失败案例集中在排序键尾部的学生身上也就是低年级、晚提交、无特殊需求的学生。要量化“尾部损失”写一个小函数统计每个排序分位段的保底人数分布。分位段按排序索引切成 10 段输出每一段的保底学生占比。如果尾部两段的占比明显高于前几段说明贪心分配在尾部牺牲过大需要后处理。5.2 单步交换只接受双向收益的移动后处理采用最简单的局部搜索遍历所有未命中第一志愿的学生尝试把该学生从当前宿舍移动到另一个宿舍同时把被挤出的学生移动到该学生原来的宿舍。只有当两边的满意度之和高于原分配时才提交这个交换。def try_exchange(stu, old_dorm, new_dorm, dorm_students): for other in dorm_students[new_dorm]: cur_score score(stu, old_dorm) score(other, new_dorm) new_score score(stu, new_dorm) score(other, old_dorm) if new_score cur_score and dorm_students[old_dorm].is_allowed(other): apply_exchange(stu, other, old_dorm, new_dorm) return True return Falsescore函数使用与 2.3 节相同的满意度定义。apply_exchange负责交换两个学生的宿舍 ID 并更新dorm_students和宿舍剩余容量。这个过程里最容易出错的点是把dorm_students[old_dorm].is_allowed(other)漏掉导致交换后出现硬约束违规。5.3 迭代上限与停止条件一轮完整的交换需要扫描每个未命中第一志愿的学生复杂度大约是 O(k × n)k 是每个宿舍的平均人数。通常 3 到 5 轮就能收敛。在每轮开始时记录一个improved标志整轮结束若没有任何成功交换则停止。对比贪心分配和后处理输出的报告通常能看到第一志愿命中率提升 5 到 10 个百分点保底人数下降一半以上。这一步的成本极低代码量不超过 50 行运行时间在几千人规模下也只有几秒适合作为贪心算法的标配后处理。提示如果交换逻辑在真实数据上完全不触发优先检查 score 函数的单调性。例如 score 返回 1/rankrank 取值范围 1 到 5交换前后分数差异可能过小导致系统认为没有改进空间。把分数放大为100 / rank可以加速收敛。本文还有配套的精品资源点击获取