JS チュートリアル -- 動的計画法アルゴリズムのナップザック容量問題

ナップザック問題

質問
アイテムNと容量Vのナップザックが与えられたとき、アイテムiの体積はwiで、その値はciです。
(各アイテムは1つだけあります)
Q: バックパックに入れるアイテムの合計価値が最大になるように、バックパックに入れるアイテムを選択するにはどうすればよいですか?

各アイテムを前に、選択肢は 2 つだけです。入れるか入れないかです。各アイテムは 1 回しか入れることができません。

先ほどと同じ考え方でもう一度試してみましょう
最後のアイテムしか残っていない場合、選択肢は2つあります
1. 残りのスペースが十分にある場合は、それを入れることを選択します
2. 残りのスペースが不足している場合、入れないでください

したがって、次の 2 つの最適な下部構造があります:
1. i-1 のアイテムを容量 V のバックパックに入れるという最適な選択
2. i- を容量 V-w のバックパックに入れる。 [i] 1 個のアイテムの最適な選択

つまり、要約すると、次のようになります:
容量 V のバックパックに i 個のアイテムを入れる最適な選択:
max (i-容量 V のバックパックに 1 つのアイテムを入れる 最適な選択は、容量 V-w[i] + c[i]) のバックパックに i-1 個のアイテムを入れることです

f[i][v] を使用して、 v の容量を持つ最初の i 個のアイテムを表します。バックパックに入れることができる最大値です。
副問題を使用して状態を定義します:
状態遷移方程式は次のとおりです: f[i] [v] = max{f[i-1] [v],f[i-1] [v-w[i]] +c[i]}。

まず、
バックパックの総容量は V = 12 であると仮定しましょう
アイテムの容量配列は w = [4, 6, 2, 2, 5, 1]
値の配列は c = [8, 10 、6、3、7、2]

1. f(i,v) = 0 (i

2. f(i,v) = c [0] (i= =1, v>=p[0]);

3. f(i,v) = f(i-1,v) (i>1, v

4. f(i,v) = max(f(i-1,v), f(i-1,v-w[i-1])+c[i-1])(i> ;1, v>= w[i-1])

左から右に進むたびに、前のデータが保存されます
上から下に進むと、前のデータが保存されます前の行
したがって、一般に保存する必要があるのは、1 行のデータの場合、空間複雑度は O(V) です
時間計算量は O(N*V)、空間複雑度は O(V) です

ただし、元の再帰的手法、つまり順列と組み合わせを使用すると、この手法を使用すると、時間計算量は O(2^N) になります

V が非常に大きく、N が小さい場合、 =1000、N=6、再帰は 2^6=64 回計算するだけでよく、評判の高い動的計画法は 1000*6=6000 回計算する必要があります

つまり、アルゴリズムが絶対的に良いか悪いかというと、キーはアプリケーションの状況によって異なります

関連する推奨事項:

JS は動的プログラミング バックパック アルゴリズムを実装します

JavaScript の高度なアルゴリズム動的プログラミングのサンプル分析

以上がJS チュートリアル -- 動的計画法アルゴリズムのナップザック容量問題の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。