开放空间坐姿优化算法

Question

由于公司的变化,我们必须重新安排我们的坐姿:一个房间有10个办公桌.出于多种原因,一些办公桌比其他办公桌更受欢迎.一种解决方案是从帽子中抽出一个桌号.我们认为有更好的方法.

我们有10个办公桌和10个人.让我们为这场比赛中的每个人提供50个假设的代币,以便在桌子上出价.你在一张桌子上出价的数量没有限制,你可以把全部50张,这就是说"我只想坐在这里,期间".你也可以通过给每张桌子5个代币说"我不在乎".

重要提示:没有人知道其他人在做什么.每个人都必须根据他/她的最佳利益来决定(听起来很熟悉吗？)

现在我们假设我们获得了这些假设的结果:

#  | Desk# >| 1  | 2  | 3  | 4  | 5  | 6  | 7  | 8  | 9  | 10 |
1  | Alise  | 30 | 2  | 2  | 1  | 0  | 0  | 0  | 15 | 0  | 0  | = 50
2  | Bob    | 20 | 15 | 0  | 10 | 1  | 1  | 1  | 1  | 1  | 0  | = 50
   ...
10 | Zed    | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | 5  | = 50

现在,我们需要找到的是一个(或多个)配置,它们给我们最大的满足感(即人们得到他们想要的办公桌,考虑所有的出价,并最大化集团的总数.当然,假设是桌面越多,他/她想要的就越多.

由于只有10个人,我认为我们可以强行查看所有可能的配置,但我想知道有更好的算法来解决这类问题？

Answer 1

您似乎正在研究可以使用匈牙利算法解决的分配问题。这是一个经过充分研究的问题，您可能会在网络上找到可供使用的代码。

在您的情况下，您可以使用 cost = 50 - bid 并使用上述内容（分配问题的任何解决方案）。