0-1 mochila sem repetição
-
29-09-2020 - |
Pergunta
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.
Solução
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 $ .