您可以通過將其作爲最小成本網絡流量問題進行優化來解決此問題。
爲每個人添加一個節點,併爲每個項目添加一個節點。
根據自己的喜好設置人與項目之間的流量成本。
(作爲Networkx提供分鐘費用流,但不是最大費用流我已設置的成本是 負。)
例如,使用Networkx和Python:
import networkx as nx
G=nx.DiGraph()
prefs={'Tom':['Project1','Project2','Project3'],
'Dick':['Project2','Project1','Project3'],
'Harry':['Project1','Project3','Project1']}
capacities={'Project1':2,'Project2':10,'Project3':4}
num_persons=len(prefs)
G.add_node('dest',demand=num_persons)
A=[]
for person,projectlist in prefs.items():
G.add_node(person,demand=-1)
for i,project in enumerate(projectlist):
if i==0:
cost=-100 # happy to assign first choices
elif i==1:
cost=-60 # slightly unhappy to assign second choices
else:
cost=-30 # very unhappy to assign third choices
G.add_edge(person,project,capacity=1,weight=cost) # Edge taken if person does this project
for project,c in capacities.items():
G.add_edge(project,'dest',capacity=c,weight=0)
flowdict = nx.min_cost_flow(G)
for person in prefs:
for project,flow in flowdict[person].items():
if flow:
print person,'joins',project
在這種代碼Tom的第一個選擇是Project1,然後是Project2,然後是Project3。
容量字典指定有多少人可以加入每個項目的上限。
哇!太棒了! 我不知道Python或networkx,但我希望我能處理這個,應該不那麼難。還有一個問題。我是否也可以爲項目設置最少人數? – Jannik
當然,您只需設置項目的需求,例如對於Project1至少有10個添加G.add_node('Project1',需求= 10),並減少dest的需求10匹配。 –