0

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

输入：

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

输出：

根据一组属性及其各自的权重和值，识别一组合格的键（总共 k 个）。

此外，在选择获胜者的每个周期中都应该修改数据，以便在下一个周期中未被选中的人的机会增加（而获胜的人的机会就好像他们在系统）。

希望手头的问题很清楚。基本上，财产的价值和各自的权重将决定哪些钥匙更有可能获胜（权重越高的价值越高，该钥匙获胜的概率就会增加），我们最终会选择每个人。

任何关于如何做到这一点的意见将不胜感激。

谢谢！- 阿泽姆

4

2 回答 2

1

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

删除该获胜者，并相应地减少总行长。然后对剩下的候选人重复这个过程，直到你选择了你的k.

在循环之后，重新调整失败者以占据大部分原始长度，然后将剩余的小块平均分配给获胜者。

于 2010-10-18T17:22:39.863 回答
0

一种未优化但有效的方法是列出所有参赛者，但为参赛者附加与体重成比例的附加索引。

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;
}
于 2010-10-18T17:11:39.250 回答