ウィキペディアからの説明が必要です：ナップサック、一部
したがって、このソリューションは O(nW) 時間と O(nW) 空間で実行されます。さらに、1 次元配列 m[W] のみを使用して現在の最適値を格納し、この配列を i+1 回渡し、m[W] から m[1] に毎回書き換えると、同じ結果が得られます。 O(W) スペースのみ。
スペースを節約するために 2D マトリックスを 1D マトリックスに変換する方法がわかりません。さらに、何をrewriting from m[W] to m[1] every time意味するか (またはどのように機能するか) についても説明します。
例を挙げてください。セット {V,W} --> {(5,4),(6,5),(3,2)} を K = 9 とします。
1D配列はどのように見えますか?
多くの動的計画問題では、各行がその直前の行にのみ依存する 2D テーブルを行ごとに構築します。0/1 ナップザック問題の場合、(ウィキペディアより) 再発は次のとおりです。
m[i, w] = m[i - 1, w] if w i > w
m[i, w] = max(m[i - 1, w], m[i - 1, w - w i ] + v i ) それ以外の場合
行 i を埋めるときのテーブルからのすべての読み取りは、行 i - 1 からのみ行われることに注意してください。表の前の行は実際には使用されません。したがって、2 つの行 (直前の行と入力する行) のみを保存することで、2D テーブルのスペースを節約できます。入力方法をもう少し賢くすることで、これを 1 行だけにさらに最適化できます。テーブル エントリ。これにより、スペースの使用量が O(nW) (O(n) 行と O(W) 列) から O(W) (1 つまたは 2 つの行と O(W) 列) に削減されます。
ただし、これには代償が伴います。多くの DP アルゴリズムは、解を明示的に計算するのではなく、代わりにテーブルに入力し、最後にテーブルに対して 2 回目のパスを実行して、最適な解を回復します。1 行だけを保存すると、最適な答えの値が得られますが、その最適な答えがたまたま何であるかがわからない可能性があります。この場合、ナップザックに収まる最大値を読み取ることができますが、その値を達成するために必要なことを必ずしも回復できるとは限りません。
お役に立てれば！