problema de secuenciación de empleo

En este artículo, vamos a ver cómo el problema secuenciación de trabajo se puede resolver utilizando la estrategia codiciosa ?

Planteamiento del problema:

Teniendo en cuenta una serie de trabajos en los que cada trabajo tiene un plazo y un beneficio. Beneficio se puede ganar solamente if el trabajo está terminado antes de la fecha límite. También se da que cada trabajo tiene una sola unidad de tiempo, por lo que el plazo mínimo posible para cualquier trabajo es 1. Cómo maximizar el beneficio total if sólo un trabajo se puede programar a la vez. Imprimir la secuencia de orden de la Id para maximizar el beneficio total.

Ejemplo de entrada

JobIDDeadlineProfit

1 4 30
2 2 20
3 2 60
4 2 30
5 1 10
6 4 80

ejemplo de salida: 4 3 1 6

Problema explicación:

En primer lugar, olvidarse del algoritmo voraz. Vamos a resolver con nuestra intuición. Dado que el problema es que la intuición de maximizar el beneficio para seleccionar dice puestos de trabajo en orden decreciente de acuerdo a su beneficio. Eso significa que para seleccionar el máximo beneficio primero, luego el segundo un máximo de beneficios y así sucesivamente. Selección de trabajos While que sólo necesitan para realizar un seguimiento de si se puede acabar en plazo.

Así que empecemos …

Se puede observar a partir de la tabla de trabajos que hay cuatro puestos de trabajo con la fecha límite prevista como máximo 2. Por lo tanto, sólo podemos seleccionar un máximo de 2 puestos de trabajo de estos puestos de trabajo desde cada 4 trabajo tomar 1 unidad de tiempo de proceso. (Observación local)

A tiempo 0:

Seleccionar un beneficio máximo con fecha límite a lo sumo 2 Identificación
de empleo: 3, fecha límite: 2, opción válida, procesar el trabajo
beneficio en el tiempo 0: 60

en el tiempo 1:

Seleccione una ganancia máxima de la fecha límite jobswith restante como máximo 2 Identificación
de empleo: 4, fecha límite: 2, opción válida, procesar el trabajo
beneficio en el tiempo 1: 60 + 30
Es por eso lata ‘t elegir trabajo con identificador de 5 y 2

en el momento 2:

Seleccionar máxima de un remanente con mayor plazo de 2 Identificación
de empleo: 6, fecha límite: 4, opción válida, procesar el trabajo
las ganancias de tiempo de 2: 60 + 30 + 80

En tiempo de 3:

Select trabajo
con el ID de empleo: 1, fecha límite: 4, opción válida, procesar el trabajo
secuencia de trabajo: 3 4 6 1
Finalmente total de ganancia = 60 + 30 + 80 + 30 = 200

_173 _

otra opción podría haber resultado mejor (se puede comprobar !!!!). Así, la solución se optimiza y hemos encontrado la solución máxima.

Ahora, revisemos lo que hemos hecho. De hecho, hemos ordenado la mesa de trabajo de acuerdo con el beneficio máximo y luego han hecho la mejor elección local en cada iteración para reducir el tamaño del problema y en última instancia, para alcanzar la meta. En pocas palabras, hemos utilizado la técnica codiciosos intuitiva y algoritmo voraz ha resuelto con éxito el problema de la secuencia de trabajo.

Ahora al código sólo tiene que seguir el siguiente pasos que son nada más que lo que hicimos la solución del ejemplo anterior:

  1. Crear una clase para definir puestos de trabajo
  2. class job
    {
    public:
    int jobid; //job id
    int deadline; //deadline
    int profit; //profit of the job
    };

  3. Para tomar la entrada se ha utilizado el concepto de arreglo de punteros a los objetos de trabajo. trabajo * obj [n]; // array de puntero a ofertas de trabajo (puestos de trabajo a saber)
  4. maxProfit función ()

    • Ordenar todos los puestos de trabajo en orden de ganancia decreciente. Para este
      do hemos definido nuestra propia función compare y STL usada especie.
    • bool mycompare(job *x,job *y)//boolean function
      {
      //sort as per decreasing profite
      return x->profit>y->profit;
      }
      sort(obj,obj+n,mycompare);

    • Encuentra la fecha límite máximo, que sea máximo .
    • Crear tienda [max] a la secuencia de almacenamiento de trabajos
      Crear ranura [max] a la marca ocupada ranuras
    • para i = 0: nº de puestos de trabajo
    • // now pick the job with max deadline from 
      // that deadline traverse array backto find an empty slot
      for(int j=(obj[i]->deadline)-1;j>=0;j--)
      {
      if(slot[j]==false){ // slot is empty
      // count the total profit
      profit+=obj[i]->profit;
      store[j]=obj[i]->jobid;
      slot[j]=true;
      break;
      }
      }

    • Imprimir la tienda gama para encontrar la secuencia de trabajo e imprimir ganancias la que se emite el máximo beneficio

C ++ aplicación de Job problema de secuenciación

#include<bits/stdc++.h>
using namespace std;
// define the class for the job
class job
{
public:
int jobid;
int deadline;
int profit;
};
// our compare function to sort
bool mycompare(job *x,job *y)//boolean function
{
//sort as per decreasing profit
return x->profit>y->profit;
}
int maxProfit(job** obj,int n){
int max=0,profit=0;;
//find maximum deadline
for(int i=0;i<n;i++){
if(i==0){
max=obj[i]->deadline;
}
else{
if(obj[i]->deadline>max)
max=obj[i]->deadline;
}
}
sort(obj,obj+n,mycompare);
// create array of max deadline size
int store[max]={0}; // empty array initially
bool slot[max]={false}; //all slots empty initially
for(int i=0;i<n;i++)
{
// now pick the job with max deadline and from
// that deadline traverse array back to find an empty slot
for(int j=(obj[i]->deadline)-1;j>=0;j--)
{
if(slot[j]==false) // slot is empty
{
// count the total profit
profit+=obj[i]->profit;
store[j]=obj[i]->jobid;
slot[j]=true;
break;
}
}
}
// printing the job sequence
cout<<"jobs sequence is:"<<"t";
for(int i=0;i<max;i++)
{
if(slot[i])
cout<<store[i]<<" ";
}
return profit; //return profit
}
int main()
{
int n,size,max,totalprofit=0;
cout<<"enter the no. of jobs:";
cin>>n;
job *obj[n]; //array of pointer to jobs(jobs namely)
// user input and finding maximum deadline
for(int i=0;i<n;i++)
{
obj[i]=(job*)malloc(sizeof(struct job));
cout<<"enter jobid,deadline and profit of job "<<i+1<<endl;
cin>>obj[i]->jobid;
cin>>obj[i]->deadline;
cin>>obj[i]->profit;
}
totalprofit=maxProfit(obj,n); //total profit
cout<<"ntotal profit is "<<totalprofit<<"n";
return 0;
}

salida

enter the no. of jobs:6
enter jobid,deadline and profit of job 1
1 4 30
enter jobid,deadline and profit of job 2
2 2 20
enter jobid,deadline and profit of job 3
3 2 60
enter jobid,deadline and profit of job 4
4 2 30
enter jobid,deadline and profit of job 5
5 1 10
enter jobid,deadline and profit of job 6
6 4 80
jobs sequence is: 4 3 1 6
total profit is 200


Deja un comentario

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