17

ナップザックを最適に満たす動的計画法アルゴリズムは、ナップザックが 1 つの場合にうまく機能します。しかし、2 つのナップザックを最適に満たす効率的な既知のアルゴリズムはありますか (容量は等しくなくてもかまいません)。

次の 2 つの方法を試しましたが、どちらも正しくありません。

  1. まず、元の DP アルゴリズムを使用して最初のナップザックを満たし、1 つのナップザックを満たし、次に他のナップザックを満たします。
  2. 最初にサイズ W1 + W2 のナップザックに水を入れ、次に溶液を 2 つの溶液に分割します (ここで、W1 と W2 は 2 つのナップザックの容量です)。

問題文 (ウィキペディアのナップザック問題も参照):

  1. 総重量がナップザックのサイズ以下でありながら、アイテムから得られる価値を最大化するために、ナップザックに一連のアイテム (各アイテムには重量と値があります) を入れる必要があります。

  2. アイテムを複数回使用することはできません。

  3. アイテムの一部を使用することはできません。アイテムの端数を取ることはできません。(すべての項目が完全に含まれているかどうかのいずれかである必要があります)。
4

3 に答える 3

11

n各アイテムは 1 回しか使用できないと仮定し、利益を最大化する必要があります。

オリジナルナップサックはdp[i] = best profit you can obtain for weight i

for i = 1 to n do
  for w = maxW down to a[i].weight do
    if dp[w] < dp[w - a[i].weight] + a[i].gain
      dp[w] = dp[w - a[i].weight] + a[i].gain

さて、ナップザックが 2 つあるので、dp[i, j] = best profit you can obtain for weight i in knapsack 1 and j in knapsack 2

for i = 1 to n do
  for w1 = maxW1 down to a[i].weight do
    for w2 = maxW2 down to a[i].weight do
      dp[w1, w2] = max
                   {
                       dp[w1, w2], <- we already have the best choice for this pair
                       dp[w1 - a[i].weight, w2] + a[i].gain <- put in knapsack 1
                       dp[w1, w2 - a[i].weight] + a[i].gain <- put in knapsack 2
                   }

時間計算量はO(n * maxW1 * maxW2)で、maxWはナップザックが運べる最大重量です。容量が大きい場合、これはあまり効率的ではないことに注意してください。

于 2013-02-09T12:57:42.473 に答える
1

元の DP は、ナップサックで取得できる値を dp 配列にマークすることを前提としており、その結果、要素を考慮して更新が行われます。
2 つのナップザックの場合、2 次元の動的配列を使用できるため、重みiを最初に配置し、重みjを 2 番目のナップザックに配置できる場合、 dp[ i ][ j ] = 1となります。更新は元の DP ケースと同様です。

于 2013-02-09T10:29:37.623 に答える