Rucksack Dynamic Programming-Komplexitätsausgabe für $ W= 1 $, ist es $ o (n) $?

Question

Das 0-1-Rucksackproblem wird von

gegeben

$$ \ START {ALIGN} & \ Text {Maximize} \ sum_ {i= 1} ^ n v_ix_i, \ tag {p1} \\ & \ text {thema} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ text {und} x_i \ in \ {0,1 \}. \ end {richten} $$

Durchführen des dynamischen Programmieralgorithmus für dieses Problem würde eine optimale Lösung in $ O (NW) $ ergeben.

Wenn ich $ p_i= w_i / w $ definiere, bekomme ich das folgende Rucksackproblem:

$$ \ beginnen {ALIGN} & \ Text {Maximize} \ sum_ {i= 1} ^ n v_ix_i, \ tag {p2} \\ & \ text {unter} \ sum_ {i= 1} ^ n p_i x_i \ leq 1, \\ & \ text {und} x_i \ in \ {0,1 \ \ \ \ \ \ end \ \ \ \ \ \ \ end {richten} $$

Wenn der dynamische Programmieralgorithmus für dieses Problem ausgeführt wird, würde eine optimale Lösung in $ o (n) $ ergeben.Das ist nicht wahr, nicht wahr?

Answer 1

Die Laufzeit ist $ o (NW) $ Wenn alle Gewichte intenger sind.Dies liegt daran, dass die dynamische Programmiertabelle mit möglichen Gewichtsgewichten von Subsets indexiert wird.Wenn alle Gewichte ganze Zahlen sind, da wir nur an Subsets interessiert sind, deren Gewichtssumme höchstens $ W $ ist, gibt es nur $ W + 1 $ Gewichte von Subsets, die uns möglicherweise interessieren könnten.Hier kommt der $ W $ Faktor in der Laufzeit von.

Teilen aller Gewichte durch $ W $ Erfüllt genau nichts.Sie haben das Problem nicht geändert, daher bleibt die erforderliche Zeit, um es zu lösen, genau das gleiche.