Dados N trabajos donde cada trabajo está representado por los siguientes tres elementos.
- Hora de inicio
- Tiempo de finalización
- Beneficio o Valor Asociado (>= 0)
Encuentre el subconjunto de trabajos de ganancia máxima tal que no haya dos trabajos en el subconjunto que se superpongan.
Ejemplo:
Input: Number of Jobs n = 4 Job Details {Start Time, Finish Time, Profit} Job 1: {1, 2, 50} Job 2: {3, 5, 20} Job 3: {6, 19, 100} Job 4: {2, 100, 200} Output: The maximum profit is 250. We can get the maximum profit by scheduling jobs 1 and 4. Note that there is longer schedules possible Jobs 1, 2 and 3 but the profit with this schedule is 20+50+100 which is less than 250.
Aquí se discute una versión simple de este problema donde cada trabajo tiene la misma ganancia o valor. La estrategia codiciosa para la selección de actividades no funciona aquí, ya que un cronograma con más trabajos puede tener una menor ganancia o valor.
El problema anterior se puede resolver utilizando la siguiente solución recursiva.
1) First sort jobs according to finish time. 2) Now apply following recursive process. // Here arr[] is array of n jobs findMaximumProfit(arr[], n) { a) if (n == 1) return arr[0]; b) Return the maximum of following two profits. (i) Maximum profit by excluding current job, i.e., findMaximumProfit(arr, n-1) (ii) Maximum profit by including the current job } How to find the profit including current job? The idea is to find the latest job before the current job (in sorted array) that doesn't conflict with current job 'arr[n-1]'. Once we find such a job, we recur for all jobs till that job and add profit of current job to result. In the above example, "job 1" is the latest non-conflicting for "job 4" and "job 2" is the latest non-conflicting for "job 3".
La siguiente es la implementación del método recursivo ingenuo anterior.
C++
// C++ program for weighted job scheduling using Naive Recursive Method #include <iostream> #include <algorithm> using namespace std; // A job has start time, finish time and profit. struct Job { int start, finish, profit; }; // A utility function that is used for sorting events // according to finish time bool jobComparator(Job s1, Job s2) { return (s1.finish < s2.finish); } // Find the latest job (in sorted array) that doesn't // conflict with the job[i]. If there is no compatible job, // then it returns -1. int latestNonConflict(Job arr[], int i) { for (int j=i-1; j>=0; j--) { if (arr[j].finish <= arr[i-1].start) return j; } return -1; } // A recursive function that returns the maximum possible // profit from given array of jobs. The array of jobs must // be sorted according to finish time. int findMaxProfitRec(Job arr[], int n) { // Base case if (n == 1) return arr[n-1].profit; // Find profit when current job is included int inclProf = arr[n-1].profit; int i = latestNonConflict(arr, n); if (i != -1) inclProf += findMaxProfitRec(arr, i+1); // Find profit when current job is excluded int exclProf = findMaxProfitRec(arr, n-1); return max(inclProf, exclProf); } // The main function that returns the maximum possible // profit from given array of jobs int findMaxProfit(Job arr[], int n) { // Sort jobs according to finish time sort(arr, arr+n, jobComparator); return findMaxProfitRec(arr, n); } // Driver program int main() { Job arr[] = {{3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}}; int n = sizeof(arr)/sizeof(arr[0]); cout << "The optimal profit is " << findMaxProfit(arr, n); return 0; }
Java
// JAVA program for weighted job scheduling using Naive Recursive Method import java.util.*; class GFG { // A job has start time, finish time and profit. static class Job { int start, finish, profit; Job(int start, int finish, int profit) { this.start = start; this.finish = finish; this.profit = profit; } } // Find the latest job (in sorted array) that doesn't // conflict with the job[i]. If there is no compatible job, // then it returns -1. static int latestNonConflict(Job arr[], int i) { for (int j = i - 1; j >= 0; j--) { if (arr[j].finish <= arr[i - 1].start) return j; } return -1; } // A recursive function that returns the maximum possible // profit from given array of jobs. The array of jobs must // be sorted according to finish time. static int findMaxProfitRec(Job arr[], int n) { // Base case if (n == 1) return arr[n-1].profit; // Find profit when current job is included int inclProf = arr[n-1].profit; int i = latestNonConflict(arr, n); if (i != -1) inclProf += findMaxProfitRec(arr, i+1); // Find profit when current job is excluded int exclProf = findMaxProfitRec(arr, n-1); return Math.max(inclProf, exclProf); } // The main function that returns the maximum possible // profit from given array of jobs static int findMaxProfit(Job arr[], int n) { // Sort jobs according to finish time Arrays.sort(arr,new Comparator<Job>(){ public int compare(Job j1,Job j2) { return j1.finish-j2.finish; } }); return findMaxProfitRec(arr, n); } // Driver program public static void main(String args[]) { int m = 4; Job arr[] = new Job[m]; arr[0] = new Job(3, 10, 20); arr[1] = new Job(1, 2, 50); arr[2] = new Job(6, 19, 100); arr[3] = new Job(2, 100, 200); int n =arr.length; System.out.println("The optimal profit is " + findMaxProfit(arr, n)); } } // This code is contributed by Debojyoti Mandal
Python3
# Python3 program for weighted job scheduling using # Naive Recursive Method # Importing the following module to sort array # based on our custom comparison function from functools import cmp_to_key # A job has start time, finish time and profit class Job: def __init__(self, start, finish, profit): self.start = start self.finish = finish self.profit = profit # A utility function that is used for # sorting events according to finish time def jobComparator(s1, s2): return s1.finish < s2.finish # Find the latest job (in sorted array) that # doesn't conflict with the job[i]. If there # is no compatible job, then it returns -1 def latestNonConflict(arr, i): for j in range(i - 1, -1, -1): if arr[j].finish <= arr[i - 1].start: return j return -1 # A recursive function that returns the # maximum possible profit from given # array of jobs. The array of jobs must # be sorted according to finish time def findMaxProfitRec(arr, n): # Base case if n == 1: return arr[n - 1].profit # Find profit when current job is included inclProf = arr[n - 1].profit i = latestNonConflict(arr, n) if i != -1: inclProf += findMaxProfitRec(arr, i + 1) # Find profit when current job is excluded exclProf = findMaxProfitRec(arr, n - 1) return max(inclProf, exclProf) # The main function that returns the maximum # possible profit from given array of jobs def findMaxProfit(arr, n): # Sort jobs according to finish time arr = sorted(arr, key = cmp_to_key(jobComparator)) return findMaxProfitRec(arr, n) # Driver code values = [ (3, 10, 20), (1, 2, 50), (6, 19, 100), (2, 100, 200) ] arr = [] for i in values: arr.append(Job(i[0], i[1], i[2])) n = len(arr) print("The optimal profit is", findMaxProfit(arr, n)) # This code is code contributed by Kevin Joshi
Javascript
<script> // JavaScript program for weighted job scheduling using // Naive Recursive Method // A job has start time, finish time and profit class Job { constructor(start, finish, profit) { this.start = start this.finish = finish this.profit = profit } } // A utility function that is used for // sorting events according to finish time function jobComparator(s1, s2){ return s2.finish - s1.finish; } // Find the latest job (in sorted array) that // doesn't conflict with the job[i]. If there // is no compatible job, then it returns -1 function latestNonConflict(arr, i){ for(let j = i - 1; j >= 0; j--) { if(arr[j].finish <= arr[i - 1].start) return j } return -1 } // A recursive function that returns the // maximum possible profit from given // array of jobs. The array of jobs must // be sorted according to finish time function findMaxProfitRec(arr, n){ // Base case if(n == 1) return arr[n - 1].profit // Find profit when current job is included let inclProf = arr[n - 1].profit let i = latestNonConflict(arr, n) if(i != -1) inclProf += findMaxProfitRec(arr, i + 1) // Find profit when current job is excluded let exclProf = findMaxProfitRec(arr, n - 1) return Math.max(inclProf, exclProf) } // The main function that returns the maximum // possible profit from given array of jobs function findMaxProfit(arr, n){ // Sort jobs according to finish time arr.sort(jobComparator) return findMaxProfitRec(arr, n) } // Driver code let values = [ [3, 10, 20], [1, 2, 50], [6, 19, 100], [2, 100, 200] ] let arr = [] for(let i of values) arr.push(new Job(i[0], i[1], i[2])) let n = arr.length document.write("The optimal profit is ", findMaxProfit(arr, n),"</br>") // This code is code contributed by shinjanpatra </script>
Producción:
The optimal profit is 250
La solución anterior puede contener muchos subproblemas superpuestos. Por ejemplo, si lastNonConflicting() siempre devuelve el trabajo anterior, se llama dos veces a findMaxProfitRec(arr, n-1) y la complejidad del tiempo se convierte en O(n*2 n ). Como otro ejemplo, cuando lastNonConflicting() regresa antes del trabajo anterior, hay dos llamadas recursivas, para n-2 y n-1. En este caso de ejemplo, la recursión se convierte en lo mismo que los números de Fibonacci.
Entonces, este problema tiene ambas propiedades de programación dinámica, subestructura óptima y subproblemas superpuestos .
Al igual que otros problemas de programación dinámica, podemos resolver este problema haciendo una tabla que almacene las soluciones de los subproblemas.
A continuación se muestra una implementación basada en Programación Dinámica.
C++
// C++ program for weighted job scheduling using Dynamic // Programming. #include <algorithm> #include <iostream> using namespace std; // A job has start time, finish time and profit. struct Job { int start, finish, profit; }; // A utility function that is used for sorting events // according to finish time bool jobComparator(Job s1, Job s2) { return (s1.finish < s2.finish); } // Find the latest job (in sorted array) that doesn't // conflict with the job[i] int latestNonConflict(Job arr[], int i) { for (int j = i - 1; j >= 0; j--) { if (arr[j].finish <= arr[i].start) return j; } return -1; } // The main function that returns the maximum possible // profit from given array of jobs int findMaxProfit(Job arr[], int n) { // Sort jobs according to finish time sort(arr, arr + n, jobComparator); // Create an array to store solutions of subproblems. // table[i] stores the profit for jobs till arr[i] // (including arr[i]) int* table = new int[n]; table[0] = arr[0].profit; // Fill entries in M[] using recursive property for (int i = 1; i < n; i++) { // Find profit including the current job int inclProf = arr[i].profit; int l = latestNonConflict(arr, i); if (l != -1) inclProf += table[l]; // Store maximum of including and excluding table[i] = max(inclProf, table[i - 1]); } // Store result and free dynamic memory allocated for // table[] int result = table[n - 1]; delete[] table; return result; } // Driver program int main() { Job arr[] = { { 3, 10, 20 }, { 1, 2, 50 }, { 6, 19, 100 }, { 2, 100, 200 } }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The optimal profit is " << findMaxProfit(arr, n); return 0; }
Java
// JAVA program for weighted job scheduling using Naive // Recursive Method import java.util.*; class GFG { // A job has start time, finish time and profit. static class Job { int start, finish, profit; Job(int start, int finish, int profit) { this.start = start; this.finish = finish; this.profit = profit; } } // Find the latest job (in sorted array) that doesn't // conflict with the job[i]. If there is no compatible // job, then it returns -1. static int latestNonConflict(Job arr[], int i) { for (int j = i - 1; j >= 0; j--) { // finish before next is started if (arr[j].finish <= arr[i - 1].start) return j; } return -1; } static int findMaxProfitDP(Job arr[], int n) { // Create an array to store solutions of // subproblems. table[i] stores the profit for jobs // till arr[i] (including arr[i]) int[] table = new int[n]; table[0] = arr[0].profit; // Fill entries in M[] using recursive property for (int i = 1; i < n; i++) { // Find profit including the current job int inclProf = arr[i].profit; int l = latestNonConflict(arr, i); if (l != -1) inclProf += table[l]; // Store maximum of including and excluding table[i] = Math.max(inclProf, table[i - 1]); } // Store result and free dynamic memory allocated // for table[] int result = table[n - 1]; return result; } // The main function that returns the maximum possible // profit from given array of jobs static int findMaxProfit(Job arr[], int n) { // Sort jobs according to finish time Arrays.sort(arr, new Comparator<Job>() { public int compare(Job j1, Job j2) { return j1.finish - j2.finish; } }); return findMaxProfitDP(arr, n); } // Driver program public static void main(String args[]) { int m = 4; Job arr[] = new Job[m]; arr[0] = new Job(3, 10, 20); arr[1] = new Job(1, 2, 50); arr[2] = new Job(6, 19, 100); arr[3] = new Job(2, 100, 200); int n = arr.length; System.out.println("The optimal profit is " + findMaxProfit(arr, n)); } }
Python3
# Python3 program for weighted job scheduling # using Dynamic Programming # Importing the following module to sort array # based on our custom comparison function from functools import cmp_to_key # A job has start time, finish time and profit class Job: def __init__(self, start, finish, profit): self.start = start self.finish = finish self.profit = profit # A utility function that is used for sorting # events according to finish time def jobComparator(s1, s2): return s1.finish < s2.finish # Find the latest job (in sorted array) that # doesn't conflict with the job[i]. If there # is no compatible job, then it returns -1 def latestNonConflict(arr, i): for j in range(i - 1, -1, -1): if arr[j].finish <= arr[i - 1].start: return j return -1 # The main function that returns the maximum possible # profit from given array of jobs def findMaxProfit(arr, n): # Sort jobs according to finish time arr = sorted(arr, key=cmp_to_key(jobComparator)) # Create an array to store solutions of subproblems. # table[i] stores the profit for jobs till arr[i] # (including arr[i]) table = [None] * n table[0] = arr[0].profit # Fill entries in M[] using recursive property for i in range(1, n): # Find profit including the current job inclProf = arr[i].profit l = latestNonConflict(arr, i) if l != -1: inclProf += table[l] # Store maximum of including and excluding table[i] = max(inclProf, table[i - 1]) # Store result and free dynamic memory # allocated for table[] result = table[n - 1] return result # Driver code values = [(3, 10, 20), (1, 2, 50), (6, 19, 100), (2, 100, 200)] arr = [] for i in values: arr.append(Job(i[0], i[1], i[2])) n = len(arr) print("The optimal profit is", findMaxProfit(arr, n)) # This code is contributed by Kevin Joshi
Javascript
<script> // JavaScript program for weighted job scheduling using // Naive Recursive Method // A job has start time, finish time and profit class Job{ constructor(start, finish, profit){ this.start = start this.finish = finish this.profit = profit } } // A utility function that is used for // sorting events according to finish time function jobComparator(s1, s2){ return s1.finish - s2.finish } // Find the latest job (in sorted array) that // doesn't conflict with the job[i]. If there // is no compatible job, then it returns -1 function latestNonConflict(arr, i){ for(let j=i-1;j>=0;j--){ if (arr[j].finish <= arr[i - 1].start) return j } return -1 } // The main function that returns the maximum // possible profit from given array of jobs function findMaxProfit(arr, n){ // Sort jobs according to finish time arr.sort(jobComparator) // Create an array to store solutions of subproblems. // table[i] stores the profit for jobs till arr[i] // (including arr[i]) let table = new Array(n).fill(null) table[0] = arr[0].profit // Fill entries in M[] using recursive property for(let i=1;i<n;i++){ // Find profit including the current job let inclProf = arr[i].profit let l = latestNonConflict(arr, i) if (l != -1) inclProf += table[l] // Store maximum of including and excluding table[i] = Math.max(inclProf, table[i - 1]) } // Store result and free dynamic memory // allocated for table[] let result = table[n - 1] return result } // Driver code let values = [ [3, 10, 20], [1, 2, 50], [6, 19, 100], [2, 100, 200] ] let arr = [] for(let i of values) arr.push(new Job(i[0], i[1], i[2])) let n = arr.length document.write("The optimal profit is ", findMaxProfit(arr, n),"</br>") // This code is code contributed by shinjanpatra </script>
Producción:
The optimal profit is 250
La Complejidad de Tiempo de la Solución de Programación Dinámica anterior es O(n 2 ). Tenga en cuenta que la solución anterior se puede optimizar para O(nLogn) mediante la búsqueda binaria en la últimaNonConflict() en lugar de la búsqueda lineal. Gracias a Garvit por sugerir esta optimización. Consulte la publicación a continuación para obtener más detalles.
Programación ponderada de trabajos en tiempo O(n Log n)
Referencias:
http://courses.cs.washington.edu/courses/cse521/13wi/slides/06dp-sched.pdf
Este artículo es una contribución de Shivam. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA