Programación ponderada de trabajos – Part 1

Dados N trabajos donde cada trabajo está representado por los siguientes tres elementos.

  1. Hora de inicio
  2. Tiempo de finalización
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *