¿Es el problema de Knapsack NP-HARD cuando $ V_I= i $?

Question

El problema de Knapsack es NP-HARD y se puede formular como: $$ \ comienza {align} & \ texto {maximize} \ sum_ {i= 1} ^ n v_i x_i, \ tag {p1} \\ & \ texto {sujeto a} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ texto {y} x_i \ in \ \ \ {0,1 \ \ in \ \ \ {0,1 \ \ in \ \ \ {0,1 \ \ in \ \ \ {0,1} \ in \ \ {0,1} \ in \ \ {0,1}} \ Fin {align} $$

¿Qué pasa si $ v_i= i $ ?¿Todavía es NP-HARD?

$$ \ comience {align} & \ texto {maximize} \ sum_ {i= 1} ^ n ix_i, \ tag {p2} \\ & \ texto {sujeto a} \ sum_ {i= 1} ^ n w_i x_i \ leq w, \\ & \ texto {y} x_i \ in \ \ \ {0,1 \ \ in \ \ \ {0,1 \ \ in \ \ \ {0,1 \ \ in \ \ \ {0,1} \ in \ \ {0,1} \ in \ \ {0,1}} \ Fin {align} $$

Estoy tratando de reducir (P1) a (P2).Dada una instancia de (P1), creo el mismo número de artículos, los mismos pesos.Ahora, tengo que relacionar las soluciones a (P1) y (P2).

Answer 1

No, este problema está en $ \ mathbf {p} $ . El punto principal es que la suma de todos los valores es $ 1 + 2 \ ldots + n=frac {n (n + 1)} {2}=mathcal {O} ( n ^ 2) $ , que es polinomial en el tamaño de entrada. Sin la restricción adicional de $ v_i= i $ , la suma de todos los valores podría ser exponencial en el tamaño de entrada, ya que los valores se representan en binario en la entrada.

Entonces podemos definir $ dp [I] [v] $ , donde $ 1 \ leq i \ leq n $ y $ 0 \ leq v \ leq \ frac {n (n + 1)} {2} $ , para ser el peso mínimo necesario para obtener un valor de al menos $ v $ , usando solo el primer $ i $ artículos. Si no se puede lograr, estableceremos $ dp [i] [v]= inf $ . La respuesta final es el máximo $ v $ de tal que $ dp [n] [v] \ leq w $ .

Los valores DP se pueden calcular de la siguiente manera:

$ dp [I] [v]=min (DP [I-1] [V], W_I + DP [I-1] [V - V-V_I]) $ .

El primer término considera la posibilidad del $ i ^ {th} $ Artículo que no se elige, y el segundo término es la posibilidad de que se elija. < / p>

Entonces, el problema completo se puede resolver en $ \ mathcal {o} (n ^ 3) $ tiempo y $ \ Mathcal {O} (n ^ 3) $ espacio, que se puede reducir a $ \ mathcal {o} (n ^ 2) $ espacio por simplemente reutilizando dos matrices de tamaño $ \ frac {n (n + 1)} {2} + 1 $ .