7

次のことを行うアルゴリズムが必要です。

NBA ファンタジー リーグでは、以下が与えられます。

  1. 各プレイヤーの平均ポイント合計
  2. 各プレーヤーの価格
  3. サラリーキャップ

最適な 9 人のプレーヤー ラインナップを選択します。

簡単な例を挙げると、リーグに 4 人のプレーヤーしかなく、サラリー キャップが $10,000 で、最適な (最大ポイントを意味する) 3 プレーヤー ラインナップが必要であるとします。平均ポイントの合計と価格は次のとおりです。

レブロン ジェームズ: 30 ポイント/ゲーム。$5,000
コービー・ブライアント: 25 ポイント/ゲーム; $3,500
Deron Williams: 20 ポイント/ゲーム; $2,500
シェルビン マック: 15 ポイント/ゲーム; $2,000

最適なラインナップは、ブライアント、ウィリアムズ、マックで、費用は 8,000 ドルで、スコアは 60 ポイントです。

さらに 1 つの制約があります。プログラムは、各ポジションに対して特定の数のプレーヤーを選択する必要があります (たとえば、ポイント ガード 2 名、シューティング ガード 2 名、スモール フォワード 2 名、パワー フォワード 2 名、センター 1 名)。これがプログラムの設計を難しくしている原因です。

4

2 に答える 2

5

まず、問題の一般化がNP-Hardであり、ナップザック問題から即座に還元可能であることは簡単にわかります。

ナップザックの問題: が与えられた場合weight=W, costs_of_items=C, weight_of_items=X、プレイヤー数に制限のないこの問題に問題を減らします (一般化は、プレイヤーが選択した最大kプレイヤー数になりkます)。

したがって、問題に対する既知の多項式時間解はないと結論付けることができます。

しかし、ナップザック疑似多項式解に基づいて解を開発できます。
簡単にするために、スモール フォワードの数だけに制限があるとしましょう (回答の原則を適用して、さらに制限を追加できます)。

次に、次の再帰的アプローチで問題を解決できます。

if i is not a forward, same as the original knapsack, while maintaining the #forwards
    f(i,points,forwards) = max {
                f(i-1,points-C[i],forwards)
                f(i-1,points,forwards)
                           }
if i is a forward:
    f(i,points,forwards) = max {
                //We used one of the forwards if we add this forward to the team
                f(i-1,points-C[i],forwards-1) 
                f(i-1,points,forwards)
                           }

ベースはすべてゼロで、次元の 1 つがゼロです: f(0,_,_)=f(_,0,_)=0(通常のナップザックと同じ) およびf(_,_,-1)=-infnity(無効なソリューション)

答えはf(2,W,n)(転送数が 2 で、異なる場合はそれも変更する必要があります) です。Wはサラリーキャップで、nは選手数です。

DP ソリューションは、再帰ボトムアップを表す行列を埋めて、疑似多項式時間ソリューションを取得します (制限が一定の場合にのみ疑似多項式です)。

このプロセスを繰り返し、各基準にディメンションを追加することで、この問題は DP ソリューションによって最適に解決されます。

得られる複雑さは次のとおりですO(B^p * W * n)- ここで:
Bは「分岐係数」です - ポジションごとのプレーヤー数 + 1 (ゼロの場合)B=3です。
W= サラリーキャップ
n= 選択する選手の数

最適解に時間がかかりすぎると感じた場合は、ヒル クライミングや遺伝的アルゴリズムなどのヒューリスティック ソリューションを使用することをお勧めします。これは、可能な限り結果を最適化しようとしますが、グローバルな最大値を見つける保証はありません。

于 2012-10-31T12:45:13.513 に答える
1

動的計画法を使用すると、これを簡単に解決できます。これを参照してください

最初のプレーヤーでドルを使用しf[i][j]て取得できる最大ポイントをji

f[i][j] = 最大{

  1. f[i - 1][j] //i 番目のプレイヤーは選択しません
  2. f[i - 1][j - cost[i]] + point[i] //彼を選ぶ

}

最後f[TOTALPLAYER][MONEYCAP]に答えです。

主なアイデアは、各プレーヤーに対して彼を選択するかどうかを決定することです。

配列f[][]は、検索プロセスを高速化するために使用されます。

ところで、Chowlettは正しいです。

于 2012-10-31T12:06:08.177 に答える