Sé que Knapsackes NP-completo, mientras que DP puede resolverlo. Dicen que la solución de DP es pseudo-polynomial, ya que es exponencial en la "longitud de entrada" (es decir, la cantidad de bits necesarios para codificar la entrada). Desafortunadamente no lo entendí. ¿Alguien puede explicarme...
87
¿Por qué el problema de la mochila es pseudopolinomial?