算法设计与分析背包问题及作业排序 第2页
//作业排序
#include "iomanip.h"
#include <iostream.h>
void JOB_S(int n,int *D);
void JOB_S(int n,int *D)
{
int i,k,r;
int *J=new int[n+1];
k=1;
D[0]=0;
J[0]=0;
J[1]=1;
for(i=2;i<=n;i++)
{
r=k;
while(D[J[r]]>D[i] && D[J[r]]!=r)
r=r-1;
if(D[J[r]]<=D[i] && D[i]>r)
{
for(int x=k;x>=r+1;x--)
J[x+1]=J[x];
J[r+1]=i;
k++;
}
}
cout<<"该作业的最优处理顺序为:";
for(i=1;i<=k;i++)
cout<<setw(4)<<J[i];
cout<<endl;
}
void main()
{
int *D,*P; //定义变量数组，采用动态分配内存
int i,n;
cout<<"请输入要处理的作业数n:";
cin>>n;
D=new int[n+1]; //作业的截止期限数组
P=new int[n+1]; //作业的效益数组
cout<<"请输入作业i的期限值D(1-"<<n<<")"<<endl;
for(i=1;i<=n;i++)
{
cout<<"作业"<<i<<"的期限：";
cin>>D[i];
}
cout<<endl;
cout<<"请输入作业i的效益值P(1-"<<n<<")"<<endl;
for(i=1;i<=n;i++)
{
cout<<"作业"<<i<<"的效益：";
cin>>P[i];
}
cout<<endl;
JOB_S(n,D);
}