零件最大加工报酬问题
用机器加工一批零件。每一个零件加工完可获得一定的加工报酬，并有加工时间要求：零件加工必须从某一时刻开始，到某一时刻结束，一次性连续加工完。
零件的加工时间要求可能有冲突，但机器只有一台，在某个时刻，只能加工一个零件。一个零件开始时间和另一个零件结束时间相同不算冲突。
请实现如下需求：在一批零件中，合理选择零件加工，输出满足上述条件的
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=0x8fffffff;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<<" ";}