Other Python

最佳CP算法

由光棍节想到的算法问题。假设一个学校里有100个少年和100个少女,少年和少女心中都有一个好感度数值排列表,现在我们来做CP(coterie partner),按照正常的剧情展开,勇敢的少年们去向少女们告白,大致流程是这样:

第一天,所有少年都去找排在他们好感度列表第1位的少女表白。告白结束后,少女如果只收到一个少年的告白,那么就和这个少年交往。如果收到多于一个少年的告白,就和其中她最喜欢的少年交往,把其他少年都拒绝掉。

第二天,所有在第一天被发好人卡的少年们,接着发起告白行动,去向排在自己好感度列表第2位的少女告白。告白结束后,如果某个少女已经在交往中,但是又有一个她更喜欢的少年来向她告白,那少女就把原来那个少年甩掉,再和这个她更喜欢的少年交往。

第三天,少年们继续发起告白运动,包括第一天告白成功,但第二天被挖了墙角的,接着向还没有拒绝过他的女生中他最喜欢的那个告白。

如此直到CP结束,我们可以得到一个稳定的CP,稳定的概念是,对于任何一对恋爱关系——比如少年A和少女A——都不存在少年A对少女B的好感度大于少女A,或是少女B对于少年A的好感度大于她现任的男朋友少年B的情况。以上就是1962年美国数学家戴维·戈尔(David Gale)和劳埃德·夏普利(Lloyd Shapley)对稳定婚姻问题研究出的Gale & Shapley算法了。经过计算发现,这种情况看似少女们拥有自主选择权,真正收益的其实是勇往直前的少年们,他们总能追到自己好感度列表中相当靠前的少女。当然,这个算法最主要是解决诸如学生对于其意向学校的选择,座位的安排,这类问题的实际可行性。

Algorithm[Python]

前面的描述有点复杂,先将其简化,假设有三男三女,互相好感度如下:

接下来按照前面的流程,开始CP

Coding & Run Result

运行结果:

Engagements:
itsukl and haruhi
shamisen and mikuru
haruhi dumped itsukl for kyou
mikuru dumped shamisen for itsukl
shamisen and yuki
Couples:
haruhi is engaged to kyou,
mikuru is engaged to itsukl,
yuki is engaged to shamise

7 thoughts on “最佳CP算法”

      1. 你来修改个后宫算法吧…无论有多少少年来告白少女们永远只和好感度最高的少年交往…

Leave a Reply

Your email address will not be published. Required fields are marked *