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