1

ウィキペディアでは、ナップザックのアルゴリズムは次のとおりです。 

for i from 1 to n do  
  for j from 0 to W do  
    if j >= w[i] then  
      T[i, j] := max(T[i-1, j], T[i-1, j-w[i]] + v[i]) [18]  
    else  
      T[i, j] := T[i-1, j]  
    end if  
  end for  
end for

そして、私がオンラインで見つけたすべての例で同じ構造です。私が理解できないのは、おそらく最大値がより小さなナップザック
に由来するという事実をこのコードがどのように考慮しているのかということです。たとえば、ナップザックの容量が 8 の場合、おそらく最大値は容量 7 (8 - 1) から得られます。 おそらく最大値が小さなナップザックから来ていると考えるロジックはどこにも見つかりませんでした。これは間違った考えですか？

4

2 に答える 2

5

ナップザックの動的計画法ソリューションは基本的に再帰的です。

T(i,j) = max{ T(i-1,j) ,         T(i-1,j-w[i]) + v[i] }
       //      ^                         ^
       //  ignore the element       add the element, your value is increase
       //                           by v[i] and the additional weight you can
       //                           carry is decreased by w[i]

T(i,j) = -infinity（else条件は、それぞれに設定した場合、再帰形式では冗長ですj < 0）。

アイデアは徹底的な検索です。1つの要素から開始し、2つの可能性があります。追加するかしないかです。
両方のオプションをチェックして、そのうちの最良のものを選択します。

それは再帰的に行われるので、要素をナップザックに割り当てるためのすべての可能性を効果的にチェックします。

ウィキペディアのソリューションは、基本的に同じ再帰式のボトムアップソリューションであることに注意してください

于 2013-01-03T10:47:49.837 に答える
4

お分かりのように、あなたはナップザックの概念を誤解しています。コード部分に到達するまで、ここで詳細に説明します。

まず、問題には 2 つのバージョンがあります。

  1. 0-1 ナップザック問題: ここでは、アイテムは分割できず、アイテムを取るか取らないかのどちらかです。動的計画法で解決できます。//and this one is the one yo are facing problems with
  2. フラクショナル ナップザック問題: 今は気にしないでください。

最初の問題については、次のように理解できます。

最大容量Wのナップザックと、 n 個のアイテムからなる集合Sが与えられた場合、各アイテムiには重みwiと利益値biがあります ( wi とWはすべて整数値です)。

SO、パックされたアイテムの最大の合計値を達成するためにナップザックをパックする方法は?

と数学的な口で:

ここに画像の説明を入力

動的計画法を使用してこの問題を解決するためV[0..k, 0..W]に、使用可能なアイテムごとに 1 つの行と、0からWまでの重みごとに 1 つの列を含むテーブルを設定します。下位の問題を慎重に特定する必要があります。

副問題は、 を計算することです。つまり、サイズwのナップサックで のV[k,w]最適解を見つけることです (容量wと項目1、…、k が与えられた場合に達成可能な最大値) 。Sk= {items labeled 1, 2, .. k}

そのため、この問題を解決するために次の式を見つけました。 ここに画像の説明を入力

このアルゴリズムは、ナップザックで運ぶことができる最大値、つまり V[n,W] の値のみを見つけます。この最大値を作るアイテムを知るには、これは別のトピックになります。

この回答がお役に立てば幸いです。テーブルに記入し、アルゴリズムを段階的に示すためにあなたと一緒に歩くppプレゼンテーションがあります. しかし、それをstackoverflowにアップロードする方法がわかりません。助けが必要な場合はお知らせください。

于 2013-01-03T16:05:59.323 に答える