алгоритм выбора набор победителей с использованием разных весов

Question

Я пытаюсь разработать алгоритм, который делает следующее.

Вход:

У меня есть набор клавиш (Total N), которые сопоставлены на набор свойств. Свойства содержат вес для каждого свойства и значение для свойства.

Выход:

Определите набор ключевых ключей (Total K) на основе набора свойств и их соответствующих весов и значений.

Кроме того, данные должны быть изменены как таковые в каждом цикле выбора победителей, такие что шансы кого-то, кто не был выбран в следующем цикле (в то время как шансы на кого-то, кто выиграл, как будто они были совершенно новыми в система).

Надеюсь, проблема под рукой ясна. По сути, значение свойства и соответствующего веса определит, какие ключи чаще выиграют (более высокое значение с более высоким весом, увеличит вероятность того, что выигрывает ключей), и мы в конечном итоге в конечном итоге выбираем всех.

Любой вклад о том, как это можно сделать, было бы очень оценено.

Спасибо! - Азеем

Answer 1

Рассмотрим ваши весы как сегменты линии, с общей длиной линии, равной сумме весов. Выберите равномерное случайное число между 0 и этой длиной. Победитель - кандидат, чей сегмент в падении.

Удалите этот победитель и соответствующим образом уменьшите общую длину линии. Затем повторите процесс с остальными кандидатами, пока вы не выбрали k.

После цикла повторно вскаскайте проигравших, чтобы занять большую часть первоначальной длины и добавить своих победителей с оставшимся небольшим кусочком, разделенным равномерно между ними.

Answer 2

Неотверженный, но эффективный метод будет составить список всех участников, но добавив дополнительные индексы для конкурсерных пропорциональных веса.

PSEUDEO полностью выходит из контекста любой реальной реализации, но вы должны получить идею.

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