Programación ponderada de trabajos | Conjunto 2 (usando LIS)

Dados N trabajos donde cada trabajo está representado por los siguientes tres elementos.
1. Hora de inicio 
2. Hora de finalización 
3. Beneficio o valor asociado
Encuentre el subconjunto de trabajos de beneficio máximo tal que no haya dos trabajos en el subconjunto que se superpongan.

Ejemplos:  

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:  
Job 1: {1, 2, 50}
Job 4: {2, 100, 200}

Explanation: We can get the maximum profit by 
scheduling jobs 1 and 4 and maximum profit is 250.

En una publicación anterior , hemos discutido sobre el problema de la programación ponderada de trabajos. Discutimos una solución de DP donde básicamente incluimos o excluimos el trabajo actual. En esta publicación, se analiza otra solución DP interesante en la que también imprimimos los trabajos. Este problema es una variación del problema estándar de subsecuencia creciente más larga (LIS) . Necesitamos un ligero cambio en la solución de programación dinámica del problema LIS.

Primero tenemos que clasificar los trabajos según la hora de inicio. Deje que job[0..n-1] sea la array de trabajos después de la clasificación. Definimos el vector L de tal manera que L[i] es en sí mismo un vector que almacena la Programación ponderada de trabajos de trabajo[0..i] que termina en trabajo[i]. Por lo tanto, para un índice i, L[i] puede escribirse recursivamente como – 

L[0] = {job[0]}
L[i] = {MaxSum(L[j])} + job[i] where j < i and job[j].finish <= job[i].start
     = job[i], if there is no such j

Por ejemplo, considere los pares {3, 10, 20}, {1, 2, 50}, {6, 19, 100}, {2, 100, 200}

After sorting we get, 
{1, 2, 50}, {2, 100, 200}, {3, 10, 20}, {6, 19, 100}

Therefore,
L[0]: {1, 2, 50}
L[1]: {1, 2, 50} {2, 100, 200}
L[2]: {1, 2, 50} {3, 10, 20}
L[3]: {1, 2, 50} {6, 19, 100}

Elegimos el vector con mayor ganancia. En este caso, L[1].

A continuación se muestra la implementación de la idea anterior: 

// C++ program for weighted job scheduling using LIS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
// A job has start time, finish time and profit.
struct Job
{
    int start, finish, profit;
};
 
// Utility function to calculate sum of all vector
// elements
int findSum(vector<Job> arr)
{
    int sum = 0;
    for (int i = 0; i < arr.size(); i++)
        sum +=  arr[i].profit;
    return sum;
}
 
// comparator function for sort function
int compare(Job x, Job y)
{
    return x.start < y.start;
}
 
// The main function that finds the maximum possible
// profit from given array of jobs
void findMaxProfit(vector<Job> &arr)
{
    // Sort arr[] by start time.
    sort(arr.begin(), arr.end(), compare);
 
    // L[i] stores Weighted Job Scheduling of
    // job[0..i] that ends with job[i]
    vector<vector<Job>> L(arr.size());
 
    // L[0] is equal to arr[0]
    L[0].push_back(arr[0]);
 
    // start from index 1
    for (int i = 1; i < arr.size(); i++)
    {
        // for every j less than i
        for (int j = 0; j < i; j++)
        {
            // L[i] = {MaxSum(L[j])} + arr[i] where j < i
            // and arr[j].finish <= arr[i].start
            if ((arr[j].finish <= arr[i].start) &&
                (findSum(L[j]) > findSum(L[i])))
                L[i] = L[j];
        }
        L[i].push_back(arr[i]);
    }
 
    vector<Job> maxChain;
 
    // find one with max profit
    for (int i = 0; i < L.size(); i++)
        if (findSum(L[i]) > findSum(maxChain))
            maxChain = L[i];
 
    for (int i = 0; i < maxChain.size(); i++)
        cout << "(" <<  maxChain[i].start << ", " <<
             maxChain[i].finish << ", "
             <<  maxChain[i].profit << ") ";
}
 
// Driver Function
int main()
{
    Job a[] = { {3, 10, 20}, {1, 2, 50}, {6, 19, 100},
                {2, 100, 200} };
    int n = sizeof(a) / sizeof(a[0]);
 
    vector<Job> arr(a, a + n);
 
    findMaxProfit(arr);
 
    return 0;
}

// Java program for weighted job
// scheduling using LIS
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
 
class Graph{
 
// A job has start time, finish time
// and profit.
static class Job
{
    int start, finish, profit;
 
    public Job(int start, int finish,
               int profit)
    {
        this.start = start;
        this.finish = finish;
        this.profit = profit;
    }
};
 
// Utility function to calculate sum of all
// ArrayList elements
static int findSum(ArrayList<Job> arr)
{
    int sum = 0;
     
    for(int i = 0; i < arr.size(); i++)
        sum += arr.get(i).profit;
         
    return sum;
}
 
// The main function that finds the maximum
// possible profit from given array of jobs
static void findMaxProfit(ArrayList<Job> arr)
{
     
    // Sort arr[] by start time.
    Collections.sort(arr, new Comparator<Job>()
    {
        @Override
        public int compare(Job x, Job y)
        {
            return x.start - y.start;
        }
    });
     
    // sort(arr.begin(), arr.end(), compare);
 
    // L[i] stores Weighted Job Scheduling of
    // job[0..i] that ends with job[i]
    ArrayList<ArrayList<Job>> L = new ArrayList<>();
    for(int i = 0; i < arr.size(); i++)
    {
        L.add(new ArrayList<>());
    }
 
    // L[0] is equal to arr[0]
    L.get(0).add(arr.get(0));
 
    // Start from index 1
    for(int i = 1; i < arr.size(); i++)
    {
         
        // For every j less than i
        for(int j = 0; j < i; j++)
        {
             
            // L[i] = {MaxSum(L[j])} + arr[i] where j < i
            // and arr[j].finish <= arr[i].start
            if ((arr.get(j).finish <= arr.get(i).start) &&
                (findSum(L.get(j)) > findSum(L.get(i))))
            {
                ArrayList<Job> copied = new ArrayList<>(
                    L.get(j));
                L.set(i, copied);
            }
        }
        L.get(i).add(arr.get(i));
    }
 
    ArrayList<Job> maxChain = new ArrayList<>();
 
    // Find one with max profit
    for(int i = 0; i < L.size(); i++)
        if (findSum(L.get(i)) > findSum(maxChain))
            maxChain = L.get(i);
 
    for(int i = 0; i < maxChain.size(); i++)
    {
        System.out.printf("(%d, %d, %d)\n",
              maxChain.get(i).start,
              maxChain.get(i).finish,
              maxChain.get(i).profit);
    }
}
 
// Driver code
public static void main(String[] args)
{
    Job[] a = { new Job(3, 10, 20),
                new Job(1, 2, 50),
                new Job(6, 19, 100),
                new Job(2, 100, 200) };
 
    ArrayList<Job> arr = new ArrayList<>(
        Arrays.asList(a));
 
    findMaxProfit(arr);
}
}
 
// This code is contributed by sanjeev2552

Producción: 

(1, 2, 50) (2, 100, 200)

Podemos optimizar aún más la solución DP anterior eliminando la función findSum(). En cambio, podemos mantener otro vector/array para almacenar la suma de la máxima ganancia posible hasta el trabajo i. La implementación se puede ver aquí .

La complejidad temporal de la solución de Programación Dinámica anterior es O(n ² ) donde n es el número de Trabajos. 
El espacio auxiliar utilizado por el programa es O(n ² ).

Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.