1. 概要

ナップサック問題は、古くて人気のある最適化問題です。 このチュートリアルでは、ナップサック問題のさまざまな変形を見て、0-1の変形について詳しく説明します。

さらに、それが NP完全問題である理由を説明し、疑似多項式時間でそれを解決するための動的計画法を提示します。

2. 一般的な定義

重み制限がのナップサック、値と重みを持つアイテムのコレクションが与えられた場合、ナップサック問題は最適化問題として定義されます。

   

   

さて、問題は、重量が重量制限を超えないようにナップザックに追加できるアイテムの最大値はいくつですか

3. ナップサック問題の変種

定義方法に応じて、上記のナップサック問題には3つのバリエーションがあります。 このセクションでは、この問題のこれらの変形について説明します。

3.1. 0-1ナップサック問題

このバリアントでは、アイテムは次のように定義されます。

ここでは、利用可能な各アイテムが1つだけあります。 つまり、の場合、アイテムはナップザックに追加されないことを意味します。 の場合、アイテムがナップザックに追加されたことを意味します。

3.2. 有界ナップサック問題

この場合、アイテムは次の条件によって制限されます。

変数は、各アイテムの使用可能なコピーの数を示します。

3.3. 無制限のナップサック問題

ここでは、アイテムは次の形式になっています。

無制限のナップザックでは、アイテムの数に制限はありません。 利用可能な各アイテムの無制限のコピーがあります。

4. なぜ0-1ナップサック問題はNP完全なのですか?

0-1ナップサック問題の決定バージョンは、NP-Complete問題です。 理由を見てみましょう。

アイテムの重みと値、およびがそれぞれ与えられた場合、次の制約を満たすアイテムのサブセットを選択できます。

   

   

上記の決定問題に対する「はい」または「いいえ」の解決策はNP完全です。 上記の不等式を解くことは、NP完全であることが証明されているサブセット和問題を解くことと同じです。 したがって、ナップサック問題は、多項式時間でサブセット和問題に還元できます。

さらに、この問題の複雑さは、入力値のサイズに依存します。 つまり、値を四捨五入して制限を強化する方法がある場合は、多項式時間アルゴリズムを使用します。

これは、アルゴリズムの非決定論的な部分が入力のサイズにあるということです。 入力がバイナリの場合、その複雑さは指数関数的になるため、NP完全問題になります。

5. 動的計画法アルゴリズム

このセクションでは、0-1ナップサック問題を解くための動的計画法のアプローチについて説明します。

まず、その擬似コードを提示しましょう。

ここで、最初に、アルゴリズムはサイズの行列を作成します。

すべてのエントリは、特定の重量制限とアイテムでナップザックが取ることができる最大値を示します。 可能なすべての重み(列に沿って)を重みの制限まで繰り返してから、新しいアイテム(次の行)を選択して、ナップザックの値がどのように増加するかを確認します。

マトリックス内の任意の位置で最大値を計算するには、次のようにします。

  • もしも :
  • もしも :

この関数は、現在の位置の真上の位置の値を示し、アイテムを追加せずにチェックし、現在のアイテムが追加されている場合はナップザックの値を表示します。

一般的な考え方は、現在のアイテム、つまりアイテムを選択することです(上記の関数の最初の項が2番目の項よりも大きい場合は、特定の重み制限に対して)。 第2項は、アイテムを選択しない場合の耐荷重での合計値を表します。

6. 例

ここで、0-1ナップサック問題の動的アプローチについて説明したので、例でアルゴリズムを実行してみましょう。

持ち運びできるのは買い物袋のみです。 バッグ内のすべてのアイテムを合わせた最大値(ここではカロリーなど)を見つけることに関心があります。

この例では、重みと値をすでに定義しています。

   

   

ここで、アルゴリズムによれば、最初のステップは、最初の行と最初の列のエントリをゼロにした行列を初期化することです。

行列の初期化後、反復ステップを開始します。

最初のループを始めましょう。 値について::

   

   

その間隔で次の理由で確認できます。

   

   

結果について表で説明しましょう。 最初の列はです。 これは、総重量がである場合、どのアイテムを選択しても、最大ナップザック値は常にであることを意味します。

次に、重みがに等しいことを選択します。 の値を使用すると、取得できる最大値はです。 したがって、すべての行に最大ナップザック値のを入力しました。

それでは、2番目のループを開始しましょう。

値について:

   

他の値については、の値を増やし、他のすべてを変更しないようにします。 次の値でループを開始します。

   

関数内には、アイテム#を選択する(この場合、アイテム#の値が追加される)か、そのままにするかの2つの選択肢がありました。

繰り返しますが、:

   

その間隔で:

   

   

この表では、容量がで、アイテムの重量がである場合、アイテムを選択することはできません。 したがって、容量がに等しい場合、最大ナップザック値は更新されません。 残りの容量値については、最大ナップザック容量値が式によって更新されます。

反復を続けて、の値を増やしましょう。 値について:

   

ここで、の値を増やしてループを実行する必要があります。

   

   

   

ここで、重量。 したがって、このアイテムを選択して、行のすべての値を更新します。

繰り返しを続けましょう。 さて、値について:

   

繰り返しますが、値については:

   

   

   

   

   

   

   

   

   

ここでの現在の重みはです。 そのため、容量値とについては、この項目を選択できません。 したがって、容量との場合、最大ナップザック容量の値は変更されません。 その他の容量値については、項目を選択して最大容量値を変更します。

の値を増やして反復を実行する時が来ました。 したがって、ループ内の値:

   

の値を増やす必要がありますが、それ以外はすべて変更されていません。 したがって、:

   

   

   

   

   

   

   

   

   

最後に、アイテムの重量がである場合、容量値がである値を更新できます。

最後に、反復が完了しました。 結果として、重量制限が kgsの場合、 、最大ナップザック値になります。

7. 時間計算量分析

このセクションでは、動的計画法アルゴリズムの時間計算量を分析してみましょう。

関数の最初の2つの初期化は時間内に実行できます。 から反復するforループには時間がかかります。 この下に、からに進む別のforループがあります。 時間がかかる。 最後に、は時間内に計算できます。

したがって、動的計画法を使用してで0-1ナップサック問題を解決できます。時間計算量はの重み制限に依存することに注意してください。

アイテム数の多項式時間アルゴリズムのように見えますが、Wがたとえば100から1,000(に)に増加すると、処理はビットからビットに進みます。 時間計算量は、ビット数とともに指数関数的に増加します。

たとえば、重みが大きくない場合、複雑さは入力項目の数の多項式時間として認識される可能性があるため、「疑似多項式」という用語が使用されます。

8. 結論

この記事では、0-1ナップサック問題について詳しく説明しました。 0-1ナップサック問題がNP完全である理由を説明しました。

この問題を解決するために、動的計画法ベースのアルゴリズムを提示しました。 問題の例でアルゴリズムを実行して、アルゴリズムが正しい結果を提供していることを確認しました。 最後に、動的アルゴリズムにかかる時間を分析しました。