php - 均匀分配 "prizes"/无方差彩票的算法

Question

我的问题:我想做一个“友好”的彩票过程。如果可能，该算法将平均分配奖品。这对于每一个奖品都买票的人来说可能会被认为是不公平的，因为他会更灵活地赢得冷门奖品，但不要紧，我们可以说奖品大致相同。该算法将有助于消除方差并减少赢得奖品的掷骰子。 (是的，无聊)

我将举办 N 场比赛，你可以赢得奖品。人 M 每 N 可以买一张票。

举个例子，这里有奖品和已经买票的人:

Prize1=[Pete,Kim, Jim]
Prize2=[Jim, Kim]
Prize3=[Roger, Kim]
Prize4=[Jim]

有4个奖品，4个唯一名称，应该可以平均分配。

这个例子可能很容易解决，你应该在 15 秒内找到它，但是当 M 和 N 增加时它会变得更糟。

我正在尝试制作一个通用算法，但这很难。我需要一些好的提示，甚至更好的解决方案或解决方案的链接。

Answer 1

理论:你有一个 Bipartite graph .你必须找到一个 Perfect matching .如果满足以下条件，则图中存在完美匹配:

• |一个| = |B|
• 图表满足 Hall condition

如果存在完美匹配，您可以运行 Hungarian algorithm找到它。