2010-10-03 57 views
1

如果n個牀位要分配給m個人。每個人可能有多種偏好或根本不喜歡。如何滿足最大限度的人。有偏好並且得到相同的人將被記錄爲滿意的人。分配偏好

我試着用最小的首選牀位先分配一個最低偏好的人。有沒有我失蹤的情況,因爲它給了我一個錯誤的答案?

回答

4

這是maximum bipartite matching的問題。 Wiki有很好的算法,也可以查詢maximum flow

+0

您能否詳細說明一下? – san8055 2010-10-03 17:51:12

+0

@ san8055 - 這很難闡述,因爲這需要相當多的圖算法知識?具體而言,您需要知道圖表是什麼以及BF搜索是什麼。如果你知道這些,然後建立一個二部圖,其中兩組是「n」牀和「m」人。如果那個人喜歡那張牀,那麼你有一個人從一個牀邊到一個牀邊。將容量1添加到這些邊緣。然後將虛擬節點的容量1邊添加到每個人,然後從每張牀添加到另一虛擬節點。從第一個虛擬節點運行最大流量算法。飽和的邊緣將代表您的分配。 – IVlad 2010-10-03 17:58:20

+0

@非常感謝。如果我的假設有任何不妥之處,可以先分配一個最低偏好的人,然後選擇最低優先的睡牀 – san8055 2010-10-03 18:58:17