Si encuentras algún detalle que no entiendes puedes comentarlo y trataremos de ayudarte rápidamente.
Solución:
En general, este problema es el problema de cobertura máxima, que es NP-difícil, por lo que no podrá encontrar la solución óptima por ningún método sustancialmente más rápido que la fuerza bruta. (Como mencioné, para un problema de su tamaño, la fuerza bruta aún es factible).
Sin embargo, una modificación de su estrategia (para elegir los intervalos de tiempo con los totales más altos) funciona razonablemente bien.
En realidad, no tiene sentido elegir inmediatamente todos los intervalos de tiempo con los totales más altos: si todos tienen los mismos estudiantes, entonces esto no es mejor que simplemente elegir uno de los intervalos de tiempo. En su lugar, podemos:
- Elegir una franja horaria con el mayor número total de alumnos.
- Elimine a todos los estudiantes que pueden llegar a ese intervalo de tiempo de la consideración. Vuelva a calcular los totales para los estudiantes restantes.
- Repita los pasos 1 y 2 hasta que haya elegido $k=5$ intervalos de tiempo.
Según el artículo de wikipedia, este algoritmo logra una relación de aproximación de $1 – frac1e$; es decir, si puede llegar a $N$ estudiantes con la elección óptima de intervalos de tiempo, este algoritmo llegará al menos a $(1 – frac1e)N$ estudiantes.
Hay otras posibles soluciones aproximadas por ahí; por ejemplo, existe la heurística del gran paso, que considera todas las opciones de intervalos de tiempo $p$ en cada paso, a diferencia de todos los intervalos de tiempo individuales. (Cuando $p=1$, es el algoritmo anterior; cuando $p=k$, es solo fuerza bruta). Ningún algoritmo rápido tiene un rendimiento garantizado mejor que $(1 – frac1e)N$, pero pueden funcionar mejor en algunos casos.
Con esos números, la fuerza bruta todavía es factible. Tienes 30 elige 5 = 142506 combinaciones diferentes. No creo que haya ningún otro algoritmo que no sea la fuerza bruta que garantice obtener la mejor solución, pero una heurística sería organizar a los estudiantes en conjuntos de menor a mayor disponibilidad. Luego clasifique los intervalos de tiempo según la cantidad de estudiantes menos disponibles que coincidan, luego rompa los empates según la cantidad de segundos menos disponibles, etc. Tome el mejor intervalo de tiempo de acuerdo con ese criterio. Elimine a todos los estudiantes que puedan llegar a ese intervalo de tiempo y aplique el mismo algoritmo a los restantes intervalos de tiempo y estudiantes, y continúe hasta que haya alcanzado su número máximo de intervalos de tiempo. En su ejemplo, Frank es el estudiante menos disponible, por lo que las 11 am, como el único horario que puede elegir, es la primera opción. Esto deja a Alice, Bob y Charlotte sin horario y, de ellos, Alice es la menos disponible. Las 9 a. m. y las 10 a. m. se adaptan a Alice, por lo que puede tomar cualquiera de las dos (aunque si tiene en cuenta a los estudiantes que se eliminaron en los pasos anteriores, entonces las 10 a. m. ganan).
Puede combinar los dos: use la heurística hasta que llegue a números lo suficientemente pequeños como para que esté de acuerdo con el uso de la fuerza bruta.
Otra heurística es observar el agrupamiento (¿hay un grupo de estudiantes que esté mayormente disponible por la mañana y otro por la noche) y elegir intervalos de tiempo en diferentes grupos.
En términos prácticos, simplemente varíe el horario de oficina cada semana.
Sección de Reseñas y Valoraciones
No se te olvide dar recomendación a esta noticia si te ayudó.