Puede abordar esto utilizando la Programación lineal de enteros y utilizar los solucionadores de ILP existentes para calcularlo por usted: desea maximizar
valorA * a + … [a, b, … serán valores booleanos que denotan si ha elegido un objeto en particular]
habiendo satisfecho las condiciones
- ¿Qué algoritmo es usado por la función Java () de la búsqueda de subcadenas?
- ¿Qué algoritmo se utiliza en los puntos de calificación para las clasificaciones de cricket ICC?
- ¿Puedo volverme competente en estructuras de datos y algoritmos sin leer el libro CLRS?
- ¿Cuál es la solución eficiente para SPOJ CCROSSX?
- ¿Por qué sigo fallando la introducción a los algoritmos en la escuela de posgrado?
- pesoA * a +… <= tamaño de mochila
- a + c <= 1
- a, b, … = 0 o 1
Puede haber una forma menos genérica que ahora no veo, aunque creo que no se puede esperar nada mejor porque incluso ignorando las propiedades de la mochila (tamaño, peso, valores) obtienes una versión mucho más simple donde solo quieres tome tantos objetos como sea posible bajo las restricciones de que a no puede estar junto con c etc. Esta versión simplificada es un problema de conjunto independiente y ya es NP-hard, por lo que no puede esperar ningún algoritmo polinomial para su versión más difícil. Sin embargo, los solucionadores de ILP deberían resolver esto fácilmente, incluso sin dar ninguna garantía de polinomialidad.
