算法实现均匀分配奖品/无方差彩票

Question

3

我的问题：我想要一个“友善”的抽奖过程。如果可能的话，这个算法将平均分配奖品。对于那些为每个奖品购买彩票的人来说，这可能被认为是不公平的，因为他们更灵活地赢得不受欢迎的奖品，但是无论如何，我们可以说奖品大致相同。该算法将有助于消除方差并减少掷骰子赢取奖品的机会。（是的，很无聊）

我将有N个比赛，您可以赢得奖品。M个人可以为每个N购买一张彩票。

以下是奖品和已购买彩票的人的示例：

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

有4个奖品和4个独特的名字，因此应该可以平均分配。

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

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

- Martin F

你要找的词是“奖品”，而不是“价格”，这样你就知道了。有点让我困惑。 - Phoenix

那么你应该如何分配奖品呢？ - flight

通过指定他们可以赢得的奖品，每个人都可以确保赢得x个奖品——其余的必须通过随机抽奖分配。 - Martin F

2个回答

0

你想要寻找一种工作分配算法，或者匈牙利算法，例如在二分图中的加权完美匹配，或者可能是所有对之间的 Floyd Warshall 算法。我的想法是，这可以表示为一个二分图。这不是一个容易解决的任务。

- Micromega

谢谢，我同意你的看法。我提出了一个暴力解决方案，它很糟糕，哈哈。高效的CPU正在让我们变得愚蠢 :D - Martin F

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- erenon · Accepted Answer

理论：你有一个二分图。你必须找到一个完美匹配。如果满足以下条件，则图中存在完美匹配：

如果存在完美匹配，你可以运行匈牙利算法来找到它。