Links sobre el Knapsack problem

En este post, varios links sobre el problema de la mochila.

Sobre el problema

• Entrada de Wikipedia: https://en.wikipedia.org/wiki/Knapsack_problem

Sobre su caracter de problema de complejidad NP

• Explicación en Stack Overflow: https://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete.

• Explicación en Quora: https://www.quora.com/What-is-the-meaning-of-pseudo-polynomial-time-complexity-I-saw-that-Knapsack-runs-in-pseudo-polynomial-time-I-read-about-this-here-Pseudo-polynomial-time-but-I-am-not-able-to-follow-I-want-to-understand-the-concept/answer/Nishanth-Dikkala.

• Polynomial-time approximation scheme (PTAS): https://en.wikipedia.org/wiki/Polynomial-timeapproximationscheme

• Pseudo-polynomial time: https://en.wikipedia.org/wiki/Pseudo-polynomial_time

• Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes: https://arxiv.org/abs/2504.15885