刚好最近工作用到
有100个男人和100个女人
每对男女之间，隔著名为爱情的距离
写成函数就是 d = dist(♂、♀)
如果如果，每个人都能和最爱的他长相厮守，该是多美的结局
但教堂的精灵早已暗示过： 人应该和第二、第三爱的人结婚
http://ext.pimg.tw/cocomi20010501/1207328483.jpg
要是每个人都抓着眼前的幸福不放
和每个人都保持优雅的距离、不在谁怀里停留的学姊 因此落单 只能跟死肥宅结婚
这未免太不幸了吧？
或许，和那个稍稍远了些的男人结婚也不坏啊
虽然鼻子大了点、少了一对像翅膀的背肌、小鸟依人的梦想终究不切实际......
但这样大家都能得到幸福了吧？
让每个人之间距离的加总最小化
也就是argmin(sum({dist(♂、♀) for all ♂&♀that are togethe}))
这样就够了吧？
是的，看到这题目就知道要头大了QAQ
不想掉入NP的深渊，几和学大概是仅有的救赎
偏偏爱漂浮在与死亡接壤的座标，连笛卡儿都难以触及
三角不等式，解不开我和她的三角习题
有点sense的人就知道，只能在集合上作动态规划了QAQ QAQ QAQ
就算真的写出这几百行的code 时间复杂度还是高达O(2^N)
干！
到底为啥我一个电机肥宅要写这个啦::>n<::
有没有适合的近似算法可以推荐一下的...感恩...