$ v_i= i $のときは、ナップザック問題NP-HARDですか？

Question

ナップザック問題はNP硬いものであり、次のように定式化することができます。 $$ \ begin {align}＆\ text {maximize} \ sum_ {i= 1} ^ n v_i x_i、\ tag {p1} \\＆ \ text {} \ sum_ {i= 1} ^ n w_i x_i \ leq w、\\＆\ text {および} x_i \ in \ {0,1 \} \ end {align} $$

$ v_i= i $ の場合それはまだnp-hard？

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

（P1）〜（P2）を下げようとしています。（P1）のインスタンスを考えると、同じ重みの数の項目を作成します。さて、私は解決策を（P1）と（P2）に関連付ける必要があります。

Answer 1

いいえ、この問題は $ \ mathbf {p} $ です。主な点は、すべての値の合計が $ 1 + 2 \ ldots + n=frac {n（n + 1）} {2}=mathcal {O}です。入力サイズの多項式であるn ^ 2）$ 。 $ v_i= i $ の追加の制限がなければ、値が入力のバイナリで表されているため、すべての値の合計は入力サイズ内の指数関数になります。

では、 $ dp [i] [v] $ を定義できます。 $ 1 \ leq i \ leq n $ と $ 0 \ leq v \ leq \ frac {n（n + 1）} {n（n + 1）} {2} $ 、値を取得するのに必要な最小重みになる少なくとも $ v $ の場合、最初の $ i $ 項目のみを使用します。それが達成できない場合は、 $ dp [i] [v]= inf $ に設定します。最後の回答は、 $ dp [n] [v] \ leq w $ $ v $ です。 >。

DP値は次のように計算できます。

$ dp [i] [v]=min（dp [i-1] [v]、w_i + dp [i-1] [v - v_i]）$ 。

最初の項は、 $ i ^ {th} $ の可能性を考慮し、2番目の期間は選択される可能性です。< / P>

だから問題全体は $ \ mathcal {}（n ^ 3）$ 時間と $で解決できます。 \ mathcal {o}（n ^ 3）$ スペース。 $ \ mathcal {O}（n ^ 2）$ スペースサイズの2つの配列を再利用する $ \ frac {n（n + 1）} {2} + 1 $ 。