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