c# - 我需要带有称重选项的随机算法

Question

我在我的 .NET 项目中有一个要求，我需要从集合中选择一个项目，每个项目都有一个分配给它的权重(1 到 10 之间的整数)。

我需要一个随机生成器来考虑这个权重，即权重越高，对象被选中的机会就越大。

快速复制/粘贴 C# 代码以防有人偶然发现。

    class RandomWeightedSelector<T>
    {
        private List<T> items = new List<T>();

        public void Add(T item, uint weight = 1)
        {
            for (int i = 0; i < weight; i++)
                items.Add(item);
        }

        public T GetRandom()
        {
            return items[new Random().Next(0, items.Count)];
        }
    }

Answer 1

这是一个不需要将项目多次添加到列表中的算法。它也可以使用非整数权重，但如果您使用 System.Random 中的 NextDouble，则必须缩放所有权重以加起来为 1，或者将 NextDouble 中的值乘以 S 以得到它所需的范围。

给定一个包含项目 (I,W) 的列表 L，其中 I 是项目，W 是权重:

1. 将所有权重相加。称此总和为 S。
2. 生成一个介于0和S之间的随机数(不包括S，但包括0)。将此值称为 R。
3. 将变量初始化为 0 以跟踪运行总计。我们将其称为 T。
4. 对于 L 中的每个项目 (I,W):
   1. T=T+W
   2. 如果 T > R，返回 I。