Esta situación no facilita el problema. El caso muy especial donde cada peso es igual al valor se conoce como el problema de la suma de subconjuntos, y también es NP completo.
De hecho, las situaciones en las que el peso está estrechamente relacionado con el valor son en realidad las situaciones más difíciles para la mochila. Cuando hay elementos con bajo peso y alto valor, o con alto peso y bajo valor, puede ver cómo, intuitivamente, es fácil tomar una decisión sobre si incluir o no esos elementos. Pero, cuando la mayoría de los artículos tienen una relación valor / peso similar (o en el caso de una suma de subconjuntos, idéntica), el problema se vuelve más sobre el aspecto del embalaje (sobre encontrar qué subconjunto de artículos minimizará la cantidad de peso capacidad que no se usa).
El aspecto del problema es difícil, y es esencialmente lo que causa la dificultad. Tenga en cuenta que la mochila fraccional, donde no es necesario que empaquete porque puede tomar cualquier fracción de cualquier artículo que desee, puede resolverse en tiempo lineal.
- ¿Por qué los problemas NP completos son más difíciles que los problemas NP si un problema NP puede reducirse a un problema NP completo?
- ¿Qué tipo de algoritmos se usaron en la generación de mapas aleatorios de los mapas de Age of Empires II?
- ¿Qué debo hacer para mejorar el pensamiento algorítmico, especialmente para la programación dinámica?
- Deje G (V, E) ser un gráfico conectado, no dirigido, dar un algoritmo O (| V | + | E |) para calcular una ruta en G que atraviesa cada borde en E exactamente una vez en cada dirección?
- Cómo dominar algoritmos, estructuras de datos y desarrollar un enfoque de resolución de problemas
