1

(動機: 利用可能なプレーヤーの母集団からスポーツ チームを選択する必要がある問題を考えてみましょう。各プレーヤーには、期待される給与に正確に比例する特定のスキル レベルがあり、このスキル/給与レベルの合計が自分の目標と正確に一致するようにする必要があります。総サラリーキャップ。）

次の関数を記述する必要があります。

 bool possibleAssignment(int N, int M, int T, vector<int> H);

入力制約は次のとおりです。

  • 0 < N <= 50
  • 0 < M <= 50
  • 0 < T <= 2500
  • H.size() == N + 1
  • フォーオールi、0 <= H[i] <= M

possibleAssign は、次の 3 つの制約を使用して M 個の int の配列 X を割り当てることができる場合に true を返します。

  1. フォーオールi、0 <= X[i] <= N
  2. forallの値vを持つ の要素数は <= H[v] ですXv
  3. X の合計は T

possibleAssignを実装するには、どのアルゴリズムまたはメソッドを使用できますか?

4

1 に答える 1

3

この問題は、部分和問題から還元できるように見えます。または、よりよく知られている変種であるナップザック問題(NP 困難) であるため、既知の多項式解はありません。

ただし、T は十分に小さいようで、幸いなことに、DP を使用した問題に対する疑似多項式の解があります。

この問題はすでにナップザック問題に似ているため、ナップザック問題に適合するように問題を縮小してから、ナップザック問題の最適解を見つけるために DP アルゴリズムを呼び出します。

最初にリストをフィルタリングし、値 v を持つ H[v] 要素のみを保持します。次に、要素を次のように設定します。

value(x) = 1
weight(x) = x
Bag size = T

これでうまくいきます-給与制約Tで割り当てることができる要素の最大数が得られます

于 2012-07-03T12:33:53.090 に答える