O problema da mochila é NP-HARD quando $ v_i= i $?

Question

O problema da mochila é NP-HARD e pode ser formulado como: $$ \ begin {alinhar} & \ text {maximizar} \ sum_ {i= 1} ^ n v_i x_i, \ tag {p1} \\ & \ Texto {Sujeito a} \ SUM_ {I= 1} ^ n w_i x_i \ leq w, \\ & \ text {e} x_i \ in \ {0,1 \}. \ end {alinhar} $$

E se $ v_i= i $ ?É ainda np-hard?

$$ \ begin {alinhar} & \ text {maximizar} \ sum_ {i= 1} ^ n ix_i, \ tag {p2} \\ & \ Texto {Sujeito a} \ SUM_ {I= 1} ^ n w_i x_i \ leq w, \\ & \ text {e} x_i \ in \ {0,1 \}. \ end {alinhar} $$

Eu estou tentando reduzir (p1) para (p2).Dada uma instância de (P1), eu crio o mesmo número de itens, mesmos pesos.Agora, tenho que relacionar as soluções para (P1) e (P2).

Answer 1

Não, este problema está em $ \ mathbf {p} $ . O ponto principal sendo que a soma de todos os valores é $ 1 + 2 \ LDOTS + n=frac {n (n + 1)} {2}=mathcal {O} ( n ^ 2) $ , que é polinomial no tamanho da entrada. Sem a restrição extra de $ v_i= i $ , a soma de todos os valores pode ser exponencial no tamanho da entrada, pois os valores são representados no binário na entrada.

para que possamos definir $ dp [i] [v] $ , onde $ 1 \ leq i \ leq n $ e $ 0 \ leq v \ leq \ frac {n (n + 1)} {2} $ , para ser o peso mínimo necessário para obter um valor de pelo menos $ v $ , usando apenas a primeira $ i $ itens. Se não puder ser alcançado, definiremos $ dp [i] [v]= inf $ . A resposta final é a máxima $ v $ tal que $ DP [n] [v] \ leq w $ .

Os valores de DP podem ser calculados da seguinte forma:

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

O primeiro termo considera a possibilidade da $ i ^ {th} $ item não sendo escolhido, e o segundo prazo é a possibilidade de ser escolhido. < / p >.

Então, todo o problema pode ser resolvido em $ \ mathcal {O} (n ^ 3) $ tempo e $ \ mathcal {o} (n ^ 3) $ espaço, que pode ser reduzido para $ \ mathcal {O} (n ^ 2) $ espaço por Apenas reutilizando duas matrizes de tamanho $ \ frac {n (n + 1)} {2} + 1 $ .