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

更新于：2019 年 07 月 30 日

416 次浏览

开启你的 职业生涯

通过完成课程来获得认证

开始学习
广告