Gale-Shapley Algorithm（稳定匹配算法）

一、算法核心思想

以男生与妹子相亲为例：有M个男生记为M={1,2…M},M个女生M’={1,2…M}，现在每个男生选择一个心仪的女生作为心动女生，可以选重复的，之后，每个男生都心有所属。这时，被多个男生选中的妹子就得考虑考虑了，该接受谁，拒绝谁，该妹子接受（有多个男生追求，则至少接受一个）了一个男生后，则暂时牵手成功，未被选中的男生则重新选择心动女生；若被拒绝了的男生重新选择的心动女生，该心动女生已经有了暂时牵手成功的对象，则该男生与该对象PK（看谁魅力更大，钱更多），PK胜出的人与该妹子暂时牵手，PK失败的男生继续寻找心动女生，从而进行迭代；最后，所有男生和女生都有一个暂时牵手对象时，则迭代结束，转正成为正式男女朋友。

转载自： https://blog.csdn.net/lc_miao/article/details/78114127

作者：lc_miao的博客

来源：CSDN