复旦大学曾试运行研究生网上选房，本科生系统自动分配的统一工作模式。由于疫情防控的常态化需求，学校毕业季和迎新季的工作计划发生调整，存在宿舍分配工作延期、学生延期毕业导致宿舍资源紧张且分散、新生招生及录取时间延后、各园区宿舍分配要求不同等特殊情况。
鉴于上述情况，学校的宿舍分配工作需要根据各园区的实际情况实施合适的分配方法，通过需求分析、自动分配算法的设计实现以及虚拟楼等概念的提出，配合宿舍管理业务部门完成特殊时期下学校宿舍的分配工作。
新生宿舍分配的现状与需求分析
复旦大学曾试运行研究生网上选房的功能模块，网上选房首先通过系统自动预分后，固定院系所在的住宿区域，然后分批次开放区域内的房间供新生选择。新生可以在“同一院系、性别、学制、培养层次”规则允许的范围内自行组团，组团时可以标注自己的兴趣爱好及作息时间。
目前宿舍分配方案的设计有以下两种：
一是网上选房，此方案的优势在于通过组团选房的功能，满足新生在允许范围内自主选择室友的个性化需求。此方案实施的问题是，若较多老生延期毕业，造成床位暂时性不足，会与网上选房的计划日期产生冲突。
二是自动分配算法，根据可配置化的规则，完成不同的自动预分及最终效果，包括三种模式：
1. 自动分配模式：完成宿舍自动划块预分后，系统自动分配新生到床位；
2. 自动预分后不分配新生的模式：完成宿舍自动划块预分但不分配新生，适用于网上选房模式；
3. 手动预分后自动分配新生的模式：园区办公室完成手动预分后，系统自动分配新生到床位。
此方案的优势在于满足了宿舍分配工作不同的需求，不足之处在于相对于网上选房模式，对新生的个性化需求关注偏少。目前仅支持通过问卷形式，将符合条件的“期望入住舍友”进行双人分配。
根据我们的调研，学校各宿舍园区对于宿舍分配的要求不尽相同，主要有以下几点：
1. 楼内学制集中，便于同一学制学生毕业离校后整栋楼宇的清扫及整修；
2. 院系、班级集中，即同一院系、性别、培养层次（博士/硕士/本科）集中住宿，便于辅导员走寝、安全卫生评比等宿舍现场管理；
3. 允许楼内院系组合，以及楼内培养层次组合；
4. 已分配宿舍的楼宇房间尽量排满；
5. 允许新生在满足上述要求的范围内填写“期望入住舍友”，实现自动双人分配。
综上所述，随着信息技术的发展，高校宿舍分配工作呈现出两个特点：一是由于每年的内外部环境的变化，宿舍分配工作的需求每年都有所不同，需要一类可以配置的动态算法以满足不断变化的需求。二是宿舍分配工作越来越关注学生的个性化需求，主要包括学生的生活习惯和性格爱好，目的是为了让学生在未来几年的学习生活中，宿舍氛围更和谐，减少宿舍矛盾发生的概率。
自动分配算法的设计实现
自动分配算法的设计主要采用了0-1背包问题的动态规划，分为以下两点设计原则：
1. 根据院系、班级集中分配的原则，将新生分组后视作将要放进背包的一件件物品，每件物品被带走或被留下，需要做出0-1选择，不能只带走某个物品的一部分或带走两次以上同一个物品。
2. 在选择是否要把一个物品放到背包中，必须把该物品放进去的子问题的解与不放该物品的子问题的解进行比较。这种方式形成的问题导致了许多重叠子问题，满足动态规划的特征。
接下来以某园区的男生宿舍分配为例，通过Excel演示自动分配算法的设计思路，其中的院系分组名称以“分组1”、“分组2”等简称替代：
首先，按照楼宇、性别、培养层次汇总统计空床位数，形成表1。
表1 不同楼宇空床位数
其次，按照院系、性别、培养层次、学制对预分学生名单进行分类汇总，统计人数，并对每个分组根据人数进行排序，形成表2。
表2 不同分组人数排序
第三，以研究生男生为例，按性别、培养层次、学制分类汇总并统计人数，结果见表3。
表3 研究生男生人数统计
第四，做完以上三步准备工作，开始宿舍分配工作。将整个园区的空床位数视作一个大瓶子，每栋楼视作一个小瓶子，遵循“先放大石头、再放小石头、最后放沙子”的原则，尽可能填满空床位，因此先分配数量最多的3年男硕士。
第五，依组依序（3年男硕士、4年男博士、5年男博士、3年男博士、4年男硕士、2年男硕士、2.5年男硕士）进行分配。以3年男硕士为例，共有444位待分配，结合0-1背包算法，给出3年男硕士的动态规划表4的部分内容。
表4 3年制男硕士的动态规划
分配说明如下：
1. 第一行的数量表示一栋楼剩余的空床位数，模拟背包的剩余空间，直至最大98；
2. 第二列的数量表示按照院系、学制、性别、培养层次分组后进行排序；
3. 从2行第3列开始的区域是从下往上、从左往右生成的，每个单元格表示该单元格对应的楼宇空床位数量下可用分组的最大分配数，“分组2”在20个空床位的楼宇下，由于“分组2”以及往下的所有分组人数都超过20个空床位，所以看到表格下方大片的“0”数据区域；
4. 由于最大空床位是98，不可能逐个计算值。根据0-1背包的状态转换方程，对每个单元格需要考察两个值，一个是f[i-1,j]，另一个是f[i-1, j-Wi]+Pi；举例对于“分组22”那行最后一列值为20，f[i-1,j]表示这个单元格下方的值，即除了“分组22”外，在20空床位楼宇下其他可用分组能分配的最大值。f[i-1, j-Wi]表示，当减去“分组22”分组人数1后，在19空床位楼宇下其他可用分组能分配的最大值。Pi指的是“分组22”的人数，即1；
5. 最后得到f[i-1,j]和f[i-1, j-Wi]+Pi后，比较得到最优解，以“分组17”所在行最后一列为例：f[i-1, j-Wi]+Pi = 11+ 9 =20，f[i-1,j] = 17，通过比较，f[i-1, j-Wi]+Pi > f[i-1,j]，所以这个单元格值为20。
第六，给出完整的动态规划表格后，因为最大空床位只有98、92、90三种，所以表格只需显示三列，以下表格表示目前这些分组可以完全填满98、92、90空床位的楼宇，一栋楼宇填满后需要剔除已分配的分组，再重复第一至第六步骤，并再次形成表5。
表5 填满最大空床位的楼宇
根据0-1背包问题算法设计第1条，且遵循“先放大石块、再放小石块、最后放沙子”的装瓶原则，分配完成后的3年男硕士的部分效果见表6。
表6 3年制男硕士部门分配结果
从上表6中可以看出分配院系1、2都是人数较多的院系，越往后则都是一些人数较少院系，到这一步已经完成了宿舍区域的划块预分。
第七，根据划块预分的结果，查询划块内的学生信息。将学生信息填充到预定区域之前，还要匹配“期望入住舍友”。先查询划块内的学生信息，在分配一名学生宿舍时，根据这名学生是否填写了期望入住舍友的信息，且房间内有可分配的空床位，则将期望入住舍友连同这名学生一并放入这个房间。
上述自动分配算法中的第一至第六步实现了将院系或班级自动预分到某个区域的效果，可根据不同的分配要求进行规则配置，可运用在网上选房的自动预分环节以及自动分配的方案中。算法的第七步在分配新生时，兼顾了期望入住舍友的结果，可运用在自动、半自动分配的方案中，通过该算法的设计实现灵活配置。
宿舍分配、组团选房及相关应用
我们根据各园区的宿舍分配要求，应用了不同的策略和功能模块，以达到学校要求。
首先，宿舍自动分配及微调，住宿分配按照研究生和本科生分为两类流程，如表7。
表7 研究生与本科生自动分配流程
研究生与本科生的宿舍分配区别在于：研究生通过线上申请确定是否住宿，而本科生统一安排住宿，根据班级集中的原则分配宿舍，由于本科生分班是学工系统的相关业务，不在此体现具体的过程。后续系统的自动分配功能参照了“自动分配算法的设计实现”一节内容实现可配置的算法规则，微调功能允许用户通过系统导出Excel调整后再导入系统，解决算法无法考虑到的特殊情况，从而完成本研新生的宿舍分配。
其次，组团选房，通过宿舍系统的网上选房和组团功能，新生组团时可以在系统上标明自己的兴趣爱好和作息时间。根据宿舍管理业务部门的反馈，大部分因寝室矛盾申请调宿的原因是性格与作息时间不合，因此组团功能打通了新生之间的信息壁垒并前置该环节，可以有效地减少学生入住后发生矛盾和申请调宿的概率。
再者，期望入住舍友，在研究生住宿意愿申请的界面上增加了“期望入住舍友”的功能，这个界面添加了一条按照“同一院系、性别、培养层次、学制”进行校验的规则，当填写的期望入住舍友不符合上述规则时，则不允许填写。另外当A填了B，B填了C时，则视作无效填写。只有在AB互填，或AB双方中只有一方填写了对方才视作有效的期望入住舍友。这个功能在新生未能组团成功或错过网上选房时，满足了部分期望住在一间寝室的新生的需求。
最后，虚拟楼，由于部分老生延期毕业，园区办公室无法为其退宿，导致新生宿舍分配工作开始后，无法给新生分配足够的床位。因此在系统中引入了“虚拟楼”的概念，根据园区需要将老生从系统中“搬迁”至虚拟楼。
通过上述的工作流程、思路与方法、以及新的系统功能，确保了我校新生宿舍分配工作的顺利推进。
对比往年相对固定的宿舍分配模式，疫情防控常态化时期学校的宿舍分配工作存在较大的变化。我们将自动分配算法做成可配置的多条规则，通过宿舍系统应用在各园区的宿舍分配工作中，同时通过“期望入住舍友”的功能满足部分新生期望入住一间寝室的个性化需求，取得了不错的效果。
未来，宿舍分配工作还将继续完善以下几点，以应对明后年宿舍分配工作可能发生的变化：
一是灵活运用系统现有功能例如网上选房、组团、住宿意愿申请、可配置的算法规则来满足各园区不同的分配要求。
二是算法中将研究生的部分院系组合视作一个整体，后续考虑完善此功能，实现院系组合的可配置化。
三是今年的本科生宿舍分配通过手动的划块预分后再进行学生的宿舍分配，只用到了算法中的部分规则，明年计划实现本科生宿舍分配的全自动过程，并考虑增加本科生新生的问卷调查步骤。
此外，在后续的实践过程中可能会出现新情况、新要求，需要对宿舍系统功能以及算法本身做出持续的完善，从而达到满意的自动分配结果，不断优化新生宿舍的统筹分配工作，也为新生们带来更好的宿舍选择体验。
