ここでのナップサックはコンテナまたはバッグのようなものです。何らかの重みや利益を持つアイテムをいくつか与えたとします。合計値が最大の利益を生み出すようにいくつかのアイテムをナップザックに入れなければなりません。

たとえば、コンテナの重量は 20 kg です。アイテムの重量の合計がコンテナの重量以下になるようにアイテムを選択し、利益が最大になるようにする必要があります。

ナップサックの問題には 2 つのタイプがあります。

• 0/1 ナップサック問題
• 分数ナップサック問題

両方の問題について 1 つずつ説明します。まずは0/1ナップザック問題について学びます。

0/1ナップザック問題とは何ですか?

0/1 ナップザック問題は、アイテムがナップザックに完全に詰められているか、アイテムがまったく入っていないことを意味します。たとえば、それぞれ重さ 2kg と 3kg の 2 つのアイテムがあります。 2kg のアイテムを選択した場合、2kg のアイテムから 1kg のアイテムを選択することはできません (アイテムは割り切れません)。 2kgのアイテムを完全に選択する必要があります。これは、アイテムを完全に選択するか、そのアイテムを選択するかのどちらかである 0/1 ナップザック問題です。 0/1 ナップザック問題は動的計画法によって解決されます。

分数ナップザック問題とは何ですか?

分数ナップザック問題は、アイテムを分割できることを意味します。たとえば、3 kg のアイテムがある場合、2 kg のアイテムを選択し、1 kg のアイテムを残すことができます。分数ナップザック問題は、Greedy アプローチによって解決されます。

0/1 ナップザック問題の例。

次のような重みと利益を持つ問題を考えてみましょう。

重み: {3、4、6、5}

利益: {2, 3, 1, 4}

ナップザックの重さは8kgです

アイテム数は4つです

上記の問題は、次の方法を使用して解決できます。

バツ_私= {1, 0, 0, 1}

= {0, 0, 0, 1}

Spring Boot の注釈

= {0, 1, 0, 1}

上記は可能な組み合わせです。 1 はアイテムが完全にピックされたことを示し、0 はアイテムがピックされていないことを意味します。アイテムが 4 つあるため、可能な組み合わせは次のとおりです。

2⁴= 16; それで。上記の問題を使用して作成できる組み合わせは 16 通りあります。すべての組み合わせができたら、最大の利益をもたらす組み合わせを選択する必要があります。

この問題を解決するもう 1 つのアプローチは、動的プログラミング アプローチです。動的計画法では、複雑な問題をサブ問題に分割し、サブ問題の解を見つけ、サブ問題の解を使用して複雑な問題の解を見つけます。

この問題は、動的プログラミングのアプローチを使用してどのように解決できるのでしょうか?

初め、

以下に示すような行列を作成します。

上の行列では、列は重量、つまり 8 を表します。行はアイテムの利益と重量を表します。ここでは重み 8 を直接取っていません。問題はサブ問題、つまり 0、1、2、3、4、5、6、7、8 に分割されています。サブ問題の解は次のファイルに保存されます。セルと問題の答えは最後のセルに保存されます。まず、重みを昇順に書き、その重みに応じた利益を以下のように示します。

で_私= {3、4、5、6}

p_私= {2, 3, 4, 1}

w=0 には項目がないため、最初の行と最初の列は 0 になります。

i=1の場合、W=1

で₁= 3;セットには重さ 3 のアイテムが 1 つだけありますが、ナップザックの容量は 1 です。容量 1 kg のナップザックに 3kg のアイテムを入れることはできないため、以下のように M[1][1] に 0 を追加します。 :

i = 1、W = 2の場合

で₁= 3;セットには重さ 3 のアイテムが 1 つだけありますが、ナップザックの容量は 2 です。容量 2 kg のナップザックに 3 kg のアイテムを入れることはできないため、以下のように M[1][2] に 0 を追加します。 :

i=1、W=3の場合

で₁= 3;セット内には重みが 3 のアイテムが 1 つだけあり、ナップザックの重さも 3 であるため、したがって、ナップザックに重量 3 のアイテムを入れることができます。以下に示すように、重量 3、つまり 2 に対応する利益を M[1][3] に置きます。

i=1の場合、W=4

_W1= 3;セット内には重みが 3 のアイテムが 1 つだけあり、ナップザックの重さは 4 であるため、したがって、ナップザックに重量 3 のアイテムを入れることができます。以下に示すように、重量 3、つまり 2 に対応する利益を M[1][4] に置きます。

i=1の場合、W=5

_W1= 3;セット内には重みが 3 のアイテムが 1 つだけあり、ナップザックの重さは 5 であるため、したがって、ナップザックに重量 3 のアイテムを入れることができます。以下に示すように、重量 3、つまり 2 に対応する利益を M[1][5] に置きます。

i=1の場合、W=6

_W1= 3;セット内には重みが 3 のアイテムが 1 つだけあり、ナップザックの重さは 6 であるため、したがって、ナップザックに重量 3 のアイテムを入れることができます。以下に示すように、重量 3、つまり 2 に対応する利益を M[1][6] に置きます。

i=1の場合、W=7

_W1= 3;セット内には重みが 3 のアイテムが 1 つだけあり、ナップザックの重さは 7 であるため、したがって、ナップザックに重量 3 のアイテムを入れることができます。以下に示すように、重量 3、つまり 2 に対応する利益を M[1][7] に置きます。

i =1の場合、W =8

_W1= 3;セット内には重みが 3 のアイテムが 1 つだけあり、ナップザックの重さは 8 であるため、したがって、ナップザックに重量 3 のアイテムを入れることができます。以下に示すように、重量 3、つまり 2 に対応する利益を M[1][8] に置きます。

ここで、「i」の値がインクリメントされ、2 になります。

i =2の場合、W = 1

値 2 に対応する重みは 4、つまり w です。₂= 4. セット内には重さ 4 のアイテムが 1 つだけあるため、ナップザックの重さは 1 です。重さ 4 のアイテムをナップザックに入れることはできないため、M[2][1] に 0 を追加します。 ]を以下に示します。

i =2の場合、W = 2

値 2 に対応する重みは 4、つまり w です。₂= 4. セット内には重み 4 のアイテムが 1 つだけあるため、ナップザックの重さは 2 です。重さ 4 のアイテムをナップザックに入れることはできないため、M[2][2] に 0 を追加します。 ]を以下に示します。

i=2の場合、W=3

値 2 に対応する重みは 4、つまり w です。₂= 4. セットには重み 3 と 4 を持つ 2 つのアイテムがあり、ナップザックの重さは 3 です。重さ 3 のアイテムはナップザックに入れることができるので、M[2][3] に 2 を加えます。以下のように示されます。

i=2の場合、W=4

値 2 に対応する重みは 4、つまり w です。₂= 4. セットには重さ 3 と 4 を持つ 2 つのアイテムがあり、ナップザックの重さは 4 であるため、重さ 4 に対応する利益が重さのアイテムより大きいため、重さ 4 のアイテムをナップザックに入れることができます。 3 なので、以下に示すように M[2][4] に 3 を追加します。

i = 2、W = 5の場合

値 2 に対応する重みは 4、つまり w です。₂= 4. セットには重さ 3 と 4 の 2 つのアイテムがあり、ナップザックの重さは 5 であるため、重さ 4 のアイテムをナップザックに入れることができ、その重さに対応する利益は 3 なので、次の式で 3 を追加します。 M[2][5] は以下のように表示されます。

i=2、W=6の場合

値 2 に対応する重みは 4、つまり w です。₂= 4. セットには重さ 3 と 4 を持つ 2 つのアイテムがあり、ナップザックの重さは 6 であるため、重さ 4 のアイテムをナップザックに入れることができ、その重さに対応する利益は 3 なので、次の式で 3 を追加します。 M[2][6] は以下のように表示されます。

i = 2、W = 7の場合

値 2 に対応する重みは 4、つまり w です。₂= 4. セットには重さ 3 と 4 を持つ 2 つのアイテムがあり、ナップザックの重さは 7 であるため、重さ 4 と 3 のアイテムをナップザックに入れることができ、重みに対応する利益は 2 と 3 になります。したがって、合計の利益は 5 となるため、以下に示すように M[2][7] に 5 を加算します。

i = 2、W = 8の場合

値 2 に対応する重みは 4、つまり w です。₂= 4. セットには重さ 3 と 4 を持つ 2 つのアイテムがあり、ナップザックの重さは 7 であるため、重さ 4 と 3 のアイテムをナップザックに入れることができ、重みに対応する利益は 2 と 3 になります。したがって、合計の利益は 5 となるため、以下に示すように M[2][7] に 5 を加算します。

ここで、「i」の値がインクリメントされ、3 になります。

i = 3、W = 1の場合

dateformat.format Java

値 3 に対応する重みは 5、つまり w です。₃= 5. セットには重み 3、4、5 の 3 つの項目があり、ナップザックの重さは 1 であるため、どちらの項目もナップザックに入れることはできないため、M[3][ に 0 を追加します。 1]を以下に示します。

i = 3、W = 2の場合

値 3 に対応する重みは 5、つまり w です。₃= 5。セットには重さ 3、4、5 の 3 つのアイテムがあり、ナップザックの重さは 1 です。どちらのアイテムもナップザックに入れることはできないため、M[3][ に 0 を追加します。 2]を以下に示します。

i = 3の場合、W = 3

値 3 に対応する重みは 5、つまり w です。₃= 5. それぞれ重さ 3、4、5 のセットに 3 つのアイテムがあり、ナップザックの重さは 3 であるため、重さ 3 のアイテムをナップザックに入れることができ、そのアイテムに対応する利益は 2、したがって、以下に示すように M[3][3] に 2 を追加します。

i = 3、W = 4の場合

値 3 に対応する重みは 5、つまり w です。₃= 5. セットにはそれぞれ重さ 3、4、5 の 3 つのアイテムがあり、ナップザックの重さは 4 であるため、重さ 3 または 4 のアイテムを保持できます。重み 4 に対応する利益 (3) は重み 3 に対応する利益より大きいため、以下に示すように M[3][4] に 3 を追加します。

i = 3、W = 5の場合

値 3 に対応する重みは 5、つまり w です。₃= 5。セットにはそれぞれ重さ 3、4、5 の 3 つのアイテムがあり、ナップザックの重さは 5 であるため、重さ 3、4、または 5 のいずれかのアイテムを保持できます。重み 4 に対応する利益 (3) は重み 3 と 5 に対応する利益より大きいため、以下に示すように M[3][5] に 3 を追加します。

i =3の場合、W = 6

値 3 に対応する重みは 5、つまり w です。₃= 5. セットにはそれぞれ重さ 3、4、5 の 3 つのアイテムがあり、ナップザックの重さは 6 であるため、重さ 3、4、または 5 のいずれかのアイテムを保持できます。重み 4 に対応する利益 (3) は重み 3 と 5 に対応する利益より大きいため、以下に示すように M[3][6] に 3 を追加します。

i =3の場合、W = 7

値 3 に対応する重みは 5、つまり w です。₃= 5. それぞれ重み 3、4、5 のセットに 3 つのアイテムがあり、ナップザックの重さは 7 であるため、この場合、重み 3 と 4 の両方のアイテム、つまり利益の合計を保持できます。は (2 + 3)、つまり 5 に等しいため、以下に示すように M[3][7] に 5 を追加します。

i = 3、W = 8の場合

値 3 に対応する重みは 5、つまり w です。₃= 5. それぞれ重み 3、4、5 のセットに 3 つのアイテムがあり、ナップザックの重さは 8 であるため、この場合、重み 3 と 4 の両方のアイテム、つまり重さの合計を保持できます。利益は (2 + 3)、つまり 5 に等しいため、以下に示すように M[3][8] に 5 を追加します。

ここで、「i」の値がインクリメントされて 4 になります。

i = 4、W = 1の場合

値 4 に対応する重みは 6、つまり w です。₄= 6. 重みのセットには 4 つのアイテムがあり、それぞれ 3、4、5、6 であり、ナップザックの重さは 1 です。すべてのアイテムの重さはナップザックの重さより大きいため、次のことはできません。ナップザックに任意のアイテムを追加します。したがって、以下のように M[4][1] に 0 を追加します。

i = 4、W = 2の場合

値 4 に対応する重みは 6、つまり w です。₄= 6. セットには 4 つのアイテムがあり、それぞれ重み 3、4、5、6 であり、ナップザックの重さは 2 です。すべてのアイテムの重さはナップザックの重さより大きいため、次のことはできません。ナップザックに任意のアイテムを追加します。したがって、以下のように M[4][2] に 0 を追加します。

i = 4、W = 3の場合

値 4 に対応する重みは 6、つまり w です。₄= 6. 重み 3、4、5、6 のセットに 4 つのアイテムがあり、ナップザックの重さは 3 であるため、重み 3 のアイテムをナップザックに入れることができ、それに対応する利益が得られます。重み 4 は 2 なので、以下のように M[4][3] に 2 を加算します。

i = 4の場合、W = 4

値 4 に対応する重みは 6、つまり w です。₄= 6. 重み 3、4、5、6 のセットに 4 つのアイテムがあり、ナップザックの重さは 4 であるため、重み 4 のアイテムをナップザックに入れることができ、その利益に対応する利益が得られます。重み 4 は 3 なので、以下のように M[4][4] に 3 を追加します。

i = 4、W = 5の場合

値 4 に対応する重みは 6、つまり w です。₄= 6. 重み 3、4、5、6 のセットに 4 つのアイテムがあり、ナップザックの重さは 5 であるため、重み 4 のアイテムをナップザックに入れることができ、その利益に対応する利益が得られます。重み 4 は 3 なので、以下のように M[4][5] に 3 を追加します。

i = 4、W = 6の場合

値 4 に対応する重みは 6、つまり w です。₄= 6. それぞれ重み 3、4、5、6 のセットに 4 つのアイテムがあり、ナップザックの重さは 6 であるため、この場合、アイテムを重さ 3、4 のいずれかにナップザックに入れることができます。 、5 または 6 ですが、利益、つまり重み 6 に対応する 4 がすべての項目の中で最も高くなります。したがって、以下に示すように、M[4][6] に 4 を追加します。

i = 4、W = 7の場合

値 4 に対応する重みは 6、つまり w です。₄= 6. それぞれ重み 3、4、5、6 のセットに 4 つの項目があり、ナップザックの重さは 7 です。ここで、重み 3 と 4 の 2 つの項目を追加すると、最大値が生成されます。利益、つまり (2 + 3) は 5 に等しいため、以下に示すように M[4][7] に 5 を追加します。

i = 4、W = 8の場合

値 4 に対応する重みは 6、つまり w です。₄= 6. それぞれ重み 3、4、5、6 のセットに 4 つの項目があり、ナップサックの重さは 8 です。ここで、重み 3 と 4 の 2 つの項目を追加すると、最大値が生成されます。利益、つまり (2 + 3) は 5 に等しいため、以下に示すように M[4][8] に 5 を追加します。

上の表からわかるように、5 がすべてのエントリの中で最大の利益です。ポインタは、値が 5 である最後の行と最後の列を指します。次に、5 の値を前の行と比較します。前の行、つまり i = 3 に同じ値 5 が含まれている場合、ポインタは上にシフトします。前の行には値 5 が含まれているため、ポインタは次の表に示すように上にシフトされます。

もう一度、上の行の値 5、つまり i = 2 を比較します。上の行には値 5 が含まれているため、ポインタは次の表に示すように再び上にシフトされます。

もう一度、上の行の値 5、つまり i = 1 を比較します。上の行には同じ値が含まれていないため、行 i=1 とみなされ、その行に対応する重みは 4 になります。では、重み 4 を選択し、以下に示す重み 5 と 6 を拒否しました。

マムタ・クルカルニ 俳優

x = { 1, 0, 0}

重みに対応する利益は 3 です。したがって、残りの利益は (5 - 3) で 2 になります。次に、この値 2 を行 i = 2 と比較します。行 (i = 1) には値 2 が含まれているため、 ;したがって、以下に示すように、ポインタが上に移動しました。

再度、値 2 を上の行、つまり i = 1 と比較します。行 i =0 には値 2 が含まれていないため、行 i = 1 が選択され、i = 1 に対応する重みは 3 として表示されます。下に：

X = {1, 1, 0, 0}

重みに対応する利益は 2 です。したがって、残りの利益は 0 です。0 の値を上の行と比較します。上の行には値 0 が含まれていますが、この行に対応する利益は 0 です。この問題では、利益を最大化するために 2 つの重み、つまり 3 と 4 が選択されます。