DAA-0-1ナップザック

このチュートリアルでは、先に、Greedyアプローチを使用した分数ナップザック問題について説明しました。 GreedyアプローチがFractional Knapsackの最適なソリューションを提供することを示しました。ただし、この章では、0-1ナップザック問題とその分析について説明します。

0-1ナップザックでは、アイテムを破壊することはできません。つまり、泥棒はアイテムをまとめて持ち去るか、そのままにしておく必要があります。これが、0-1ナップザックと呼ばれる理由です。

したがって、0-1ナップザックの場合、 _ x〜i〜' の値は _0' または 1 のいずれかで、他の制約は同じままです。

0-1ナップザックは貪欲なアプローチでは解決できません。貪欲なアプローチは、最適なソリューションを保証しません。多くの場合、貪欲なアプローチは最適なソリューションを提供します。

次の例は、ステートメントを確立します。

例1

ナップザックの容量はW = 25で、アイテムは次の表に示すとおりであると考えてみましょう。

Item	A	B	C	D
Profit	24	18	18	10
Weight	24	10	10	7

単位重量あたりの利益（ p〜i〜/w〜i〜 ）を考慮せずに、この問題を解決するために貪欲なアプローチを適用すると、最大の利益をもたらすため、最初の項目 A が選択されますすべての要素の中で。

アイテム A を選択すると、それ以上アイテムは選択されません。したがって、この特定のアイテムセットでは、総利益は 24 です。一方、最適なソリューションは、項目 B およびCを選択することで達成できます。総利益は18 + 18 = 36です。

例2

全体的な利益に基づいてアイテムを選択する代わりに、この例では、アイテムは比_p〜i〜/w〜i〜に基づいて選択されます。ナップザックの容量は_W = 60で、アイテムは次の表に示すとおりであると考えてみましょう。

Item	A	B	C
Price	100	280	120
Weight	10	40	20
Ratio	10	7	6

貪欲なアプローチを使用して、最初の項目 A が選択されます。次に、次の項目 B が選択されます。したがって、総利益は 100 + 280 = 380 です。ただし、このインスタンスの最適なソリューションは、項目 B および C を選択することで実現できます。ここで、総利益は 280 + 120 = 400 です。

したがって、貪欲なアプローチは最適なソリューションを提供しない可能性があると結論付けることができます。

0-1ナップザックを解くには、ダイナミックプログラミングアプローチが必要です。

問題文

泥棒は店を強奪しており、最大重量 W をナップザックに運ぶことができます。 n 個のアイテムがあり、 i ^ th ^ アイテムの重量は w〜i〜 であり、このアイテムを選択する利益は p〜i〜 です。泥棒はどのようなアイテムを取るべきですか？

動的プログラミングのアプローチ

*_i_* を、 *W* ドルの最適なソリューション *S* で最も高い番号のアイテムとします。 そして、 *_ S ^ '^ = S-\ {i} _* は *_W-w〜i〜_* ドルの最適なソリューションであり、ソリューション *_S_* の値は *_V〜i〜_* に値を加えたものです。副問題の。

この事実を次の式で表すことができます： c [i、w] をアイテム 1,2、…、i および最大〜i〜mum重量 w の解となるように定義します。

アルゴリズムは次の入力を取ります

最大重量 W
アイテムの数 n
2つのシーケンス v = <v〜1〜、v〜2〜、…、v〜n〜> および w = <w〜1〜、w〜2〜、…、w〜n〜>

Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
   c[0, w] = 0
for i = 1 to n do
   c[i, 0] = 0
   for w = 1 to W do
      if wi ≤ w then
         if vi + c[i-1, w-wi] then
            c[i, w] = vi + c[i-1, w-wi]
         else c[i, w] = c[i-1, w]
      else
         c[i, w] = c[i-1, w]

取得するアイテムのセットは、 c [n、w] から開始して、最適な値がどこから来たかを逆方向にトレースして、テーブルから推測できます。

c [i、w] = c [i-1、w] _の場合、アイテム _i はソリューションの一部ではないため、 c [i-1、w] でトレースを続けます。それ以外の場合、アイテム i はソリューションの一部であり、 c [i-1、w-W] でトレースを続けます。

分析

このアルゴリズムは、テーブル_c_に（n + 1）。（_ w_ + 1）エントリがあるため、各エントリが計算にθ（1）時間を必要とするため、θ（n、w）回かかります。

Design-and-analysis-of-algorithms-01-knapsack

目次

DAA-0-1ナップザック

例1

例2

問題文

動的プログラミングのアプローチ

分析