¿El problema de la mochila 0-1 es donde el valor es igual a peso NP-completado?

Question

Tengo un problema que sospecho que es NP-Completo. Es fácil demostrar que es NP. Mi tren de pensamiento actual gira en torno al uso de una reducción de la mochila, pero daría como resultado instancias de 0-1-Knapsack con el valor de cada elemento igual a su peso.

¿Sigue siendo esto completo NP? ¿O me estoy perdiendo algo?

Answer 1

Sí, esto se llama el problema de suma subconjunto y es np-hard.