2

我需要一种算法来解决以下条件的问题:

有一组“n”个人和另一组“m”个车间,人比车间多。每个人都选择了所有研讨会的大小为“j”的子集,并根据他们希望帮助该特定研讨会的程度为每个人分配值。现在,每个车间只有有限的职位空缺。

鉴于这些条件,问题将是:

将人员分配到研讨会的最佳方式是什么,以便每个人都参加她认为最有价值的研讨会(给定问题约束,即如果一个人不能参加他们的第一选择,那么算法应该选择第二,第三,第四,等等)。

我认为这个问题与组合优化有关,但我对算法知之甚少。如果有人能告诉我开始调查的人的名字,我将非常感激。

谢谢!请原谅我的英语。

4

1 回答 1

0

这是一个与片面偏好匹配的问题(从某种意义上说,人们对研讨会有偏好,但不是相反)。

这是一篇出色的论文,更详细地讨论了这个问题:https ://mattmccutchen.net/lumc/index.html

这个问题的最佳解决方案不是特别清楚。有许多不同的最优(帕累托有效)准则。不幸的是,对于他们中的许多人来说,这个问题是 NP 难的。

但是,多项式时间算法有标准。在我链接的论文的“相关工作”部分中有一个很好的列表。

于 2012-04-17T20:21:08.040 回答