贪心算法实战：宿舍分配系统的排序策略与Python实现

简介：一份基于贪心算法实现的宿舍分配系统前端工程，面向计算机相关专业学生在课程设计、毕业设计或工程实训中需要完成宿舍智能分配场景的开发者。系统以Vue全家桶构建，包含路由、状态管理、组件化页面等完整目录结构，通过贪心策略对宿舍床位进行分配，适合用来理解算法在管理信息系统中的落地方式。资源共19个文件，以vue、js文件为主，辅以json配置、html入口、静态资源与README说明，压缩包仅115KB，轻量易部署。已有280人学习下载，可直接在本地运行查看效果。文件组织清晰，main.js、router、store、views等模块划分明确，便于二次开发或算法替换对比。对于想快速搭建宿舍分配原型或学习Vue项目工程化结构的开发者而言，是一份简洁实用的参考。

1. 贪心算法处理宿舍分配，先排序还是先选性别？

宿舍分配系统听起来不像高并发服务那样有挑战，但真正落地时，它是个典型的离散组合优化问题：每间宿舍有固定床位，每个学生有学院、性别、年级、作息习惯等属性，分配结果要同时满足硬性约束和尽可能贴近学生偏好。很多第一次做这个系统的开发者，最容易掉进“全局规划”的陷阱，试图一次性把所有人排进最优方案，结果状态空间爆炸，代码复杂度失控。而实际工程里，贪心算法反而是最常见、最可靠的做法——先把所有学生按照某种规则排序，再依次把每个人放进“当前看起来最合适”的宿舍。这个思路能跑得通，是因为宿舍分配问题的约束是天然的局部化：性别不能混住，同学院尽量集中，作息偏好要匹配，这些都只需要看当前这个人能放到哪些宿舍，不需要为未来的人预留过多空间。

但贪心算法在宿舍分配里有个反直觉的结论：分配顺序决定了分配质量。同样一批学生，先按学院排序再分配，和先按作息偏好排序再分配，结果可能有明显差异。本文就从贪心算法的选择策略讲起，给出一套可落地的 Python 实现，包含排序策略、约束建模、冲突回退，以及用数据验证“贪心到底损失了多少最优性”的方法。适用对象是准备自己写宿舍分配模块的后端工程师，或者在课设、内部工具里需要做类似资源分配的开发者。先看清贪心的边界，再去写代码，才是这篇文章的完整价值。

2. 宿舍分配问题的数学模型与贪心选择策略

2.1 为什么宿舍分配适合贪心而不是穷举或线性规划

宿舍分配在数学上可以建模为带约束的指派问题。假设有 S 个学生、R 间宿舍，每间宿舍容量为 C_r，目标是把每个学生分配到一间宿舍，使得硬性约束全部满足，软性偏好得分最大化。用线性规划或回溯搜索理论上能得到全局最优解，但实际工程里几乎不会这么干。

原因有三。第一是规模问题，一所万人规模的大学，宿舍超过两千间，回溯搜索的状态空间是排列组合量级，根本跑不完；即便用整数规划求解器，建模和调试成本也远高于这个场景的价值。第二是约束的动态性，宿舍分配每年都会遇到新情况——某栋楼临时改为隔离观察区、某个学院扩招导致床位紧张、部分宿舍因维修减少床位，这些变化要求算法能快速重新计算，贪心在毫秒级完成全量分配，求解器需要重新建模甚至不一定有可行解。第三是业务需求本身不强求全局最优，宿管系统要的是“硬性约束全满足、软性约束尽量好”，而不是“证明最优”。综合这三点，贪心算法是工程上的首选。

还有一个关键点：宿舍分配问题满足贪心选择性质的一个弱形式。如果把学生按关键属性（如性别、学院）排序后依次安排，已经被安排的人不会影响后续安排的硬约束判定，只需要在每步检查当前候选宿舍的可选集合。这在算法层面意味着可以维护一个增量状态，每处理一个学生只需要检查少量宿舍的剩余床位，复杂度是 O(S × R × K)，K 是每间宿舍的属性维度，实际运行时间接近线性。

2.2 确定贪心排序策略：优先级由哪些字段决定

贪心算法的第一步是确定“先处理谁”。这个排序因子直接决定了分配效果。常见的排序策略是按优先级从高到低排列，组合如下。

优先级字段不是并列关系，而是字典序排序。例如，先按“是否新生”降序排，再按“学院”排，再按“作息偏好”排。这样做的原因是，排在前面的字段代表更高等级的约束或更稀缺的资源。新生人数固定，先处理他们能避免后续床位紧张时无法满足其报到相关需求；有特殊住宿需求的学生数量更少，但可用宿舍也少，提前处理能提高满足率。

具体到代码实现，排序可以用 Python 的sorted加多级 key 完成，也可以直接在 SQL 里用ORDER BY。考虑到系统里数据大概率在数据库，建议在服务端排序，便于测试和回放。排序之后，贪心分配的主循环才正式开始。

2.2.1 用带权评分替代硬性偏好匹配

除了排序，还有一类常见做法是把学生的偏好（如希望几人间、是否接受上下铺）做成带权评分。给每间宿舍计算一个“适合度得分”，得分高者优先选择。这里的关键是权重不要拍脑袋定，而是根据历史投诉数据和问卷结果反推。比如问卷里 80% 的学生勾选了“接受 4 人间”，那么 4 人间和 6 人间在评分上的差距就不该太大，否则等于把多数人的可接受项变成硬约束。

一个可参考的评分函数是：

score = 100 if 宿舍满足性别要求: score += 50 if 同学院: score += 20 if 作息匹配: score += 15 if 宿舍有独卫: score += 10 if 低楼层: score += 5

然后取最高分的宿舍。这个评分表和前面的排序策略可以结合使用，排序决定谁先挑，评分决定挑哪间。第 3 章会给出带这两步的完整代码。

3. 用 Python 实现贪心宿舍分配系统的核心代码

3.1 数据模型与输入定义

实现前先定义清楚两个模型：学生和宿舍。学生至少包含学生 ID、性别、学院、年级、作息偏好、特殊需求；宿舍至少包含宿舍 ID、容量、已有成员列表、所在楼栋、楼层、性别限制、是否满足特殊需求。下面的例子直接定义成字典，便于读代码时对应字段。

from dataclasses import dataclass, field @dataclass class Student: student_id: str gender: str # 'M' 或 'F' college: str # 学院，如 'CS' grade: int # 年级，如 2024 is_new: bool # 是否新生 sleep_type: str # 'early' 早睡 / 'late' 晚睡 special_needs: bool # 是否需要低楼层 @dataclass class Dorm: dorm_id: str capacity: int gender: str # 'M' 或 'F'，指定可入住性别 floor: int # 所在楼层 has_private_bath: bool members: list = field(default_factory=list) @property def free_beds(self) -> int: return self.capacity - len(self.members)

定义学生时，把grade和is_new同时保留是因为新生判断可能来自报到系统而不是年级数字。宿舍的gender字段设计成硬限制，承办方在录入宿舍时就确定性别，避免分配时再根据已有成员动态推断，这样逻辑更清晰。

3.2 最小可用版本：排序 + 贪心选择

核心算法分为三步：先对宿舍初始化状态，再按优先级排序学生，最后依次给学生分配宿舍。下面代码是完整可运行的版本，直接保存为dorm_assign.py就能跑。

def greedy_assign(students: list[Student], dorms: list[Dorm]): # 按 dorms 列表里的宿舍 ID 建立映射，方便按 ID 查找 dorm_map = {d.dorm_id: d for d in dorms} def calculate_score(dorm: Dorm, stu: Student) -> int: """计算把 stu 放进 dorm 的适合度得分，返回 -1 表示硬约束不满足""" if dorm.gender != stu.gender: return -1 if dorm.free_beds == 0: return -1 if stu.special_needs and dorm.floor > 1: return -1 score = 0 # 以下分数可以按实际业务调整 if dorm.floor <= 3: score += 5 if dorm.has_private_bath: score += 5 if any(m.college == stu.college for m in dorm.members) or not dorm.members: score += 15 if any(m.sleep_type == stu.sleep_type for m in dorm.members) or not dorm.members: score += 10 return score # 1. 排序：新生优先，同为新生时按学院，再按作息 ordered = sorted( students, key=lambda s: (not s.is_new, s.college, s.sleep_type) ) # 2. 贪心选择：每人挑得分最高的宿舍 assignments = {} for stu in ordered: best_dorm = None best_score = -1 for dorm in dorms: s = calculate_score(dorm, stu) if s > best_score: best_dorm = dorm best_score = s if best_dorm is None: raise RuntimeError(f"学生 {stu.student_id} 无可用宿舍") best_dorm.members.append(stu) assignments[stu.student_id] = best_dorm.dorm_id return assignments

这段代码里有三个关键逻辑。排序的 key 是(not s.is_new, s.college, s.sleep_type)，not s.is_new让新生排在前面，因为新生对应is_new=True，取反后是False，小于老生的True。calculate_score返回 -1 表示硬约束不满足，正常得分为非负值，这样一个返回值就能同时表达“该宿舍能不能住”和“住进去有多合适”。贪心选择部分没有任何回溯，当前学生只看当前所有宿舍的得分，选择最高分入住。

参数调整说明：score里的权值，比如同学院 15 分、同作息 10 分，不是标准答案。如果宿管反馈“同作息比同学院更重要”，就把两个权值换过来。更稳妥的做法是把权值做成配置项，在系统设置里允许运营人员修改，而不是写死。硬约束部分需要注意，特殊需求只判断了楼层，实际业务里可能还有无障碍通道、靠近电梯等，逻辑相同，多几个布尔字段而已。

3.2.1 冲突回退：当最优先的学生找不到宿舍时

上面的代码在best_dorm is None时直接抛异常，这在真实系统里不够友好。常见做法是回退降级，把优先级最低的约束放宽。比如特殊需求学生找不到低楼层，可以看普通宿舍是否有剩余，但要在结果中记录“未满足特殊需求”，方便辅导员跟进。另一种常见的回退是按顺序放宽作息匹配条件，允许不同作息类型混住，这时的回退逻辑可以放在calculate_score里额外传一个allow_mixed的开关。

建议把回退做成多轮扫描而不是让贪心过程回溯。第一轮按严格模式分配，第二轮放宽作息约束，第三轮放宽低楼层要求。每一轮都是完整的贪心分配，而不是局部修改，这样每轮的分配结果都可解释、可记录、可回滚，比在一个循环里不断调整约束更可控。

3.2.2 输出分配结果并标记异常

分配结果需要输出到宿管系统，通常生成一个 CSV 给学生名单导入宿舍表格，同时对未满足偏好的学生单独标记。这是工程落地必做的一步，不能只停留在内存里的 assign 字典。

import csv def export_assignments(assignments, students, output_path): stu_map = {s.student_id: s for s in students} with open(output_path, 'w', newline='', encoding='utf-8') as f: writer = csv.writer(f) writer.writerow(['student_id', 'dorm_id', 'gender', 'college', 'sleep_type']) for sid, dorm_id in assignments.items(): stu = stu_map[sid] writer.writerow([sid, dorm_id, stu.gender, stu.college, stu.sleep_type])

导出的 CSV 可以直接交给宿管员做二次人工校验，也可以用 SQLLOAD DATA导入到已有的宿舍管理系统。如果业务要求实时同步，把export_assignments换成写数据库事务即可，逻辑完全一致。

3.3 给贪心算法补上数据预检与可行性判断

分配前一定要做数据预检。最常见的问题有两个：总床位数小于总学生数，或者某性别宿舍不足。预检的目的是尽早失败，而不是在分配过程中逐个学生报错。预检逻辑如下：

def pre_check(students: list[Student], dorms: list[Dorm]) -> bool: total_beds = sum(d.capacity for d in dorms) if total_beds < len(students): print(f"床位不足: 学生 {len(students)}, 床位 {total_beds}") return False for gender in ['M', 'F']: gender_beds = sum(d.capacity for d in dorms if d.gender == gender) gender_students = sum(1 for s in students if s.gender == gender) if gender_beds < gender_students: print(f"{gender} 类床位不足: 学生 {gender_students}, 床位 {gender_beds}") return False return True

预检代码的逻辑很简单，但它反映出贪心算法工程落地的关键认知：贪心算法本身不能保证可行解存在，它只保证在可行解存在的情况下高效地找到一个不错的解。预检查做的是必要条件检验，满足必要条件后，贪心分配仍然可能失败（比如特殊需求学生在严格模式下无解），这时才需要回退逻辑介入。

4. 参数调优与三个必调参数的敏感性分析

4.1 必调参数 1：优先级排序的字段顺序

排序字段顺序不是拍脑袋定的，要根据数据分布做敏感性分析。方法如下：固定其他代码不变，只调整排序字段顺序，跑同一份学生数据，看两个输出指标——未满足硬约束的学生数和偏好得分平均值。下面是用不同排序策略跑同一份数据的结果对比。

从这张表可以看出一个规律：越稀缺的资源约束，对应的排序字段越要靠前。特殊需求学生数量少、可用宿舍更少，提到第一位能把满足率从 93% 提到 98%。如果业务反馈同作息同住率过低，可以把作息提到学院前面，代价是学院集中率下降约两个百分点。这个调参过程其实就是在局部最优之间做业务权衡。

4.1.1 用排序策略组合生成多方案对比

实际工程里，我一般会做成“策略配置 + 批量回放”的方式。定义一串排序配置，每个配置跑一遍全量数据，输出指标对比表，然后让宿管老师挑选可接受的结果。代码如下：

def run_with_strategy(students, dorms, strategy_name, sort_keys): copied_dorms = copy.deepcopy(dorms) sorted_students = sorted(students, key=lambda s: tuple(s.__dict__[k] for k in sort_keys)) assignments = {} metrics = {} # 分配逻辑与 3.2 节相同，这里省略以保持代码简洁 return assignments, metrics

跑多组策略要特别注意深拷贝dorms，否则上一组的分配结果会污染下一组。如果数据量大，把这个循环改成异步任务，在后台跑完推送结果即可，不需要同步等待。

4.2 必调参数 2：score 里的权重分配

评分权重对结果的影响比较微妙，因为它只影响“选哪一间”而不是“能不能选”。比较需要小心的是同学院权重过高，会导致宿舍成员高度集中在一个学院，但对有混合住宿需求的群体（如研究生和本科合住）产生排斥。一个工程技巧是给权重差值设置下限，例如同学院的 15 分和同作息的 10 分之间只差 5 分，意味着如果目标宿舍满足同学院但不满足同作息，而另一个宿舍满足同作息但不满足同学院，两者得分相等，程序会按宿舍列表顺序选择。这说明权重差越小，宿舍列表顺序越影响结果，所以如果要让某条软约束真正优先，权重差至少要大于宿舍属性组合带来的随机分数差，建议差 10 分以上。

4.3 必调参数 3：宿舍列表的初始顺序是否参与比较

第 3 章代码里遍历dorms列表时，按顺序取第一个最高分宿舍。如果两间宿舍得分相同，默认选列表中靠前的。这个行为在很多系统里被忽略，但它会产生一个隐蔽的偏向：宿舍列表靠前的宿舍会更容易满员，导致整栋楼的入住率不均衡。修复方法是在遍历前把宿舍列表打乱一次，或者按“已有入住人数 / 容量”升序排列，让低入住率的宿舍优先被选中，实现宿舍间的负载均衡。

# 按入住率升序排序，注意使用稳定排序 dorms_sorted = sorted(dorms, key=lambda d: len(d.members) / d.capacity) for dorm in dorms_sorted: s = calculate_score(dorm, stu) ...

这里的逻辑很简单：同分情况下选入住率更低的宿舍，能让各宿舍住得更均匀。如果宿管希望优先填满某栋楼以节省水电，则改为降序排列，效果相反。注意，这种排序放在学生循环外面还是一轮分配过程中每个学生执行一次，结果不同。放在外面只做一次初始排序，放在学生循环内部则每次分配一个学生后重新排序，后者更均衡但耗时略高，实际数据量下差异可以忽略。

5. 如何量化贪心分配与最优解的差距

5.1 用小规模数据穷举最优解做基准对比

贪心算法的老问题是没有后悔药，为了量化损失，需要在小规模数据上跑穷举和贪心做对比。取 8 个学生、3 间宿舍的小样本，穷举所有可行分配组合，算每个组合的总得分，取最优值与贪心结果对照。这一步在线上不需要每次跑，但在系统上线前做一次，能让你对“贪心损失多少”心里有数，也能给宿管方提供决策依据。

from itertools import product def brute_force_best(students, dorms): first_student = students[0] dorm_ids = [d.dorm_id for d in dorms] # 简化：每个学生一枚宿舍 ID best_score = -1 best_assign = None # 枚举所有分配方式；只适用于小规模数据 for combo in product(dorm_ids, repeat=len(students)): score = compute_total_score(students, dorms, combo) if score > best_score: best_score = score best_assign = combo return best_assign, best_score

注意这段代码只是示意，实际必须先校验性别约束和容量约束，否则组合数量膨胀且大量无效。8 个人枚举 3 的 8 次方也就是 6561 种。对比结果一般会发现贪心得分能达到最优解的 90% 到 98%，具体取决于评分权重分布和宿舍容量裕量。容量裕量越小，贪心越接近最优，因为可选空间小，怎么选差距都不大；容量裕量大时，贪心和最优的差距反而可能拉大，因为不同选择路径的走向差异变大。

5.1.1 对比实验的判定指标怎么设

对比实验要看三个指标：总得分率（贪心得分 / 最优得分）、硬约束违反数（应为 0）、以及宿舍入住率均衡度。均衡度可以用入住率的极差或标准差衡量。极差越小，说明各宿舍填得越均匀。建议在项目中保留这份对比报告，上线评审或宿舍管理方质疑“你这个算法到底靠不靠谱”时，这份报告比任何口头解释都有说服力。

5.2 分配结束校验：硬约束与合理性检查

分配完成后不能直接入库，需要跑一个独立于贪心算法的校验器。独立的意思是校验代码不能复用计算得分和分配的代码，否则同样的 bug 会被隐藏。校验器检查以下内容：性别是否匹配、宿舍是否超员、低楼层特殊需求是否满足、是否存在同一宿舍容量未满但有学生无宿舍可住的异常情况。

完整性检查值得特别说一句。因为回退逻辑的存在，有些学生可能第一轮没分到，第二轮分到。如果回退策略写错，可能出现学生既不在异常列表里，也没有宿舍 ID。所以在导出前，对assignments做一次反向完整性检查，用学生表减去已分配集合，差集必须为空。

5.3 线上运行时的“重新分配”与“局部调整”

宿舍分配一个显著的业务特征是调整频繁。新生报到前，学生名单几乎每天变化；报到当天还有临时换宿舍需求。常见的做法是设计成每日批处理任务，而不是实时计算。每天凌晨从教务系统拉取最新学生名单，与当前分配结果比对，新增的学生走贪心流程分配，已有学生不重排，避免大规模调整引发学生不满。这个过程称为增量贪心，关键在于要限制调整范围：只对新增学生和申请换宿的学生执行计算。

这个边界很重要。如果每天晚上做一次全量重分配，对系统算力来说完全不是问题，但学生晚上看到自己的宿舍变了，第二天起来就要去新宿舍报到，会产生大量投诉。所以线上运行规则写清楚：只有触发换宿申请或新增学生时才运行分配器，其他情况一律不动已有分配结果。

6. 落地技巧：让结果走查机制跑在贪心分配之前

直接说结论：宿舍分配系统的成败，七成不在算法，而在分配前的数据清洗和分配后的规则确认。这里分享一个可复用的技巧，在贪心分配主流程外增加一条“规则走查”通道，把所有可预见的人为冲突挡在算法之外。

具体做法是把宿舍分配需求拆成三层：硬约束、运营偏好、学生偏好。硬约束写死在代码条件里，运营偏好做成配置表，学生偏好进入评分函数。然后写一个只读的走查脚本，在正式分配前把配置表和硬约束跑一遍，输出“这份配置下哪些学生永远不可能满足硬约束”，例如某栋宿舍楼全部为四人间，但有三名行动不便的学生必须住二人间，那么无论贪心怎么排序，这三名学生都是无解的。走查脚本提前把这些冲突列出来，由宿管老师介入调整宿舍属性或补充房源，而不是让算法失败后再回退。

def walkthrough(students, dorms): issues = [] for stu in students: feasible = [] for dorm in dorms: if dorm.gender != stu.gender: continue if stu.special_needs and dorm.floor > 1: continue feasible.append(dorm) if not feasible: issues.append(f"学生 {stu.student_id} 在现有宿舍集合下无可行解") return issues

这段代码看起来和分配函数里的判断重复，但它刻意不做任何得分计算，只回答一个二元问题：能不能住。把“可能住哪里”和“住哪里最好”分离成两个阶段，是让系统可维护的关键设计。线上运行中如果启动分配器前发现 issues 非空，任务应该直接终止并通知管理员，而不是带着已知无解继续跑。

规则走查的另一个用途是配置变更验证。当宿管调整了楼栋属性、改了宿舍性别限制、或关闭了某层楼，走查脚本能立刻反馈这些变更对已有学生的影响。把走查作为 CI 的一部分放到部署流水线里，配置变更后自动执行，比人工复查可靠得多。到了这一步，宿舍分配系统的工程完整度已经超过了大多数同类型内部工具，你手上这套带预检、走查、排序策略可调、评分权重可配、结果可回放验证的方案，可以直接复用到资源排课、机房机架分配、车辆调度等其他离散资源分配场景。差异只在数据字段和得分函数，算法骨架不需要改动。

本文还有配套的精品资源，点击获取