问题描述：
有n个作业，每个作业可获得效益p，要在规定期限d内完成，求如何安排作业使所获效益最大？
/*作业排序
*/
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define N 5//作业个数
struct node{
int p;//效益
int d;//期限
bool operator<(const node&t)const{
return p>t.p;
}
};
node work[N+1]={{0,0},{20,2},{15,2},{10,1},{5,3},{1,3}};
int J[N+1];//表示最优解中的第i个作业
void JS(){
J[0]=0;
J[1]=1;
int k=1,r;
for(int i=2;i<=N;i++){
r=k;
while(work[J[r]].d>work[i].d&&work[J[r]].d!=r)r--;
if(work[J[r]].d<=work[i].d&&work[i].d>r){//把i插入J
for(int j=k;j>r;j--)J[j+1]=J[j];
J[r+1]=i;
k++;
}
}
}
int main(){
sort(work+1,work+N+1);//先按照效益大小排序
JS();
cout<<"作业分配为："<<endl;
for(int i=1;i<=N;i++)cout<<"第"<<i<<"天分配 作业"<<J[i]<<endl;
return 0;
}
更快速的作业排序：
/*快速作业排序
总是把效益最高的尽量往后面的天数安排
并查集
*/
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define N 7//作业个数
struct node{
int p;//效益
int d;//期限
bool operator<(const node&t)const{
return p>t.p;
}
};
node work[N+1]={{0,0},{35,4},{30,2},{25,4},{20,3},{15,4},{10,8},{5,3}};
int J[N+1];//表示最优解中的第i个作业
//并查集begin
int F[N+1];
int FIND(int x)
{
if(F[x]!=x)
F[x]=FIND(F[x]);
return F[x];
}
void UNION(int x,int y)//将x与y合并
{
int f1=FIND(x);
int f2=FIND(y);
if(f1!=f2)
F[f2]=f1;
}
//并查集end
void FJS(){
for(int i=0;i<=N;i++){
F[i]=i;
}
int k=0;
for(int i=1;i<=N;i++){
int j=FIND(min(N,work[i].d));
if(F[j]!=0){
k++;
J[k]=i;
int l=FIND(F[j]-1);
UNION(l,j);
F[j]=F[l];
}
}
}
int main(){
sort(work+1,work+N+1);//先按照效益大小排序
FJS();
cout<<"作业分配为："<<endl;
for(int i=1;i<=N;i++)cout<<J[i]<<" ";
return 0;
}