5

私は500個のフロートのリストを持っています。

合計すると N になり、N が X <= N <= Y の範囲内にあるリストから 11 個の数字を選びたい

これは基本的に、人物のラインナップから 11 人の選手を自動選択するファンタジー フットボール ゲーム用です。

総コストは、ランダムではなく、範囲内のどこかにある必要があります。

1つの解決策は、合計が範囲内に収まるまで11人のプレーヤーを継続的にランダムに選択することかもしれませんが、よりエレガントなアプローチがあるかどうか疑問に思っていますか?

4

3 に答える 3

4

コメンターが指摘したように、これは NP 困難な問題です。ただし、データがそれほど悪くない場合は、次のようにするとうまくいくはずです。

picks[] := K numbers chosen at random from the population
While sum(picks) is not in the allowable range
  if sum(picks) < MinRange
    select an element p from picks at random
    let subpop := elements in population which are larger than p
    replace p with a random element from subpop
  if sum(picks) > MaxRange
    select an element p from picks at random
    let subpop := elements in population which are smaller than p
    replace p with a random element from subpop

これは非常に簡単にコーディングできます。制約を満たす比較的ランダムな選択が返されます。実際に問題の難しいインスタンスがない限り、それほど長くはかからないはずです。その場合、見つけるのは非常に困難になります。任意のアルゴリズムを使用したソリューション。

アルゴリズムを高速化したい場合は、要素を毎回p最小/最大の要素として選択できます。picksこれにより、アルゴリズムが高速化されますが、ピックの「ランダム」な選択が少なくなります。

于 2013-10-18T11:20:02.570 に答える
0

XとYとは？それらとプレーヤーのスコアを整数で近似できますか? もしそうなら、 ナップザック問題のように動的計画法を使うことができます。

しかし、いくつかの問題があります。

  1. このアルゴリズムは、O(Y) メモリと O(M + Y) 時間を必要とします。ここで、M はプレーヤーの総数です。
  2. 許容可能なすべてのチームを見つけてランダムに選択する場合、そのようなチームが指数関数的に存在する可能性があるという問題が発生します。

したがって、実用的なアプローチについては、mrip の提案に賛成です。

于 2013-10-18T14:31:30.727 に答える