5

したがって、練習用の質問では、0/1ナップサック問題のバリエーションである動的計画法アルゴリズムを設計することになっています...基本的に、各アイテムは4つの異なるソースから取得され、そのアイテムは1つのソースからのみ取得できます。 。

つまり、

S1={(d_k, b_k) | 1 ≤ k ≤ n},
S2={(d_k, b_k) | n + 1 ≤ k ≤ 2n},
S3={(d_k, b_k) | 2n + 1 ≤ k ≤ 3n},
S4 = {(d_k, b_k) | 3n + 1 ≤ k ≤ 4n}

のために、あなたが置くn = 10ことを選択した場合、それはあなたが選択しないことを意味します...i = 166, 26 or 36

この問題を解決し、漸化式を考案するのを手伝ってもらえますか？

4

2 に答える 2

8

4n個の要素があります。

表記：

  • V[k]-要素kの値（1 <= k <= 4n）
  • W[k]-要素kの重み（1 <= k <= 4n）
  • B-限界
  • f(k,B)-境界がBで、4k要素がある場合の最適解の値。

k番目の要素には、次の5つの選択肢があります。

  1. k番目の要素をナップザックに挿入していません。その制約の下で、最適解の値はですf(k-1,B)。なんで？k-1個の要素があり、境界はまだBであるためです。
  2. S1からk番目の要素を取得します。その制約の下で、最適解の値はですV[k] + f(k-1, B - W[k])。なんで？k番目の要素とウエストW[k]でV[k]を獲得しました。したがって、残りの要素については、f（k-1、B-W [k]）を獲得します。
  3. S2からk番目の要素を取得します。前と同じロジックを使用して、その制約の下での最適解の値がであるかどうかを確認しますV[k+n] + f(k-1, B - W[k+n])。
  4. S3からn番目の要素を取得します。最適：V[k+2n] + f(k-1, B - W[k+2n])。
  5. S4からn番目の要素を取得します。最適：V[k+3n] + f(k-1, B - W[k+3n])。

あなたの目的はfを最大化することです。したがって、漸化式は次のようになります。

f(k, B) =
   max { 
        f(k-1,B),                      //you don't take item n
        V[k]    + f(k-1, B - W[k]),    //you take item k from S1
        V[k+n]  + f(k-1, B - W[k+n]),  //you take item k from S2
        V[k+2n] + f(k-1, B - W[k+2n]), //you take item k from S3
        V[k+3n] + f(k-1, B - W[k+3n])  //you take item k from S2
   }

残っているのは、初期条件を見つけることです。

于 2011-03-20T22:00:31.170 に答える
3

標準の0/1ナップサック問題：アイテムごとに、服用しないか、服用します。

あなたの問題：各アイテムについて、あなたはそれを受け取らないか、あなたはそれをソース1から取るか、または...、またはあなたはそれをソース4から取るかのどちらかです。

次に、0/1ナップサック問題の通常の動的計画法アルゴリズムと漸化式を見てください。漸化式のRHSの各ビットがどこから来ているかを見てください。上記の最初のステートメントに対応します。代わりに、上記の2番目のステートメントを使用するように調整してください。

（私が少し謎めいているのなら、これは宿題であり、あなたは学ぶことを意図しているからです:-)）

于 2011-03-20T21:43:35.497 に答える