algoritmo per scegliere insieme dei vincitori con pesi differenti

Question

Sto cercando di progettare un algoritmo che fa quanto segue.

Input:

Ho un mazzo di chiavi (totale n) che sono mappati al gruppo di proprietà. Le proprietà contengono il peso per ogni proprietà e il valore della proprietà.

Output:

Identificare un set di chiavi che sono qualificati (k totale) in base al set di proprietà e dei loro rispettivi pesi e valori.

Inoltre, i dati deve essere modificata in quanto tale, in ogni ciclo di scegliere i vincitori in modo tale che le probabilità di una persona che non è stato scelto va su nel ciclo successivo (mentre le probabilità che qualcuno che ha vinto sarebbe come se essi sono completamente di nuovo nel sistema).

Speriamo che la questione in mano è chiaro. In sostanza, il valore della proprietà e il rispettivo peso sarebbe determinare quali tasti sono più probabilità di vincere (un valore superiore con un peso più elevato aumenterebbe la probabilità di vincere quella chiave) e siamo alla fine finire per scegliere tutti.

Qualsiasi input su come questo può essere fatto sarebbe molto apprezzato.

Grazie! - Azeem

Answer 1

Si consideri il vostro peso come segmenti di una linea, con la lunghezza complessiva linea pari alla somma dei pesi. Scegliere un numero casuale uniforme tra 0 e tale lunghezza. Il vincitore è il candidato il cui segmento il numero cade in.

Rimuovi che il vincitore, e ridurre la lunghezza complessiva linea di conseguenza. Quindi ripetere il processo con gli altri candidati fino a quando hai scelto il tuo k.

Dopo il ciclo, ridimensionare i perdenti di occupare la maggior parte della lunghezza originale e aggiungere nuovamente i vincitori con il piccolo pezzo rimanente diviso equamente tra loro.

Answer 2

un metodo non ottimizzata ma efficace sarebbe di fare una lista di tutti i partecipanti, ma gli indici di accodamento aggiuntivi per contestest proporzionale al peso.

pseudo è totalmente fuori contesto di una vera esecuzione, ma si dovrebbe ottenere l'idea.

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