Algorithmus Satz von Gewinner auszusuchen verschiedenen Gewichten

Question

Ich bin versucht, einen Algorithmus zu entwickeln, die die folgenden.

Input:

Ich habe eine Reihe von Tasten (gesamt n), der Reihe von Eigenschaften zugeordnet werden. Die Eigenschaften enthalten das Gewicht für jede Eigenschaft und den Wert für die Eigenschaft.

Ausgabe:

Identifizieren eines Satzes von Schlüsseln, die qualifizierten (total k) basieren auf dem Satz von Eigenschaften und ihrer jeweiligen Gewichte und Werte.

Darüber hinaus sollten die Daten als so modifiziert werden, in jedem Zyklus des Gewinners, so dass die Chancen, dass jemand der Wahl, die nicht gewählt wurde, im nächsten Zyklus nach oben gehen (während der Chancen von jemandem, der gewonnen hat, wäre, als ob sie vollständig sind neu im System).

Hoffentlich wird die Frage auf der Hand, ist klar. Grundsätzlich ist der Wert der Immobilie und das jeweilige Gewicht würden bestimmen, welche Tasten sind eher (einen höheren Wert mit einem höheren Gewicht würde die Wahrscheinlichkeit dieses Schlüssels erhöhen gewinnen), um zu gewinnen und wir werden schließlich die Wahl jedem am Ende.

Jede Eingabe, wie kann dies geschehen würde sehr geschätzt werden.

Danke! - Azeem

Answer 1

Betrachten Sie Ihre Gewichte als Segmente einer Linie, wobei die Länge Gesamtleitung gleich der Summe der Gewichte. Wählen Sie eine einheitliche Zufallszahl zwischen 0 und dieser Länge. Der Gewinner ist der Kandidat, dessen Segment der Zahl fällt.

entfernen, dass die Gewinner, und reduziert die Gesamtleitungslänge entsprechend. Dann wiederholen Sie den Vorgang mit den verbleibenden Kandidaten, bis Sie Ihre k gewählt haben.

Nach dem Zyklus rescale die Verlierer der meisten der ursprünglichen Länge zu besetzen und die Gewinner mit den verbleibenden kleinen Brocken gleichmäßig zwischen ihnen aufgeteilt hinzufügen zurück.

Answer 2

eine nicht optimiert, aber effektive Methode würde eine Liste aller Teilnehmer zu machen, aber append zusätzliche Indizes für contestest proportional zum Gewicht.

psuedo ist völlig aus dem Zusammenhang einer echten Implementierung, aber man sollte die Idee.

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