動態(tài)規(guī)劃是通過組合子問題的解而解決整個問題。
動態(tài)規(guī)劃算法設(shè)計可以分為4個步驟
（1）描述最優(yōu)解的結(jié)構(gòu)
（2）遞歸定義最優(yōu)解的值
（3）按自底向上的方式計算最優(yōu)解的值
（4）由計算出的結(jié)果構(gòu)造一個最優(yōu)解
裝配線調(diào)度實現(xiàn)(算法導(dǎo)論192頁)
參考算法導(dǎo)論 第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);
}