algorithm - 需要帮助找出要使用的算法

Question

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

有一组“n”个人和另一组“m”个工作坊，人数比工作坊多。每个人都选择了总研讨会中大小为“j”的子集，并根据他们愿意为该特定研讨会提供多少帮助来为每个人分配值(value)。现在，每个车间都只有有限的职位空缺。

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

将人员分配到研讨会的最佳方式是什么，以便每个人都参加她认为最有值(value)的研讨会(考虑到问题限制，也就是说，如果一个人不能参加他们的第一选择，那么算法应该选择第二个、第三个、第四个等等)。

我认为这个问题与组合优化有关，但我对算法了解不多。如果有人能告诉我可以从中开始调查的人的名字，我将不胜感激。

谢谢!请原谅我的英语。

Answer 1

这是一个单向偏好的匹配问题(从某种意义上说，人们对研讨会有偏好，但反之则不然)。

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

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

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