7.14 PROGRAM TO IMPLEMENT JOB SEQUENCING USING GREEDY METHOD

#include
#include
#include
class jobs
{
private:
int *p;
int *d;
int n;
int k;
public:
int retsize(){return k;}
int jobseq(int []);
void readdata(int);
};
void jobs:: readdata(int x)
{
n=x;
p=new int [n+1];
d= new int [n+1];
cout<<"enter the deadlines:\n";
for(int i=1;i<=n;i++)
cin>>d[i];
cout<<"enter the profits:[in descending order]\n";
for(i=1;i<=n;i++)
cin>>p[i];
}
int jobs::jobseq(int j[])
{
int r,t;
int profit=0;
d[0]=0;j[0]=0;
k=1;
j[1]=1;
profit+=p[1];
for(int i=2;i<=n;i++)
{
r=k;
while(d[j[r]]>d[i] && d[j[r]]!=r)
r--;
if((d[j[r]] <=d[i]) && (d[i]>r))
{
for(t=k;t>=r+1;t--)
j[t+1]=j[t];
profit+=p[i];
j[r+1]=i;
k++;
}
}
return profit;
}
void main()
{
jobs obj;
int optsoln;
int n;
int *j;
int s;
clrscr();
cout<<"enter the no of objects:";
cin>>n;
obj.readdata(n);
j=new int [n+1];
optsoln=obj.jobseq(j);
s=obj.retsize();
cout<<"the solution vector:\n";
for(int i=1;i<=s;i++)
cout< cout<< endl;
cout<<"the optimal solution =" << optsoln< }

OUTPUT:

enter the no of objects:4
enter the deadlines:
2 1 2 1
enter the profits:[in descending order]
100 27 15 10
the solution vector:
2 1
the optimal solution =127