Tengo un problema que en la superficie se ve como 0-1 mochila. Tengo un conjunto de posibles "candidatos" que pueden ser elegidos (o no), cada candidato tiene un "peso" (costo) y un "valor" potencial. Si este fuera todo el problema, usaría un enfoque DP y terminaría con eso. Pero aquí está la curva: hay "restricciones de partición" en los posibles candidatos que pueden estar en la solución final.0-1 Mochila con restricciones de partición
Lo que quiero decir es que el espacio candidato se divide en clases de equivalencia discretas. Para mi problema particular, hay alrededor de 300 candidatos y 12 posibles clases de equivalencia. Existen "reglas de negocio" que dicen que solo puedo tener hasta 3 candidatos de clase C1 y 6 de C2, etc.
Esta restricción sugiere un enfoque de tipo de búsqueda de gráficos utilizando técnicas de ramificación y unión o algunas Otra forma de poda, sin embargo, estoy un poco perplejo en cuanto a cómo comenzar, ya que solo estoy familiarizado con la solución DP a 0-1 Knapsack. ¿Qué técnicas/enfoques podrían ser adecuados para este problema? También pensé en utilizar una biblioteca de programación de restricciones pero no estoy seguro de si sería capaz de encontrar una solución.