根据投票将人分组

Question

我在寻找一种对人的数据集进行排序的算法时遇到了问题。我尽量详细解释：

故事从一项调查开始。一群人，比如说 600 人可以在 20-25 个项目之间进行选择。他们提出 #1-wish、#2-wish 和 #3-wish，其中 #1 是他们最想参与的项目，并希望 3 是“不完美但最可接受的选择”。

这些项目的参与者数量有限。每个项目可以加入大约 30 人（根据人数和项目数量）。

该算法将人们放在不同的项目中，并应找到最佳组合。

问题是你不能把所有有 1 个愿望 X 的人都放在某个项目中，然后把所有其他人也有 1 个愿望 X 放在第 2 个愿望中，因为那不会是最“最快乐”的情况为所有人。

当你想象得到他的第 1 名的每个人希望你得到 100 分，每个得到他的第 2 名的人希望得到 60 分，第 3 名的每个人希望得到 30 分，而那些没有得到他的一个愿望时，你可能会想到我的意思。 0 分。并且您希望获得尽可能多的积分。

我希望你能解决我的问题。这是一个学校项目日。有什么可以帮助我的吗？你有什么主意吗？我会感谢每一个小费！！

亲切的问候

Answer 1

您可以通过将其制定为最小成本网络流问题来最佳地解决此问题。

为每个人添加一个节点，为每个项目添加一个节点。

根据个人和项目的偏好设置他们之间流动的成本。

（由于 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。

容量字典指定了可以加入每个项目的人数上限。