2

バスケットボール選手とその名前、ポジション、コスト、および予測ポイントを表すタプルのリストがあるとします。

listOfPlayers = [
                 ("Player1","PG",Cost,projectedPoints),
                 ("Player2","PG",Cost,projectedPoints),
                 ("Player3","SG",Cost,projectedPoints),
                 ("Player4","SG",Cost,projectedPoints),
                 ("Player5","SF",Cost,projectedPoints),
                 ("Player6","SF",Cost,projectedPoints),
                 ("Player7","PF",Cost,projectedPoints),
                 ("Player8","PF",Cost,projectedPoints),
                 ("Player9","C",Cost,projectedPoints),
                 ("Player10","C",Cost,projectedPoints) 
                ]

すべての名前、コスト、および予測ポイントが変数であると仮定します。

私は伝統的なナップザックの問題を抱えています.彼らは与えられた重量に基づいてナップザックを分類して梱包することができます. しかし、これはポジションを考慮していません。
ナップザックのコードを編集して、すべての位置 (pg、sg、sf、pf、c) のうちの 1 つだけを含める方法があるかどうか疑問に思っていました。

従来の 0/1 ナップザックでこれを行うことができますか、それとも別のものに切り替える必要がありますか?

4

2 に答える 2

5

これは「複数選択ナップザック問題」と呼ばれます。

0/1 ナップザック問題の動的計画法と同様のアルゴリズムを使用できます。

0/1 ナップザック問題の解は次のとおりです: (ウィキペディアより)

までのアイテムm[i, w]を使用して、以下の重量で達成できる最大値と定義します。次のように再帰的に 定義できます。wi
m[i, w]

m[i, w] = m[i-1, w] if w_i > w   (new item is more than current weight limit)
m[i, w] = max(m[i-1, w], m[i-1, w-w_i] + v_i) if w_i <= w.

を計算することで解を求めることができますm[n,W]。これを効率的に行うために、テーブルを使用して以前の計算を保存できます。

現在の拡張機能は、代わりにすべての選択肢の最大値を見つけることです。

あるポジションのn選択肢として利用可能なプレーヤーi(c_i_j選択のコストとjポイントp_i_j) の場合、次のようになります。

m[i, c] = max(m[i-1, c],
              m[i-1, c-c_i_1] + p_i_1   if c_i_1 <= c, otherwise 0,
              m[i-1, c-c_i_2] + p_i_2   if c_i_2 <= c, otherwise 0,
              ...
              m[i-1, c-c_i_n] + p_i_n   if c_i_n <= c, otherwise 0)

だから、私たちが持っているとしましょう：

Name     Position  Cost  Points
Player1  PG        15    5
Player2  PG        20    10
Player3  SG        9     7
Player4  SG        8     6

次に、「PG」と「SG」の 2 つの位置があり、各位置には 2 つの選択肢があります。

したがって、位置 "PG" (でi=1) については、次のようになります。

m[i, c] = max(m[i-1, c],
              m[i-1, c-15] + 5    if 15 <= c, otherwise 0,
              m[i-1, c-20] + 10   if 20 <= c, otherwise 0)

そして、ポジション「SG」（でi=2）については、次のようになります。

m[i, c] = max(m[i-1, c],
              m[i-1, c-9] + 7    if 9 <= c, otherwise 0,
              m[i-1, c-8] + 6    if 8 <= c, otherwise 0)
于 2013-10-16T10:31:58.460 に答える