Ist das Rucksackproblem NP-Hard, wenn $ v_i= i $?

Question

Das Rucksackproblem ist np-hart und kann als formuliert werden: $$ \ beginnen {Align} & \ Text {Maximize} \ sum_ {i= 1} ^ n v_i x_i, \ Tag {P1} \\ & \ text {thema} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {und} x_i \ in \ {0,1 \}. \ end {richten} $$

was ist, wenn $ v_i= i $ ?Ist es immer noch np-hart?

$$ \ beginnen {Align} & \ Text {Maximize} \ sum_ {i= 1} ^ n ix_i, \ tag {p2} \\ & \ text {thema} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {und} x_i \ in \ {0,1 \}. \ end {richten} $$

Ich versuche, (P1) bis (P2) zu reduzieren.Angesichts einer Instanz von (P1) erstellte ich die gleiche Anzahl von Elementen, gleiche Gewichte.Nun muss ich die Lösungen auf (P1) und (P2) beziehen.

Answer 1

Nein, dieses Problem ist in $ \ mathbf {p} $ . Der Hauptpunkt ist, dass die Summe aller Werte $ 1 + 2 \ ldots + n=frac {n (n + 1)} {2}=mathcal {o} ( n ^ 2) $ , das Polynom in der Eingabegröße ist. Ohne die zusätzliche Einschränkung der $ v_i= i $ könnte die Summe aller Werte in der Eingabegröße exponentiell sein, da die Werte in der Input in Binary dargestellt werden.

So können wir $ dp [i] [v] $ definieren, wobei $ 1 \ leq i \ leq n $ und $ 0 \ leq v \ leq \ frac {n (n + 1)} {2} $ , um das Mindestgewicht zu sein, das erforderlich ist, um einen Wert zu erhalten Von mindestens $ V $ , verwenden Sie nur den ersten $ i $ Elemente. Wenn es nicht erreicht werden kann, setzen wir $ dp [i] [v]= inf $ . Die endgültige Antwort ist der maximale $ V $ so, dass $ dp [n] [v] \ leq w $ .

Die DP-Werte können wie folgt berechnet werden:

$ dp [i] [v]=min (dp [i-1] [v], w_i + dp [i-1] [v - v_i]) $ .

Der erste Begriff ist der Auffassung, dass die Möglichkeit der $ I ^ {th} $ nicht gewählt wird, und der zweite Term ist die Möglichkeit, dass sie ausgewählt wird. < / p>

Das gesamte Problem kann also in $ \ Mathcal {O} (N ^ 3) $ Uhrzeit und $ gelöst werden \ mathcal {o} (n ^ 3) $ space, der auf $ \ mathcal {o} (n ^ 2) $ raum von reduziert werden kann Nur zwei Arrays der Größe $ \ frac {n (n + 1)} {2} + 1 $ .