“<”,javasciprt下jquery函数$.post执行无响应的原因
问题描述:
有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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。