现在在刷算法导论，从动态规划问题开始刷起来~ 首先，凝神静气。。。。看算法需要有耐心以及平静的内心，因为有许多推导公式，一定要仔细思考其中的逻辑关系。 开始啦~ 动态规划是指把一个大问题划分为一些子问题，和分治法的区别是这些子问题之间并不是相互独立的而是彼此之间有联系，把它们表示在一张表中边可以利用彼此之间的关系很方便得求得最优解。 动态规划关键步骤： 1.描述最优解的结构； 2.递归表示最优解的值； 3.按照自底向上的方法计算最优值的解； 4.根据据计算的结果构造出最优解；
15.1 装配线调度问题 具体题目参见《算法导论》193面。在这里我只写出自己的代码，必要的注释见代码，这个不能调试出来，有些步骤省略了。
//装配线问题 #include <iostream> using namespace std; int print_station (int m,int n) { if (n>=1) { print_station(l[m][n],n-1); } cout <<"string；"<<l[m][n]<<"station:"<<n<<endl; } //已经利用了递归实现了逆序； int main () { int a,b，i,j; int f[a+1][b+1]//i表示装配线，j表示不同的装配站； int t[100][100],a[100][100],l[100][100]; //t表示每一个装配站发生装配线转移时的时间消耗； //a表示在每一个装配站花费的时间； //l表示本次最优装配站前面的最有装配站所在装配线。。。有点绕，仔细 感受一下。 //l是用来寻找最优的装配线安排，有索引的作用； //具体的输入输出先不写了。。。先去吃饭。。 int x1=3,x2=2;//表示离开装配线时的消耗时间； cout <<"请输入b的数值"<<endl; cin>>b; cout <<"请输入两条装配线上装配站的数目："<<endl; for (int i=i;i<=2;i++) { for (j=1,j<=b;j++) { cin>>f[i][j]; } } for (j=2;j<=b;j++) { if((f[1][j-1]+a[1][j])<(f[2][j-1]+t[2][j-1]+a[1][j])) f[1][j]=f[1][j-1]+a[1][j]; l[1][j]=1; else f[1][j]=f[2][j-1]+t[2][j-1]+a[1][j]; l[1][j]=2; if (f[2][j-1]+a[2][j])<(f[1][j-1]+t[1][j-1]+a[2][j])) f[2][j]=f[2][j-1]+a[2][j]; l[2][j]=1; else f[2][j]=f[1][j-1]+t[1][j-1]+a[2][j]; l[2][j]=2; } //现在关系表已经构造完成； if ((f[1][b]+x1)<(f[2][b]+x2))//说明在第一个装配线上消耗的时间最短，就按照这个计算； int fm=f[1][b]+x1; int lm=1; else int fm=f[2][b]+x2;//这个表示最短的消耗时间； int lm=2;//这个有索引的作用，可以帮助找到整条路径； //接下来应该研究输出的问题； print_station(lm,b);//函数在最上方。。。 }