Stable Marriage Problem - 聯招

SMP問題也可以用來解決大學聯招問題

運用學生 考試分數 與 志願排名 來進行配對

這個方法算是簡易的配對方法
如果學校有設定科目加權、要求分數需於均標、高標等
則需改寫配對方法

配對方法：

尋找學生第一志願

    學校是否額滿

        是，配對

改變最低錄取分

檢查額滿狀態

        否，找尋學校中最低錄取分數 比較

            分數較高    取代

                        重新計算最低錄取分

並為被取代的重新尋找配對

            分數較低    找下一志願

==============================================

配對部分程式碼(Java)

   public void match(){
      int i;
      for( i=0 ; i <= schAmt ; i++ ){      //清空額滿狀態
         schFull[i]=false;
      }
      for( i=1; i <= stdAmt ; i++){      //為每位學生配對
         stableByGrade(i);
      }

   }

   private void stableByGrade(int std){
      int pstd,psch,i;
      boolean s;
      s = false;
      i=1;
      while(!s){
         psch = student.getWsr(std,i);         //尋找std 志願
         if (schFull[psch]==false){   //學校未額滿 直接配對
            stdSch[std] = psch;
            schStdAmt[psch]++;         
            school.setEnrollList(psch,schStdAmt[psch], std);
         
            //若比最低錄取分低 改變最低分數 登記為最低分數學生
            if(school.getLastGrade(psch) > student.getGrade(std)){
               school.setLastGrade(psch,student.getGrade(std));
               schStdLast[psch]=std;
               schStdLastSeat[psch]=schStdAmt[psch];
            }
            //如果總數已達到錄取名額 改變為錄取額滿
            if(schStdAmt[psch] >= school.getEnrollLimit(psch)){
               schFull[psch] = true;
            }
            s = true;         //配對成功
         }
         else{               //學校錄取額滿 先比較
            //讀取最低分數 比較分數
            //分數較高 取代 並為學生重新配對
            if(school.getLastGrade(psch) < student.getGrade(std))
            {
               pstd = schStdLast[psch];
               stdSch[std] = psch;
               school.setEnrollList(psch,schStdLastSeat[psch],std);
               //重新尋找最低分數
                  int scSeat, lscLim, lgrd, lstd;
                  lscLim = school.getEnrollLimit(psch);
                  lstd = 0;
                  lgrd = 100;
                  for(scSeat = 1; scSeat <= lscLim ; scSeat++ )
                  {
                     lstd = school.getEnrollList(psch,scSeat);
                     if(lgrd > student.getGrade(lstd)){
                        lgrd = student.getGrade(lstd);
                        schStdLast[psch]=lstd;
                        schStdLastSeat[psch]=scSeat;
                     }
                  }
                  school.setLastGrade(psch,lgrd);
               s=true;         //配對成功
            
               stableByGrade(pstd);   //pstd重新配對
            }
            else{
               i++;         //找下一個志願
            }
         }
      }
   }