Emissão de complexidade de programação dinâmica da mochila por $ W= 1 $, é $ O (n) $?

Question

O problema da mochila 0-1 é dado por

$$ \ begin {alinhar} & \ text {maximizar} \ sum_ {i= 1} ^ n v_ix_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} $$

Execução do algoritmo de programação dinâmica para este problema daria uma solução ideal na $ O (NW) $ .

Se eu definir $ p_i= w_i / w $ , recebo o seguinte problema da mochila:

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

Executando o algoritmo de programação dinâmica para este problema daria uma solução ideal na $ O (n) $ .Isso não é verdade, não é?

Answer 1

O tempo de execução é $ O (NW) $ Se todos os pesos forem inteiros .Isso ocorre porque a tabela de programação dinâmica é indexada por possíveis pesos de subconjuntos.Se todos os pesos forem inteiros, então, uma vez que estamos apenas interessados em subconjuntos cuja soma de pesos é no máximo $ W $ , há apenas $ W + 1 $ Pesos de subconjuntos que possam nos interessam.É aí que a $ W $ fator no tempo de execução é vindo.

Dividindo todos os pesos por $ W $ realiza exatamente nada.Você não mudou o problema, então o tempo necessário para resolver é exatamente o mesmo.