我需要带有权重选项的随机算法

本文介绍了我需要带有权重选项的随机算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

I have a requirement in my .NET project where I need to select an item from a collection, each item has a Weight (integer from 1 to 10) assigned to it.

我需要一个随机发生器，该发生器将考虑此权重，即，权重越高，选择对象的机会就越大。

I need a random generator that would take this weight into consideration i.e., the higher the weight, the more chances the object would be selected.

快速复制/

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)]; } }

推荐答案

一种不需要将项目多次添加到列表的算法。它也可以使用非整数权重，尽管如果您使用System.Random中的NextDouble，则必须缩放所有权重以将其总和增加1，或者将NextDouble的值乘以S才能得到

Here's an algorithm which doesn't require adding the items multiple times to a list. It can also work with non-integer weights, although if you're using NextDouble from System.Random, you'll have to scale all of the weights to add up to 1, or multiply the value from NextDouble with S to get it in the desired range.

给出一个项目L的列表（I，W），其中I是项目，W是权重：

Given a list L of items (I,W), where I is the item and W is the weight:

将所有权重加在一起。将此总和称为S。

生成一个介于0和S之间的随机数（不包括S，但包括0）。将此值称为R。

将变量初始化为0，以跟踪运行总计。

对于L中的每个项目（I，W）：

Add all of the weights together. Call this sum S.

Generate a random number between 0 and S (excluding S, but including 0). Call this value R.

Initialize a variable to 0 to keep track of the running total. We'll call this T.

For each item (I,W) in L:

T = T + W

如果T> R，则返回I。