排序人以群分的基础上投票 [英] Sorting People into Groups based on Votes

问题描述

我有找到一个算法排序人数据集的一个问题。我试图解释尽可能详细：

I have a problem with finding a algorithm for sorting a dataset of people. I try to explain as detailed as possible:

这个故事开始于一个调查。一堆人，可以说600 20-25项目之间可以选择。他们提出了一个＃1的心愿，＃2，愿望和＃3的愿望，其中＃1是他们想参与，并希望3不完美的，但是，最可以接受的，选择最想要的项目。

The story starts with a survey. A bunch of people, lets say 600 can choose between 20-25 projects. They make a #1-wish, #2-wish and #3-wish, where #1 is the most wanted project they want to take part and wish 3 the "not-perfect-but-most-acceptable-choose".

这些项目都在他们的参与人数限制。每个项目都可以参加30人左右（根据人数和项目数）。

These project are limited in their number of participants. Every project can join around 30 people (based on the number of people and count of projects).

该算法使人们在不同的项目，应该可以找到最佳的组合。

The algorithm puts the people in the different projects and should find the best possible combination.

现在的问题是，你不能只是把所有的人在某些项目中的1号的心愿X和东西的所有其他在有数字2的心愿也数1心愿x方法，因为那会不会是最最幸福的局面为大家。

The problem is that you can't just put all the people with their number 1 wish X in the certain project and stuff all the other with also number 1 wish X in there number 2 wish because that would not be the most "happiest" situation for everybody.

您也许能想到的我是什么意思时，你能想象，对于大家谁得到他的1号祝你得到100分，为大家谁得到他的2号心愿60分，3号心愿30分，谁得到没有在一个他的愿望0分。你希望得到尽可能最高分的可能。

You may can think of what I mean when you imagine that for everybody who get his number 1 wish you get 100 points, for everybody who get his number 2 wish 60 points, number 3 wish 30 points and who get not in one of his wishes 0 points. And you want to get as most points as possible.

我希望你明白我的问题。这是一个学校项目的一天。 有什么在那里，可以帮助我？你有什么想法？我将感谢每TIPP !!

I hope you get my problem. This is for a school-project day. Is there something out there that could help me? Do you have any idea? I would be thankful for every tipp!!

亲切的问候

推荐答案

您可以通过优化配制它作为最小成本网络流问题解决这个问题。

You can solve this optimally by formulating it as a min cost network flow problem.

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

Add a node for each person, and one for each project.

设置费用的人，并根据其preferences一个项目之间的流

Set cost for a flow between a person and a project according to their preferences.

（作为Networkx提供了一个最小代价流，但不是最大的成本流，我设置了费用为 负。）

(As Networkx provides a min cost flow, but not max cost flow I have set the costs to be negative.)

例如，使用Networkx和Python：

For example, using Networkx and 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

在此code汤姆的1号选择是PROJECT1，其次是Project2的，那么项目3。

In this code Tom's number 1 choice is Project1, followed by Project2, then Project3.

的能力字典指定的有多少人可以参加每个项目的上限。

The capacities dictionary specifies the upper limit on how many people can join each project.

这篇关于排序人以群分的基础上投票的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！