最大化幸福的算法

Question

假设您有:

• 100 人
• 100 个项目

每个人都按照他们希望从事的顺序对所有 100 个项目进行排序。什么样的算法可以用来最大化人们的幸福感(即被分配到他们排名更高的项目转化为更大的幸福感)。

假设每个人一个项目。

Answer 1

这类问题的算法非常流行，被称为匈牙利算法。用这类问题解决的类似问题:

We consider an example where four jobs (J1, J2, J3, and J4) need to be executed by four workers (W1, W2, W3, and W4), one job per worker. The matrix below shows the cost of assigning a certain worker to a certain job. The objective is to minimize the total cost of the assignment.

来源:http://www.hungarianalgorithm.com/examplehungarianalgorithm.php

请注意，默认的匈牙利算法会找到最小成本，但您可以更改程序以使其以最大化成本的方式运行。

If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.

来源:http://en.wikipedia.org/wiki/Hungarian_algorithm

我已经在我的 Github 上实现了匈牙利算法, 所以请随意使用它并修改它以使其发挥最大的成本。