0-1 mochila sem repetição

Question

minha pergunta é por que o (NW) no problema da mochila é pseudo-polinomial.

Eu li muita explicação no Stackoverflow, mas eu realmente não entendo isso. ( https://stackoverflow.com/Questions / 19647658 / What-is-Pseudopolyncomial-time-how-it-differ-it-differ-de-tempo de polinomial , https://stackoverflow.com/questions/4538581/why- é-the-knapsack-problema-pseudo-polynomial # Resposta-4538668 )

O core é por que temos que pensar apenas 'W' como 'logw' bits entrada, não 'n' como 'log n' bits.

As muitas explicações disseram que 'W' é inteiro, mas 'n' é apenas o número de item. Portanto, apenas o tamanho 'W' é proporcional ao "logw".

Eu acho que esta lógica deve ser aplicada a 'n'.

Assumindo que estamos numerando os itens de 1 a N, para diferenciar os itens,

Temos que contar os números de 1 a n.

Eu acho que é o mesmo que o loop faz iteração para o W vezes.

Portanto, acho que é o mesmo com 'W' porque esta contagem também precisa de "log n" bits.

O que eu entendo mal neste problema?

obrigado.

Answer 1

Aqui está como você codifica a entrada:

• peso e valor do item 1.
• peso e valor do item 2.
• ...
• peso e valor do item $ n $ .
• $ W $ .

Suponha que o peso e o valor sejam inteiros, estão no máximo $ m $ , e ambos são codificados em binário, como é $ W $ .Então o comprimento da codificação é $$ \ Ômega (n + \ log w), O (n \ log m + \ log w). $$ Espero que isso esclarece a diferença entre $ n $ e $ W $ .