Variante de programación de intervalos ponderados con “multitarea”
Tengo una variante de la programación de intervalos ponderados que no pude encontrar información al respecto: los datos de entrada son intervalos en los cuales las personas están presentes en el área objetivo, su importancia (el “peso”) y la cantidad permitida de visitas al área objetivo. El resultado deberá ser los momentos para visitar el área objetivo para conocer a las personas de mayor importancia (una visita es un punto único en el tiempo, donde se conocen a todas las personas presentes en el momento de la visita, si alguien está presente en múltiples visitas, solo se cuenta una vez).
Intenté resolver esto de forma recursiva sin ninguna memorización, y funciona, pero estoy seguro de que debe haber una forma mejor. Además, ¿este tipo de problema tiene su propio nombre?
davy.ai
Esta variante de programación de intervalos ponderados parece ser una combinación de programación de intervalos y el problema de mochila de elección múltiple, donde el peso del intervalo representa su importancia y la cantidad permitida de visitas representa la capacidad de la mochila. El objetivo es maximizar el peso total de los intervalos al respetar la restricción de capacidad.
Una forma de resolver este problema es utilizar programación dinámica con memorización. Podemos ordenar los intervalos por sus tiempos finales en orden ascendente y definir un estado (i, c) como el peso total máximo alcanzable al visitar los intervalos del 1 al i con un máximo de c visitas. Luego, podemos calcular recursivamente el valor de cada estado basado en dos casos: o bien el intervalo i-ésimo no se visita, o bien se visita y su peso se suma al peso máximo alcanzable al visitar intervalos hasta el i-1 con c-1 visitas. El caso base es cuando i=0 o c=0, donde el peso máximo es 0.
Para evitar cálculos redundantes, podemos almacenar en caché el valor de cada estado en una tabla de memorización y reutilizarlo si se ha calculado anteriormente. La respuesta final es el peso máximo alcanzable con un máximo de k visitas, donde k es la cantidad permitida de visitas.
Este problema no parece tener un nombre estándar, pero se puede ver como una variación del clásico problema de programación de intervalos ponderados.