さまざまなウェイトを使用して勝者のセットを選択するアルゴリズム

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