01ナップザック問題の動的計画法

動的プログラミングの基本的な考え方:

動的プログラミング アルゴリズムは、通常、特定の最適な特性を持つ問題を解決するために使用されます。私たちが通常「最適な下部構造特性」と呼ぶもの。

動的計画法アルゴリズムは分割統治法に似ており、その基本的な考え方は、解決すべき問題をいくつかのサブ問題に分解し、最初にサブ問題を解決してから、解を得るというものです。これらの部分問題の解決策から元の問題に導きます。分割統治法との最大の違いは、動的計画法による解決に適した問題の場合、分解後に得られる部分問題、つまり次の部分段階の解が互いに独立していないことが多いことです。前のサブステージのソリューションに基づいています。

この種の問題を分割統治法で解くと、分解によって得られる部分問題の数が多すぎて、一部の部分問題は何度も再計算されることになります。解決したサブ問題の答えを保存し、必要なときに得られた答えを見つけることができれば、多くの繰り返し計算を避け、時間を節約できます。テーブルを使用して、解決されたすべてのサブ問題に対する回答を記録できます。部分問題が後で使用されるかどうかに関係なく、計算される限り、その結果がテーブルに入力されます。

問題の説明:

N 個のアイテムとバックパックが与えられました。アイテム i の重量は Wi、その価値は Vi、バックパックの容量は C です。バックパックに移すアイテムの合計価値を最大化するには、バックパックに入れるアイテムをどのように選択すればよいですか? ?

アイテムを選択するとき、各アイテムには 2 つの選択肢しかありません。つまり、バックパックに積み込むか、バックパックに積み込まないということです。アイテム i を複数回ロードしたり、アイテムの一部だけをロードしたりすることはできません。したがって、この問題は 0-1 ナップザック問題と呼ばれます。

問題分析: V(i,j) は、最初の i(1

(1)   V(i,0)=V(0,j)=0 

(2)   (a)  V(i,j)=V(i-1,j)    j<wi  

      (b)  V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) }   j>wi

(1) 式は以下を示します: i 番目のアイテムの重みがより大きい場合バックパックの容量を考慮すると、アイテム i で得られる最大値は、積み込む前にアイテム i-1 で得られる最大値と同じになります。つまり、アイテム i をバックパックに積み込むことはできません。

(2) 式は次を示します。 i 番目のアイテムの重量がバックパックの容量より小さい場合、次の 2 つの状況が発生します。 (a) i 番目のアイテムがバックパックに積み込まれていない場合バックパックの場合、バックパック内のアイテムの価値 これは、容量 j のバックパックに最初の i-1 アイテムを入れることによって得られる値に相当します。 (b) i 番目のアイテムがバックパックに入れた場合、バックパックのアイテムの値は、容量 j-wi のバックパック内の i-1 番目のアイテムの値に i 番目のアイテムの値 vi を加えた値に等しくなります。 ; 明らかに、最大の値を持つものが、最初の i 個のアイテムを容量 j のバックパックに積み込むための最適解です。

推奨チュートリアル: PHP チュートリアル

以上が01ナップザック問題の動的計画法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。