动态规划是通过组合子问题的解而解决整个问题。
动态规划算法设计可以分为4个步骤
（1）描述最优解的结构
（2）递归定义最优解的值
（3）按自底向上的方式计算最优解的值
（4）由计算出的结果构造一个最优解
装配线调度实现(算法导论192页)
参考算法导论 第15章
#include<stdio.h>
#include<stdlib.h>
int schedule(int a[][6],int t[][5],int e[],int x[])
{
int f[2][6];
int l[2][5];
int totalMin;
int lastL;
int i,k;
f[0][0]=e[0]+a[0][0];
f[1][0]=e[1]+a[1][0];
for(i=1;i<6;i++)
{
if(f[0][i-1]<(f[1][i-1]+t[1][i-1]))
{
f[0][i]=f[0][i-1]+a[0][i];
l[0][i-1]=1;
}else{
f[0][i]=f[1][i-1]+t[1][i-1]+a[0][i];
l[0][i-1]=2;
}
if(f[1][i-1]<(f[0][i-1]+t[0][i-1]))
{
f[1][i]=f[1][i-1]+a[1][i];
l[1][i-1]=2;
}else{
f[1][i]=f[0][i-1]+t[0][i-1]+a[1][i];
l[1][i-1]=1;
}
}
for(i=0;i<2;i++)
{
for(k=0;k<6;k++)
{
printf("%d ",f[i][k]);
}
printf("\n");
}
if((x[0]+f[0][5])<(x[1]+f[1][5]))
{
totalMin=x[0]+f[0][5];
lastL=1;
}else{
totalMin=x[1]+f[1][5];
lastL=2;
}
printf("totalMin=%d\n",totalMin);
if(lastL==1)
{
printf("S (1,6) ");
k=0;
}else{
printf("S (2,6) ");
k=1;
}
for(i=4;i>=0;i--)
{
if(l[k][i]==1)
{
printf("S (1, %d) ",i+1);
k=0;
}else{
printf("S (2, %d) ",i+1);
k=1;
}
}
printf("\n");
}
int main()
{
int a[2][6]={{7,9,3,4,8,4},{8,5,6,4,5,7}};
int t[2][5]={{2,3,1,3,4},{2,1,2,2,1}};
int e[2]={2,4};
int x[2]={3,2};
schedule(a,t,e,x);
}