算法使用不同的权重挑选优胜者

Question

我正在尝试设计一种执行以下操作的算法。

输入：

我有一组键（总n）映射到一组属性。该属性包含每个属性的权重和属性的值。

输出：

根据属性集及其各自的权重和值确定一组合格的密钥（总k）。

此外，应该在选择获奖者的每个周期中对数据进行修改，以便在下一个周期中没有选择的人的机会（而赢得胜利的人的机会就好像他们在系统）。

希望手头的问题很明确。基本上，物业的价值和各自的权重将确定哪些键更可能获胜（更高的重量价值会增加该键获胜的可能性），我们最终将最终选择所有人。

对如何完成此操作的任何意见将不胜感激。

谢谢！ -Azeem

Answer 1

将您的权重视为一条线段，总线长度等于权重的总和。选择一个均匀的随机数在0和该长度之间。获胜者是候选人，该候选人的数字属于。

删除该获胜者，并相应地减少整个线路长度。然后与其余候选人重复该过程，直到您选择了 k.

周期结束后，重新生命失败者占据了大部分原始长度，并将剩余的小块均匀地分配给他们的大部分原始长度。

Answer 2

一种不优化但有效的方法将列出所有参赛者，但要附加与重量成正比的竞赛索引。

psuedo完全不在任何实际实现的上下文中，但是您应该理解这个想法。

const int DEFAULT_WEIGHT = 1;
public List<Contestant> items = new List<Contestant>();
public List<Guid> LotteryPool = new List<int>();

public Contestant Roll()
{
     Random rnd = new Random();
     rnd.Seed = DateTime.Now.Ticks;

     // Generate LotteryPool
     foreach(Contestant item in items)
     {
              for(int i = 0; i < item.Weight; i++)
              {
                       LotteryPool.Add(item.Id);
              }

              item.Weight++;
     }

     // Find the contestant matching a random id from the pool.
     Contestant result = FindContestant(LotteryPool[rnd.Next(0, LotterPool.Count]);

     // apply the default weight the winner
     result.Weight = DEFAULT_WEIGHT;

     return result;
}