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

输入:

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

输出:

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

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

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

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

谢谢! -Azeem

有帮助吗?

解决方案

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

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

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

其他提示

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

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;
}
许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top