一、GIT项目地址
二、结对人
- 蔡鸿杰（031502601）
- 曾玮诗（031502602）
三、问题描述
- 提供输入包括：
-
20个部门
- 部门编号（唯一值）
- 各部门需要学生数的要求的上限(单个，数值，在[0,15]内)；
- 部门的特点标签(多个，字符)；
- 各部门的常规活动时间段(多个，字符/日期）;
-
300个学生
- 学号（唯一值）；
- 学生绩点信息（单个，数值）；
- 学生部门意愿（部门意愿不多于5个且不能空缺）；
- 学生空闲时间段（多个，字符/日期）；
-
- 实现一个智能自动分配算法，根据输入信息，输出部门和学生间的匹配信息（一个学生可以确认多个他所申请的部门，一个部门可以分配少于等于其要求的学生数的学生） 及 未被分配到学生的部门 和 未被部门选中的学生。
四、数据模型
（1）输入数据模型
- 数据生成原理（略粗暴gg）
-
项目要求生成部门和学生信息，在部门的编号、部门标签（学生兴趣标签）、活动时间（学生空闲时间）方面我们是事先设计好部门的编号存入数组。
-
在随机生成时，有直接生成数据，比如说生成部门上限人数，则是在[10,15]里面随机生成一个数据。
-
还有随机从数组里面取出一个元素，比如要生成部门编号，则是随机生成一个数据i，先判断i是否前面已生成，符合条件后取出编号数组depart_no[i]里面的元素，否则再次随机生成数据直至符合条件。
-
如果是从数组里面取出多个元素，比如生成多个部门标签，需考虑同个部门不能生成重复标签，在生成i并成功取出标签数组tags[i]中的元素后，用一个bool型数组judge[i]对i进行标记以免下次重复。
-
其余数据生成均类似上述情况。
-
Example1:生成部门人数
dep[i].setShangxian(10+r.nextInt(6));//学生数【10,15】
Example2:生成一个编号
boolean []judge=new boolean[20];
int j,bm;
for(j=0;j<20;j++) //生成编号
{
bm=r.nextInt(20);
if(!judge[bm])
{
dep[i].setNum(depart_no[bm]);
judge[bm]=true;
break;
}
}
Example3:随机生成部门标签
int tag1,tag2,k=0;
tag1=2+r.nextInt(3);//随机生成2-4个标签数
boolean []judge2=new boolean[20];
String []tag=new String[tag1];
for(j=0;j<tag1;j++)//部门标签
{
while(k==0){
tag2=r.nextInt(10);
if(!judge2[tag2]){
tag[j]=tags[tag2];
judge2[tag2]=true;
k=1;
}
}
k=0;
}
dep[i].setTedian(tag);
- 考虑因素：
- 部门编号：按公平起见部门编号打乱分配。
- 部门人数上限：不了解部门实际要求，按照[10,15]人数区间随机生成部门人数。
- 部门活动（学生空闲）时间：我们所设计的时间是根据学生的实际情况进行考虑并规划设计合适的时间并在周日适当增加时间段，使时间更加实际化和人性化。
- 学生学号：按顺序分配，分为6个班级，每个班级50个人。
- 部门标签（学生兴趣）：选取设计较为广泛的标签（兴趣），部门和学生的标签都是一样，能够相互匹配。
- 绩点成绩：不了解学生实际情况，所以我们随机生成成绩。
- 学生数据模型
/*学生类*/
public class Xuesheng {
private String xuehao;//学号
private int chengji;//成绩
private String []xingqu;//兴趣数组
private String []yiyuan;//意愿数组
private String []kongxian;//空闲时间段数组
}
输入样例：
/*输入类*/
public class Shurulei {
private Xuesheng []students;//学生对象数组
private Bumen []departments;//部门对象数组
｝
- 部门数据模型
/*部门类*/
public class Bumen {
private String num;//部门编号
private int shangxian;//部门上限 0-15
private String []tedian;//部门特点标签
private String []huodong;//部门活动时间段
}
输入样例：
（2）输出数据模型
- 输出数据模型里面包括：
- 没匹配学生学号
- 没匹配部门编号
- 已匹配学生（学生学号，匹配部门编号）
/*输出类*/
public class Shuchulei {
private String []meipipei_xuesheng;//未匹配学生数组
private String []meipipei_bumen;//未匹配部门数组
private Pipei []yipipei;//已匹配对象数组
}
/*匹配类*/
public class Pipei {
private String xuehao;
private String bumen;
}
五、算法分析
-
根据题目所给的信息，我们将输入数据分成了两个类，学生类和部门类。两个类中分别拥有各自的属性。
-
在进行算法设计之前，我们研究了我们用的数据结构，发现在匹配的过程中可以使用的因素有：学生的成绩，部门活动时间和学生的空闲时间，每个学生的部门意愿以及部门标签和学生的兴趣标签。我们觉得我们的匹配算法可以在这几个因素上面做文章。首先是学生的部门意愿，我们认为在分配时，只有有意愿去某个部门的学生才有机会被分配到那个部门，于是我们决定意愿成为最优先的因素。
-
在这之后我们决定了三个优先算法：活动时间优先，兴趣优先，成绩优先。
前提条件是：学生对象数组按照学号顺序，部门的顺序打乱以保障公平性，每个算法都是按照部门顺序，每个部门先后依次匹配所有的学生。 -
活动时间优先：这个算法只考虑两个因素：活动时间重合度和学生成绩，活动时间重合度是指学生的空闲时间跟部门活动时间相等的个数，相等个数越多，重合度就越高，然后按照重合度从高到低选出部门所需的学生，重合度相同优先考虑成绩高于80的学生。因为学生被部门选中后相应的空闲时间也将被占用，所以被占用的时间将不会参与计算与其他部门活动时间的重合度。
private static void time(int s,int d,Xuesheng []stu,Bumen []dep) {
// 活动时间
int i,j,h[][]=new int [d][s];
Shuchulei out = new Shuchulei();//输出对象
Pipei []studep = new Pipei [s*5];//匹配对象
for (i=0;i<s*5;i++) {
studep[i] = new Pipei();
}
String []ustu = new String[s];//没被选中的学生数组
String []udep = new String[d];//没有选中学生的部门数组
int cstu[]=new int[s];//学生选中情况（被选中为1，未被选中为0）
int cdep[]=new int[d];//部门选人情况（有人为1没人为0）
int count=0,ust=0,ude=0;
int stunum;//最大匹配的学生
int max;//部门最大人数
/*开始匹配*/
for(i=0;i<d;i++){
max=dep[i].getShangxian();
for(j=0;j<s;j++){//学生与部门匹配程度
if(dep[i].want(stu[j].getYiyuan())){//判断学生是否报名该部门
h[i][j]=dep[i].cmpt(stu[j].getKongxian())*2;
if(stu[j].getChengji()>=80)h[i][j]+=1;//成绩大于80的学生优先
}
else{
h[i][j]=-2;//没有报名的学生该部门优先值为-2
}
}
for(int k=0;k<max;k++){
stunum=maxstu(h[i],stu);
System.out.println(stunum);
if(stunum>=0){//只有报名了该部门的学生才有机会进入该部门
studep[count].setXuehao(stu[stunum].getXuehao());
studep[count].setBumen(dep[i].getNum());
dep[i].putbusy(stu[stunum].getKongxian());//学生对应的空闲时间被部门占用
count++;
cdep[i]=1;
cstu[stunum]=1;
}
else break;
}
}
for(j=0;j<d;j++){
if(cdep[j]==0){
udep[ude]=dep[j].getNum();//记录没有选中学生的部门
ude++;
}
}
for(j=0;j<s;j++){
//System.out.println(cstu[i]);
if(cstu[j]==0){
ustu[ust]=stu[j].getXuehao();//记录没有被部门选中的学生
ust++;
}
}
/*给输出对象赋值*/
Pipei []sd = new Pipei [count];
String []us = new String[ust];
String []ud = new String[ude];
for(i=0;i<count;i++){
sd[i]=studep[i];
}
for(i=0;i<ust;i++){
us[i]=ustu[i];
}
for(i=0;i<ude;i++){
ud[i]=udep[i];
}
out.setYipipei(sd);
out.setMeipipei_bumen(ud);
out.setMeipipei_xuesheng(us);
Duxie.xie(out, new File(".\output_condition.txt"));//输出结果
}
- 兴趣优先：这个算法同样只考虑两个因素：兴趣重合度和成绩，兴趣重合度是指学生的兴趣跟部门标签相同的个数，相同的个数越多，重合度就越高，然后按照重合度从高到低选出部门所需的学生，重合度相同优先考虑成绩高于80的学生。因为学生的兴趣可以同时跟多个部门的标签相同，所以学生被部门选中后兴趣不会发生变化。
int i,j,h[][]=new int [d][s];//优先值数组
Shuchulei out = new Shuchulei();//输出对象
Pipei []studep = new Pipei [s*5];//定义匹配对象
for (i=0;i<s*5;i++) {
studep[i] = new Pipei();
}
String []ustu = new String[s];//没被选中的学生数组
String []udep = new String[d];//没有选中学生的部门数组
int cstu[]=new int[s];//学生选中情况（被选中为1，未被选中为0）
int cdep[]=new int[d];//部门选人情况（有人为1没人为0）
int count=0,ust=0,ude=0;
int stunum;//最大匹配的学生
/*开始匹配*/
for(i=0;i<d;i++){
int max=dep[i].getShangxian();//获取该部门人数上限
for(j=0;j<s;j++){//学生与部门匹配程度
if(dep[i].want(stu[j].getYiyuan())){//判断学生是否报名该部门
h[i][j]=dep[i].cmph(stu[j].getXingqu())*2;//根据兴趣给确定优先值
if(stu[j].getChengji()>=80)h[i][j]+=1;//成绩大于80的学生优先
//System.out.println(h[i][j]);
}
else{
h[i][j]=-2;//没有报名的学生该部门优先值为-2
}
}
for(int k=0;k<max;k++){
stunum=maxstu(h[i],stu);//找出优先值最大的学生
//System.out.println(stunum);
if(stunum>=0){//只有报名了该部门的学生才有机会进入该部门
studep[count].setXuehao(stu[stunum].getXuehao());
studep[count].setBumen(dep[i].getNum());
count++;
cdep[i]=1;
cstu[stunum]=1;
}
else break;
}
if(cdep[i]==0){
udep[ude]=dep[i].getNum();//记录没有选中学生的部门
ude++;
}
}
for(j=0;j<s;j++){
//System.out.println(cstu[i]);
if(cstu[j]==0){
ustu[ust]=stu[j].getXuehao();//记录没有被部门选中的学生
ust++;
}
}
- 成绩优先：这个算法只考虑一个因素：成绩，每个部门将根据报名该部门的学生的成绩来选择学生，优先选择成绩高的学生。同样学生的成绩不会因为学生被部门选中而发生变化。
int i,j,h[][]=new int [d][s];
Shuchulei out = new Shuchulei();//输出对象
Pipei []studep = new Pipei [s*5];//匹配对象
for (i=0;i<s*5;i++ ) {
studep[i] = new Pipei();
}
String []ustu = new String[s];//没被选中的学生数组
String []udep = new String[d];//没有选中学生的部门数组
int cstu[]=new int[s];//学生选中情况（被选中为1，未被选中为0）
int cdep[]=new int[d];//部门选人情况（有人为1没人为0）
int count=0,ust=0,ude=0;
int stunum;//最大匹配的学生
int max;//部门最大人数
/*开始匹配*/
for(i=0;i<d;i++){
max=dep[i].getShangxian();//获取该部门人数上限
for(j=0;j<s;j++){//学生与部门匹配程度
if(dep[i].want(stu[j].getYiyuan())){
h[i][j]=stu[j].getChengji();//根据成绩确定优先值
}
else{
h[i][j]=-2;//没有报名的学生该部门优先值为-2
}
}
for(int k=0;k<max;k++){
stunum=maxstu(h[i],stu);//找出优先值最大的学生
System.out.println(stunum);
if(stunum>=0){//只有报名了该部门的学生才有机会进入该部门
studep[count].setXuehao(stu[stunum].getXuehao());
studep[count].setBumen(dep[i].getNum());
count++;
cdep[i]=1;
cstu[stunum]=1;
}
else break;
}
}
for(j=0;j<d;j++){
if(cdep[j]==0){
udep[ude]=dep[j].getNum();//记录没有选中学生的部门
ude++;
}
}
for(j=0;j<s;j++){
//System.out.println(cstu[i]);
if(cstu[j]==0){
ustu[ust]=stu[j].getXuehao();//记录没有被部门选中的学生
ust++;
}
}
- 之所以在前两个算法中都加入了成绩因素是因为我们觉得成绩的高低在一定的程度上体现了学生的能力和态度，对部门在选择学生的时候有一定的参考价值。
六、代码规范
- 以前都是一个人编写代码，所以比较没怎么注意代码规范。这次结对作业双方对编码做了些规范：
- 每个功能使用一个函数，
- 在输入输出方面使用对象，每个对象进行了单独的封装，通过接口进行调用。
- 使用注释，让结构更加清晰。
- 类名首字母大写
- 函数名首字母小写
部分代码如下：
private static int maxstu(int[] h,Xuesheng []stu) {
// 选出最大下标学生
int max=-2;
int num=0;
int i;
for(i=0;i<h.length;i++){
if(h[i]>max){
max=h[i];
num=i;
}
}
if(max>=0){
h[num]=-2;
return num;
}
else return -1;
}
七、算法测试报告与结果分析评价
| 输入次数 | 优先条件 | 匹配学生个数 | 未匹配学生个数 | 实际耗时 | 输出文件路径 |
|---|---|---|---|---|---|
| 1 | 活动时间 | 168 | 132 | 0.533 | 文件路径 |
| 1 | 兴趣 | 153 | 147 | 0.563 | 文件路径 |
| 1 | 成绩 | 99 | 201 | 0.508 | 文件路径 |
| 2 | 活动时间 | 180 | 120 | 0.584 | 文件路径 |
| 2 | 兴趣 | 159 | 141 | 0.573 | 文件路径 |
| 2 | 成绩 | 103 | 197 | 0.594 | 文件路径 |
| 3 | 活动时间 | 182 | 118 | 0.519 | 文件路径 |
| 3 | 兴趣 | 154 | 146 | 0.547 | 文件路径 |
| 3 | 成绩 | 91 | 209 | 0.552 | 文件路径 |
- 以上是三次输入所得的不同优先条件下的测试数据：
- 可以看出三个优先条件中成绩作为优先条件时，匹配人数最少，活动时间作为优先条件时，匹配学生人数最多。可见成绩的限制比较片面，而活动时间的限制则较为合理。
- 时间上貌似由于样本比较小，优先条件不同的时候时间相差不大。
- 由于一个学生可以加入多个部门同时部门要求的学生有限，所以有较多的学生没有被选中。
八、结对感受
曾玮诗：
- 第一次结对编写代码，感觉还不错。经过讨论我们最终决定用JAVA进行编写，队友挺强的，能够在算法方面有较好的解决方法，匹配方面的问题基本采用队友的算法思想。我主要在生成程序方面设计编写，主要考虑一些随机数的生成以及属性不重复的问题。虽然整个过程下来比较顺利，但是最后生成效率感觉一般般，有点尴尬，还得继续努力。
- 在结对过程,双方能够互补，我也有时一些非常细小的bug甚至能为紧张的赶作业气氛变得欢乐起来（比如我在写生成程序时在标签数组tags中写入了两个相同的“reading”,在编译运行时发现有重复属性生成急的赶紧看算法，后来试了好多次突然发现只有"reading"会重复，赶紧去看一下数组，于是乎，寝室里迸发出了原子弹般的笑声,2333!)。这门课能要求自己不断按时完成作业，挺好的，希望以后能不断进步。>_<
蔡鸿杰：
- 因为之前选课较晚，所以第一次结对是三个人，这次是第一次两个人结对，我的对友也是我的舍友，但是由于国庆放假的原因各自都回家了，所以在交流上存在一定的困难，没有能像在宿舍时的交流那么方便。我们在研究了题目的要求之后决定使用并不是十分了解的java进行开发（当时可能是觉得java的工具比较方便吧），同时因为远程交流不方便的原因，所以我们在分工以后基本就是各自开发，大的方面两个人讨论决定，细节的话就按照各自的想法来实现，回到学校以后再将两个人开发的程序进行整合。我负责的是文件的读写和匹配的算法，在算法方面，首先java和C++的算法逻辑有一定的相似性，但是我对java的理解不够深，所以导致有些想法不能很好的转换成代码，同时也浪费了不少的时间（写了半天才发现这样不太行，又得改回去），所以导致最后的算法可能会比较简单。在文件读写方面我选择了上网学习大神的代码，在这过程中我另外一个舍友推荐给我一个谷歌大神写的json工具包，在一段时间的学习以后，通过这个工具包我很好的实现了文件的读入和输出。在学习的过程中也加深了自己对java这门语言的了解。
- 因为对友是舍友的关系，我们两个在整合程序时遇到的困难能够很快的解决，但是在写代码的过程中有效的交流不多，导致两者的代码不太匹配，好在程序有一定的模块化，在整合时遇到的困难也比较容易解决。
- 在结对的过程中我发现一个人的能力有的时候还是有限的，特别是我还有一点拖延症，两个人一起解决问题的速度比一个人自己解决快了很多。而且我的对友，我觉得在组织语言这个方面上他比我强，所以博客主要是我的对友写的，我在旁边提供我的想法供他参考。同时两个人合作也能够发现一些自己一个人发现不了的bug。