零件最大加工报酬问题

发布时间:2016-12-7 1:53:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"零件最大加工报酬问题",主要涉及到零件最大加工报酬问题方面的内容,对于零件最大加工报酬问题感兴趣的同学可以参考一下。

用机器加工一批零件。每一个零件加工完可获得一定的加工报酬,并有加工时间要求:零件加工必须从某一时刻开始,到某一时刻结束,一次性连续加工完。 零件的加工时间要求可能有冲突,但机器只有一台,在某个时刻,只能加工一个零件。一个零件开始时间和另一个零件结束时间相同不算冲突。 请实现如下需求:在一批零件中,合理选择零件加工,输出满足上述条件的 1)最大加工报酬。 2)最优零件加工序列:能获得最大加工报酬的所有零件加工序列(可能有多组序列) 说明:  每一个零件的信息包括:零件编号,零件加工报酬,加工开始时间,加工结束时间。每个零件的零件编号不能重复。      示例:         零件信息——                   零件编号 零件加工报酬 加工开始时间 加工结束时间                       1         10           1            2                       2         15           5            6                       3         20           4            6                       4         15           1            5                       5         20           4            6 计算结果:  1)最大加工报酬:30 2)最优零件加工序列: 有三个,分别是{1,3}、{1,5}、 {4,2} 解法: typedef struct product { int id; int reward; int start_time; int end_time; }Product; Product P[N]; 本题可用动态规划来解,首先将各个零件依据零件的加工结束时间从小到大进行排序,然后定义一个数组r[N],其中r[i]为到第i个为止的最大报酬, 则r[i]=max{r[j]+P[i].reward,0<=j<i,且第i个零件的加工时间和第j个零件的加工时间不重合},最后的最大报酬为max{r[i],0<=i<n},本题与数组的最长递增子序列有几分相似之处。 为了求得最优零件加工序列需要用数组pre[N]保存满足r[i]=max{r[j]+P[i].reward,0<=j<i,且第i个零件的加工时间和第j个零件的加工时间不重合} 条件的零件。最后遍历r[N]一遍,找出满足r[i]==maxreward的零件的id并根据pre[N]数组,打印出最优零件加工序列。 具体代码如下: #include<iostream> #include<algorithm> using namespace std; typedef struct product//零件信息 { int id; int reward; int start_time; int end_time; }Product; bool comp(Product p1,Product p2);//零件排序依据 bool overlap(Product p1,Product p2);//判段区间是否交叉 void max_reward(Product *P,int n);//求最大报酬 void print_path(int m,int *pre,Product *P);//打印最优序列 int main() { int n; cin>>n; Product *P=new Product[n]; int i; for(i=0;i<n;i++) cin>>P[i].id>>P[i].reward>>P[i].start_time>>P[i].end_time; sort(P,P+n,comp); max_reward(P,n); delete []P; return 0; } bool comp(Product p1,Product p2) { return p1.end_time<p2.end_time; } bool overlap(Product p1,Product p2) { if(p1.end_time <=p2.start_time||p2.end_time<=p1.start_time) return false; return true; } void max_reward(Product *P,int n) { if(P==NULL||n<=0) return; int *r=new int[n]; int *pre=new int[n]; int i,j; for(i=0;i<n;i++) pre[i]=-1; for(i=0;i<n;i++) { r[i]=P[i].reward; for(j=0;j<i;j++) { if(!overlap(P[i],P[j])&&(r[i]<r[j]+P[i].reward)) { r[i]=r[j]+P[i].reward; pre[i]=j; } } } int maxreward=(signed int)0x80000000; for(i=0;i<n;i++) { if(r[i]>maxreward) maxreward=r[i]; } cout<<"The maximum reward is "<<maxreward<<endl; int k=1; for(i=0;i<n;i++) { if(r[i]==maxreward) { cout<<k++<<" : "; print_path(i,pre,P); cout<<endl; } } delete []r; delete []pre; } void print_path(int m,int *pre,Product *P) { if(m<0||pre==NULL||P==NULL) return; if(m==0) { cout<<P[m].id<<" "; return; } print_path(pre[m],pre,P); cout<<P[m].id<<" "; } 时间复杂度为O(n^2),空间复杂度为O(n);

上一篇:exit(0)与exit(1)、return区别
下一篇:Hadoop分布式文件系统和OpenStack对象存储有何不同

相关文章

相关评论