$ W= 1 $のためのナップザック動的プログラミングの複雑さ問題は、それは$ O（n）$ですか？

Question

0-1ナップザック問題は

で与えられます

$$ \ begin {align}＆\ text {maximize} \ sum_ {i= 1} ^ n v_ix_i、\ tag {p1} \\＆ \ text {} \ sum_ {i= 1} ^ n w_i x_i \ leq w、\\＆\ text {および} x_i \ in \ {0,1 \} \ end {align} $$

動的プログラミングアルゴリズムを実行するこの問題に対する $ o（nw）$ に最適な解決策を与えます。

$ p_i= w_i / w $ を定義した場合、次のナップザック問題が発生します。

$$ \ begin {align}＆\ text {maximize} \ sum_ {i= 1} ^ n v_ix_i、\ tag {p2} \\＆ \ text {} \ sum_ {i= 1} ^ n p_i x_i \ leq 1、\ \＆\ text {および} x_i \ in \ {0,1 \} \ end {align} $$

動的プログラミングアルゴリズムを実行するこの問題に対する $ o（n）$ に最適な解決策を与えます。これは真実ではありません、それはそうではありませんか？

Answer 1

実行時間は、すべての重み付けが整数の場合、 $ o（nw）$ です。これは、動的プログラミングテーブルがサブセットの可能性のある重みによって索引付けされているためです。すべての重みが整数であれば、重みの合計が $ w $ にあるサブセットにのみ興味があるため、 $ W + 1 $ 興味があるサブセットの重み。これが、ランニングタイムの $ w $ の因子が存在します。

$ w $ ですべての重みを分割します。問題を変更していないので、それを解決するための必要な時間はまったく同じです。