使用不同权重选择一组获胜者的算法

Question

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

输入:

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

输出:

根据属性集及其各自的权重和值，确定一组合格的键(共 k 个)。

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

希望手头的问题是清楚的。基本上，属性的值和各自的权重将决定哪些键更有可能获胜(较高的值和较高的权重会增加该键获胜的可能性)，我们最终会选择每个人。

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

谢谢! - 阿泽姆

Answer 1

将您的权重视为线段，总线长等于权重​​之和。在 0 和该长度之间选择一个统一的随机数。获胜者是号码落入其分割市场的候选人。

移除那个获胜者，并相应地减少总行长度。然后对其余候选人重复该过程，直到您选择了您的 k。

循环结束后，重新缩放失败者以占据原始长度的大部分，并将剩余的小块平均分配给获胜者。