【問題E25】老問題─求最大的總美滿度。 [回前頁]
這是個困擾人類數萬年的問題:如何使每個人找到最適合的伴侶?好的對象人人追求,因此追求失敗的比例永遠超過成功率。許多人被迫選擇心目中較差的對象,也產生了大量不美滿的婚姻。
姑且假定地球上的男女一樣多,每個配對都有一個"美滿度",例如甲男配乙女美滿度為 90 ,丙男配丁女美滿度為40,如此可以得到一個矩陣:
A男 B男 C男 D男
A女 90 80 80 80
B女 80 20 10 10
C女 85 70 20 10
D女 80 60 80 10
在亞當斯密資本主義理論風行全球的二十世紀中,約翰納許提出了劃時代的創見。也因此獲得了諾貝爾經濟學獎。
他理論的一個推斷為:倘若所有人同時追求最好的對象,整體婚姻的美滿度反而會下降。舉例而言:假定這個世界是由男性來追求女性,而女性決定他的伴侶,在上面那個矩陣裡,所有人都想跟A女在一起,A女選擇了在一起後會最美滿的A男,B女則挑了剩下來最好的B男,C配C,D配D,最後四對新人的總美滿度為90+20+20+10=140。(見底線數字)
做點讓步反而會有更好的結果:假定不要每個人都競爭A女,A男配B女;B男配C女;C男配D女;D男配A女,則總美滿度為80+80+70+80=310。(見斜黑體數字)
然而在自由競爭的結婚"市場"下,每個個體無法去判斷自己該做怎麼樣的讓步以及該讓到什麼地步,因此你會發現所有人還是努力去追求自己心目中最理想的對象(你會因為跟你朋友討論對面那三個異性怎麼"分配"比較好嗎?)這或許也是離婚率不斷高升的原因之一。
到了二O五O年,政府決定要出面改善這個狀況,等數的男女資料被輸入資料庫,由電腦判斷每種配對的"美滿度",之後透過程式運算得到最大的總「美滿度」,並根據結果替每位適婚男女安排結婚對象。
你的工作就是依照「美滿度」表找出最佳的配對方式,當然,每個人最多只能有一個伴侶,但要注意,有些人天生"顧人怨",沒有人願意跟他/她配對,意即美滿度可以是負數,而不配對的美滿度就是0,簡而言之,如果配對起來美滿度是負數的話不如不配。身為一個程式設計師,你是否能成為稱職的「月下老人」呢?
輸入檔說明
輸入檔包含了多筆的測試資料。每筆資料第一行為一個正整數N(1≦N≦100),接下來包含N個整數,並以一個空白鍵分隔,其中第i行的第j個整數表示女士Wi與男士Mj配對後的美滿度(可能為負整數或0)。最後一筆資料後會有一行0表示結束。輸出檔說明
針對每筆資料輸出一個整數,即最大的總美滿度,並以換行分隔。
範例輸入
3
1 2 3
1 2 3
1 2 3
4
90 80 80 80
80 20 10 10
85 70 20 10
80 60 80 10
4
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
-1 -1 -1 -1
0
範例輸出
6
310
0