剛好最近工作用到
有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<::
有沒有適合的近似演算法可以推薦一下的...感恩...