基于权重的随机元素挑选

Question

假设我们有一个名称和权重的数组

就像这样

简5约翰3丹0无名氏1

如果权重为0，则丹恩的名字应该比权重为1的时候显示1/10的时间

其余的是成比例的。

所以名字简会比无名氏多出现5次

最大权重为10

我正在考虑一种有效的算法来根据它们的权重来选择名字。

我目前所做的就是将权重转换成一个非常大的数组。

所以Dane会有一个入口。简将有50个条目。然后我随机挑选每个条目机会相等的地方。

我正在使用PhP。

我想知道是否有更有效的方法。

Answer 1

您可以使用以下步骤:首先，将所有权重的值求和。

其次，生成1和求和之间的随机数。

现在，我们有一个随机数，它小于或等于所有权重的总和。但我们需要其中一个权重。此外，它应该有更高的机会获得更高的权重。

我们可以通过从生成的随机数中逐个减去所有权重来做到这一点。如果结果值是非负的，则它可能具有较低的权重。如果结果值为负，则它应该是一个更高权重的元素。