0

あなたがサッカーチームのコーチだと想像してみてください。プレーヤーがプレーするフィールドには、11 人のプレーヤーと 11 の異なるポジションがあります。各プレーヤーは、指定された位置で特定のレーティングを使用して、11 の異なるすべての位置でプレーすることができます。

チームのコーチであるあなたは、全体の評価 (つまり、評価の合計) が最大になるように、チーム (全 11 人のプレーヤーで構成される) で可能な限り最強の LINEUP を決定する必要があります。2 人のプレーヤーが同じポジションでプレーすることはできません。

例として、3 人のプレーヤーだけが特定のゲームをプレイする小さな LINEUP 問題を考えてみましょう。

3 2 1
4 1 5
6 7 3

プレーヤー 1 は、レーティング 3 でポジション 1、レーティング 2 でポジション 2、レーティング 1 でポジション 3 でプレーできます。最高のラインナップは、プレイヤー 1 がポジション 1、プレイヤー 2 がポジション 3、プレイヤー 3 がポジション 2 でプレーするときであり、最大レーティング = 15 (3 + 5 + 7) になります。

では、この問題は動的計画法によってどのように解決できるのでしょうか? 誰かがこの問題を DP で解決しているフォーラムを読んだことがありますが、問題がどのように最適部分構造を持っているのかわかりません。だから私がそれを理解するのを手伝ってください....

また、DP で問題を解決できるかどうかについても言及してください

そして、タイトルを適切に編集してください...

4

2 に答える 2

2

ここに割り当ての問題があると思いますが、これはハンガリーの方法で解決できます。

本当に DP ソリューションが必要な場合は、ここに 1 つのアイデアがあります。F[i,j], i=0..11,を持っていないのはなぜですかj = 0..2^11-1。i- は、選択できる選手の数です。j- は、カバーされるフィールド ポジションを表すビットマスクであり、F取得できる最大の「チーム値」です。たとえばi = 1、 の場合、jバイナリ表現の値に最大で 1 つのセット ビットが含まれる値のみが「有効」です。明らかに、1 人のプレーヤーだけで複数のポジションをコンバートすることはできません。

// initialize the F[][] array with -infinity
F[0][0] = 0;

for(i = 1; i <= 11; ++1)
{
  for(j = 0; j < 2^11; ++j)
    for(k = 0; k < 11; ++k )
    if( (j & (1 << k)) == 0 ) // k-th position is not occupied?
      F[i][j | (1 << k)] = max( F[i][j | (1 << k)], F[i-1][j] + <value of payer i playing at position k> );
}

ANSWER = F[11][2^11-1]

これは明らかに最適化できます。正確に設定さF[i]れたビットを含むビットマスクにのみ関心があるためです。i

ビットマップで可能な状態を表現することで、組み合わせ問題をDP問題に変える手法の名前がありましたが、覚えていません。これに対する適切な解決策は、依然としてハンガリーの方法です。

于 2012-12-27T07:33:26.950 に答える
0

マッチングの問題です。KMアルゴリズムを使用してそのwikiを解決できます .アレックスが言及したハンガリーの方法はKMの特殊なケースです. DP 法については、Ales が正解でした。プレイヤー数は多くないので、ここではビットマニピュレーション方式を使用できます

于 2012-12-29T03:01:55.823 に答える