算法來選擇使用不同權重的獲勝者集合

Question

我試圖設計一個算法，它可以執行以下操作。

輸入：

我有一組被映射到設置屬性的鍵（總共n）的。這些屬性包含每個屬性的權重和屬性的值。

輸出：

確定基於所設定的屬性和它們各自的權重和值的一組鍵的那些合格的（總K）。

此外，在選擇獲勝者的每個週期中都應該修改數據，以便未被選中的人的機會在下一個週期中上升（而獲勝的人的機會就好像他們是全新的系統）。

希望手頭的問題很明確。基本上，財產的價值和各自的權重將決定哪些鑰匙更有可能贏得（更高的價值和更高的重量會增加贏得鑰匙的可能性），我們最終會選擇每個人。

任何有關如何做到這一點的輸入將不勝感激。

謝謝！ - Azeem

Answer 1

考慮你的權重作爲一行的段，總行長度等於權重的總和。從0到那個長度之間選擇一個統一的隨機數。獲勝者是數字所屬的候選人。

刪除該獲勝者，並相應地縮短總體線條長度。然後重複與剩下的候選人的過程，直到你選擇你的k。

循環後，重新調整輸家以佔據原始長度的大部分，並將剩下的小塊平均分配給他們。

Answer 2

一個未經優化但有效的方法會列出所有參賽者的名單，但會追加與競爭力成比例的額外索引。

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