=b的作业集合将N1的作业按a非减序排序, N2中的作业按照b非增序排序, 则N1作业接N2作业构成最优顺序.
2．最长公共子序列问题
（1）最长公共子序列的结构
解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。
事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理：
定理: LCS的最优子结构性质
设序列X=和Y=的一个最长公共子序列Z=，则：1. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；
2. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；
3. 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。
（2）子问题的递归结构
由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。
与矩阵连乘积最优计算次序问题类似，我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=，Yj=。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。（3）计算最优值
直接利用(2.2)式容易写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。
计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。
核心代码
1.流水作业调度
void Sord(struct Jnode s[],int n)
{
int i, j, k, m;
for(i=1; i<=n-1; i++)
{
k=i;
while(k<=n&&s[k].tag!=0)
k++;
if(k>n)
break;
else{
for(j=k+1; j<=n; j++)
if(s[j].tag==0)
if(s[k].a>s[j].a)
k=j;
JSwap(s[i],s[k]);
}
}
for(j=i; j<=n-1; j++)
{
k=j;
for(m=j+1; m<=n; m++)
if(s[k].bk=m;JSwap(s[j], s[k]);
}
}
2．最长公共子序列
void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
int i, j;
//LCS:最长公共子序列
//c[X][Y]:保存X，Y的子序列的LCS
//b[X][Y]:保存c[X][Y]的各项比较结果
//当i=0或j=0时，LCS必为0（因为其中一个数组长度为0）
for(i = 0; i <= m; i++)
c[i][0] = 0;
for(j = 1; j <= n; j++)
c[0][j] = 0;
for(i = 1; i<= m; i++)
{
for(j = 1; j <= n; j++)
{
if(x[i-1] == y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 0;
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 1;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = -1;
}
}
}
}
void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 0)
{
PrintLCS(b, x, i-1, j-1);
printf(\"%c \
}
else if(b[i][j] == 1)
PrintLCS(b, x, i-1, j);
else
PrintLCS(b, x, i, j-1);
}
结果分析
1．流水作业调度：
2．最长公共子序列：
