结对作业二[未完成]

时间：2023-02-12 17:37:02

结对作业二

作业链接

0 结对成员

031502411 胡冰
031502324 林诗尧

1 git链接

git传送门

2 生成数据

  • 程序原理
    • 手工设计一套标签与一套时间+随机random。
    • 对于每个部分，比如生成空闲时间段标签，先随机生成的数据的个数，因为题目中对个数有一定要求，还需要对个数做出调整。
  • 考虑因素
    • 手工设计的标签中相近相容的放在一组内，部门的标签在同组标签中选择，以免太过跳脱。
    • 同个对象不能生成重复的数据。用两种映射函数减少冲突的可能。

3 建模与算法

  • 数学建模
    • 假设学生最多有n个志愿。将匹配过程拆为n轮，每轮抽象为学生->部门一对一的匹配。分轮次充分兼顾志愿的优先级，单轮中考虑一种策略使得尽可能有多的学生至少被一个部门录取，减少unlucky数量。
  • 匹配程序思路
    • 匹配算法1.0
      • 首先按照志愿的优先级分n轮进行。
      • 单轮匹配时两种检查匹配策略。时间匹配要求学生的空闲时间段完全包含部门的常规活动时间。兴趣标签匹配按照匹配的个数优先级从高到低。学生按照这两个因素进行排序，排在前的先选择。
      • 不考虑将unlucky学生调剂到他没有填报志愿的部门，不存在补录。
      • 那对于收不到人的部门、进不了部门的学生我也很无奈啊。
      • 存在的问题：极端情况。可能存在一些情况，该轮匹配时已经匹配多个部门的学生因为兴趣标签与部门匹配程度高，该学生先进行选择，这样不能实现让尽可能多的学生最终匹配到部门。
    • 稍作改进算法2.0
      • 单轮中学生先按照该轮志愿部门分组，同组内的学生根据评价函数排序。设计的评价函数考虑到三个因素，学生已经录取的部门的数量p，学生剩余可能被录取的部门的个数q和学生与该轮志愿部门标签匹配程度s。设计函数f(p,q,s)=1/(p+1)+1/(q+5)+0.15*s。权值大的学生具有更高的优先选择权。
      • 上面的评价函数怎么算的呢？我悄悄脑补了一下，f与p、q成反比，而我觉得q是个不确定的因素，不应该占太大的比例，0.15s是减少上面说的极端情况，尚未被部门录取的学生1/(p+1)=1，不容易被0.15s反超，减少录取部门数量差距大的情况下因为标签匹配程度高而优先选择的可能。
      • 我是将空闲时间段拆成区间来处理。version1.0只添加了将输入string数组初始转化为区间以及区间的合并，将空闲时间处理成不相交、孤立的区间处理。匹配问题转化为两坨区间是否为包含关系的判断。而其实学生被部门录取时，应动态修改学生的空闲时间，version2.0增加了区间的拆分，因为考虑一下得出减少学生空闲时间的操作最多只可能将一个区间拆成两个不相交的小区间。来一波扫描线会更优雅。
  • 题外话
    • 想用个数据结构保存区间。先写了一波结构体套结构体作为成员变量，编译成功但不能运行啊？改了个class套class的数组还不行啊？最后用vector实现。理论AC写完各种用到的函数后一编译一万个报错。我改还不行吗。
    • 写代码时十分顺畅没啥问题，讲代码流程时却很绕，框架还好但实现有点复杂。

4 代码规范

  • 函数采用驼峰法命名
void Student::getTimeslot(Student stu) {
    prework.init();
    stu.time_slot = prework.deal_tmie(free_size, free_time);
}

int Student::getTagMatch(int dep_tag_size,string *dep) {
        return prework.tag_match_check(free_size,free_time,dep_tag_size,dep);
}
void Student::beAdmitted(int round,Timeslot dep) {
    time_slot = prework.split(time_slot, dep);
    ++admitted_size;
    is_accepted[round-1] = 1;
}
  • 成员变量采用xx_xx的形式
class Student {
public:
    int tag_size;
    int free_size;
    int dept_size;
    int can_match;
    int admitted_size;
    int tag_match[105];
    int round_dep;
    double round_value;
    string no;
    string tag[15];
    string free_time[55];
    string department[7];
    string addimited_dep[7];
    int department_id[7];
    int is_accepted[7];
    Student() { 
        tag_size = 0, free_size = 0, dept_size = 0, admitted_size = 0, can_match = 0, round_dep = 0;
        memset(tag_match, 0, sizeof tag_match);
        memset(is_accepted, 0, sizeof is_accepted);
    }

    Timeslot time_slot;
    void getTimeslot(Student stu);
    int getTagMatch(int m, string *dep);
    void beAdmitted(int id,Timeslot dep);
    Prework prework;
};
  • 宏定义，使用简洁，代码优雅
// student
#define Stu "students"
#define Sfree "free_time"
#define Sno "student_no"
#define Sdept "applications_department"
#define Stag "tags"

// department
#define Dept "departments"
#define Dsche "event_schedules"
#define Dno "department_no"
#define Dnum "member_limit"
#define Dtag "tags"

// print
#define Pstu "unlucky_student"
#define Padmt "admitted"
#define Padmt_mem "member"
#define Padmt_dept "department_no"
#define Pdept "unlucky_department"

5 结果评估

输入了助教给出的示例，看到一长串unlucky_student我是一脸懵逼，然后发现示例中部门招收的总人数为248，对于结果还是可以接受的。

6 结对感受

Loaing...

标签：

相关文章