稳定匹配问题之三国
首先，我们先看看问题：
有n个男人和n个女人(n>=2)，每个男人对所有女人有一个好感度排名，每个女人对所有男人也有一个好感度排名。将男女两两配对，得到n对男女，称之为一个完美匹配。如果有一组男女A和B，他们在匹配中没有被配对，且对对方的好感度均大于对现有配偶的好感度（男人A觉得女人B好过现在的妻子C，女人B觉得A好过现在的丈夫D），则称之为一个不稳定配对。如果一个完美匹配中没有不稳定配对，则称改匹配为一个稳定匹配。
|
左图是男对女的好感度，右图是女对男的好感度
思路：
首先，拿到这个题，一次性写出是不现实的，也就是说，这其实也就是一个不断尝试的过程，也就是说，我们匹配之后，需要对已经匹配的序列确保排序没有问题，达到稳定匹配，当然想选择和自己最喜欢的人在一起了，但是，最为上帝，得考虑到全局，也就是说大家尽量都是彼此更爱的人，没有一个你爱的人他身边的人更爱的你身边的人，你身边的人更爱他身边的人。哈哈哈哈，有点绕了。但是我们的目的也就是找出一个稳定匹配。
#include<stdio.h>
#include<stdlib.h>
#define num 5
int m[num][num]={{0,1,2,4,3},{0,2,1,3,4},{4,0,2,1,3},{2,1,3,0,4},{2,0,1,3,4}};
//男生对女生的偏爱程度
int w[num][num]={{4,0,1,3,2},{3,1,2,0,4},{3,2,1,4,0},{0,1,3,2,4},{2,3,4,1,0}};
//女生对男生的偏爱程度
int s1[num]={-1,-1,-1,-1,-1}; //男生是否配对 -1否 其它为配对女生的序号
int s2[num]={-1,-1,-1,-1,-1}; //女生是否配对 -1否 其它为配对男生的序号
void output() //输出两个偏好矩阵
{
printf("男：0->吕布,1->刘备,2->孔明,3->周瑜,4->曹操
");
printf("女：0->貂蝉,1->大乔,2->小乔,3->尚香,4->阿丑
");
int i,j;
printf("男生偏好矩阵：
");
for(i=0;i<num;i++)
{
printf("男%d:",i);
for(j=0;j<num;j++)
{
printf("% d",m[i][j]);
}
printf("
");
}
printf("女生偏好矩阵：
");
for(i=0;i<num;i++)
{
printf("女%d:",i);
for(j=0;j<num;j++)
{
printf("% d",w[i][j]);
}
printf("
");
}
}
void match() //匹配
{
int i,j,k;
int old, now;
for(i=0;i<num;i++){
if(s1[i]==-1){ //该男生没有有匹配对象
for(j=0;j<num;j++)
{
if(s2[m[i][j]]==-1){ //如果心仪女神没有配对，则配对
s1[i]=m[i][j];
s2[m[i][j]]=i;
break;
}else{ //如果心仪女神有配对
old=now=-1;
//寻找女生现男友在女生心仪对象列表的下标
for(k=0;k<num;k++)
if(w[m[i][j]][k]==s2[m[i][j]])
old = k;
//寻找当前男生在女生心仪对象列表的下标
for(k=0;k<num;k++)
if(w[m[i][j]][k]==i)
now = k;
if(old>now){ //如果女生更加偏爱该男生，则换对象
s1[i]=m[i][j]; //当前男生
s2[m[i][j]]=i;
s1[w[m[i][j]][old]]=-1; //前男友
break;
}
//如果女生更加偏爱现在男生，则替换下一个女生
}
}
}
}
for(i=0;i<num;i++) //是否所有的男生都配对完成
{
if(s1[i]==-1){
match();
break;
}
}
}
void display() //输出配对完成后的男女搭配
{
int i;
printf("man —— woman
");
for(i=0;i<num;i++)
{
printf(" %d —— %d
",i,s1[i]);
}
}
int main()
{
output();
match();
display();
}
注释写了大致的算法逻辑部分，应该可以看懂的