주어진 특정 사례에 대한 일치 문제를 해결하는 C++ 프로그램

이것은 주어진 특정 케이스에 대한 매칭 문제를 해결하기 위한 C++ 프로그램입니다. 여기서 N명의 남자와 N명의 여자가 주어지고, 각 사람은 이성의 모든 구성원을 선호하는 순서대로 순위를 매기고, 남녀 모두가 자신보다 서로를 갖고 싶어하는 두 명의 이성애자가 없도록 결혼합니다. 현재 파트너. 그런 사람이 없다면 모든 결혼은 "안정적"입니다.

알고리즘

Begin
   function WomenPrefersMenOverMen1():
   A) Check if women prefer men over her current engagement men1
   B) If men1 comes before men in list of women, then women prefer her current engagement.
   C) If men comes before men1 in womens's list, then free her current engagement and engage her with men.
End
Begin
   function stablewedding():
   1) Boys are numbered as 0 to N-1.
   2) Girls are numbered as N to 2N-1.
   3) While men are free
      A) Pick the first free man
      B) One by one go to all women according to pick free man’s preferences.
      C) The woman of preference is free, woman and man become partners.
      D) If woman is not free Find current engagement of woman
      E) If woman prefers man over her current engagement man1, then break the engagement between woman and man1 and engage man with woman.
End

예

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define N 4
bool WomenPrefersMenOverMen1(int prefer[2*N][N], int w, int m, int m1) {
   for (int i = 0; i < N; i++) {
      if (prefer[w][i] == m1)
         return true;
      if (prefer[w][i] == m)
         return false;
   }
}
void stablewedding(int prefer[2*N][N]) {
   int wPartner[N]; //Initialize an array to store partner of women.
   bool mFree[N]; //Initialize an array to store availability of men.
   //Initialize all men and women as free.
   memset(wPartner, -1, sizeof(wPartner));
   memset(mFree, false, sizeof(mFree));
   int freeCnt = N;
   while (freeCnt > 0) { //While men is free
      int m; //Pick the first free man
      //One by one go to all women according to pick free man’s preferences.
      for (m = 0; m < N; m++)
         if (mFree[m] == false)
            break;
      for (int i = 0; i < N && mFree[m] == false; i++) {
         int w = prefer[m][i];
         //The woman of preference is free, woman and man become partners.
         if (wPartner[w-N] == -1) {
            wPartner[w-N] = m;
            mFree[m] = true;
            freeCnt--;
         } else { //If w is not free
             //Find current engagement of woman
            int m1 = wPartner[w-N];
            // If woman prefers man over her current engagement man1, 
            // then break the engagement between woman and man1 and engage man with woman.
            if (WomenPrefersMenOverMen1(prefer, w, m, m1) == false) {
               wPartner[w-N] = m;
               mFree[m] = true;
               mFree[m1] = false;
            }
         }      
      }
   }
   cout << "Woman Man" << endl;
   for (int i = 0; i < N; i++)
      cout << " " << i+N << "\t" << wPartner[i] << endl;
}
int main() {
   int p[2*N][N] = { 
      {7, 5, 6, 4},
      {5, 4, 7, 6},
      {4, 5, 7, 6},
      {4, 5, 7, 6},
      {0, 1, 3, 2},
      {0, 1, 3, 2},
      {0, 1, 3, 2},
      {0, 1, 3, 2},
   };
   stablewedding(p);
   return 0;
}

출력

Woman Man
4 3
5 1
6 2
7 0