0-1 Mochila sin repetición

Question

Mi pregunta es la razón por la que O (NW) en el problema de Knapsack es pseudo-polinomio.

Leí mucha explicación en StackOverflow, pero realmente no lo entiendo. ( https://stackoverflow.com/Questions / 19647658 / What-is-Pseudopolinomial-Time-How-How-Do-It-Differ-De-Polinomial-Time , https://stackoverflow.com/questions/4538581/40 is-the-knapsack-problem-pseudo-polinomio # respuesta-4538668 )

La cosa básica es la razón por la que tenemos que pensar solo 'w' como 'Logw' Entrada de bits, no 'n' como 'bits de registro n'.

Dicha explicación dijo que 'W' es entero pero 'n' es solo el número de artículo. Por lo tanto, solo el tamaño 'W' es proporcional a 'Logw'.

Creo que esta lógica debe aplicarse a 'n'.

Suponiendo que estamos numerando los artículos de 1 a N, para diferenciar los artículos,

Tenemos que contar los números de 1 a n.

Creo que es lo mismo que el bucle hace la iteración por W Times.

Por lo tanto, creo que es igual con 'W' porque este conteo también necesita 'bits de registro n'.

¿Qué entiendo mal en este problema?

gracias.

Answer 1

Aquí es cómo codifica la entrada:

• Peso y valor del artículo 1.
• Peso y valor del artículo 2.
• ...
• Peso y valor del artículo $ n $ .
• $ w $ .

Suponga que el peso y el valor son enteros, están en la mayoría de $ m $ , y ambos están codificados en binario, ya que es $ W $ .Luego, la longitud de la codificación es $$ \ Omega (n + \ log w), O (n \ log m + \ log w). $$ Esperemos que esto aclare la diferencia entre $ n $ y $ w $ .