El algoritmo codicioso no puede ayudar en ese caso. Y no se puede comparar con problemas de mochila fraccionales o 0-1. El primero podría resolverse mediante un algoritmo codicioso en O (n) y el segundo es NP.
El problema que tiene podría ser la fuerza bruta en O (2 ^ n). Pero podría optimizarlo usando programación dinámica.
1) Ordenar intervalos por hora de inicio.
2) Inicialice int [] cost = new int [jobs.length] con Integer.MIN_VALUE (o cualquier valor negativo);
3) Defina la siguiente rutina recursiva (aquí está Java):
private int findCost(Job[] jobs, int k, int[] costs) {
if(k >= jobs.length) {
return 0;
}
if(costs[k] < 0) {
int x = findNextCompatibleJob(jobs, k);
int sumK = jobs[k].cost + findCost(jobs, x, costs);
int sumK1 = findCost(jobs, k + 1, costs);
costs[k] = Math.max(sumK, sumK1);
}
return costs[k];
}
private int findNextCompatibleJob(Job[] jobs, int k) {
int finish = jobs[k].finish;
for(int i = k + 1; i < jobs.length; i++) {
if(jobs[i].start > finish) {
return i;
}
}
return Integer.MAX_VALUE;
}
4) Comience la recursión con k = 0;
Solo he implementado la rutina de recursión, mientras que otras partes son triviales. Consideré que cualquier costo es> = 0. Si podría haber trabajos con costos negativos, necesitamos agregar un cheque para eso y simplemente aprobar esos trabajos sin tener en cuenta.
Sí, es equivalente a un problema de mochila. Considere la hora de finalización del trabajo y prepare la mesa como una mochila. Antes de leer la siguiente solución, consulte el problema de la mochila y su solución.
También puede imprimir los trabajos programados recorriendo la tabla:
La complejidad es la misma que el problema de la mochila.
fuente