算法导论 15.1动态规划装配线调度

本文主要是介绍算法导论 15.1动态规划装配线调度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码根据15.1中伪代码编写

#include<stdio.h>int e[3]={-1,2,4};
int x[3]={-1,3,2};
int n = 6;
//a1[j]表示a(1,j)，a2[j]表示a(2,j)，以此类推，a1[0]不使用，设为-1 
int a1[7]={-1,7,9,3,4,8,4};
int a2[7]={-1,8,5,6,4,5,7};
int t1[6]={-1,2,3,1,3,4};
int t2[6]={-1,2,1,2,2,1};
int f1[7]={-1,0,0,0,0,0,0};
int f2[7]={-1,0,0,0,0,0,0};
//l1[0]和l1[1]不使用，设为-1；l2同理 
int l1[7]={-1,-1,0,0,0,0,0};
int l2[7]={-1,-1,0,0,0,0,0};
int f_final = 0;//f* 
int l_final = 0;//l* void fastest_way(int *e, int *x, int *a1, int *a2, int *t1, int *t2,int *f1, int *f2, int *l1, int *l2)
{int j; f1[1] = e[1]+a1[1];f2[1] = e[2]+a2[1];for (j = 2; j <= n; j++) {//根据公式15。4计算f1[j]的最小值int way1 = f1[j-1]+a1[j];int way2 = f2[j-1]+t2[j-1]+a1[j];if(way1 <= way2)//若way1较小，赋给f1[j]；并把l[j]设为1，表示走装配线1 {f1[j] = way1;l1[j] = 1;}else//否则选择way2，即走装配线2 {f1[j] = f2[j-1] + t2[j-1] + a1[j];l1[j] = 2;}//根据公式15。5计算f1[j]的最小值way2 = f2[j-1]+a2[j];way1 = f1[j-1]+t1[j-1]+a2[j];if(way2 <= way1){f2[j] = way2;l2[j] = 2;}else{f2[j] = way1;l2[j] = 1;}} //求f*，l* int final1 = f1[6] + x[1];int final2 = f2[6] + x[2];if(final1 <= final2){f_final = final1;l_final = 1;}else{f_final = final2;l_final = 2;} 
}void print_stations(int *l1, int *l2, int l_f, int n)
{int i = l_f;int j;printf("line %d, station %d\n", i, n);for(j = n; j >= 2; j--){if(i == 1){i = l1[j];printf("line %d, station %d\n", i, j-1);}else if(i == 2){i = l2[j];printf("line %d, station %d\n", i, j-1);}} 
}int main()
{int i;fastest_way(e, x, a1, a2, t1, t2, f1, f2, l1, l2);print_stations(l1, l2, l_final, n);
}

输出:
这里写图片描述
可以看到是按站点从大到小输出的.原因是l1,l2记录的路径信息是从后往前计算的.

那么问题来了:
Exercise 15.1-1:修改原来的输出函数print_stations,以站号递增顺序输出.
提示:利用递归.
改写的递归函数如下:

//原理：路径是从后往前计算的，因此可以将l1[n]或l2[n]传给下一层n-1的调用 
void recursive_print(int route, int n)//route为上一层传入的路径信息,指示走哪条.顶层route=l*(此处为l_final) 
{if(n == 1)//递归终止条件 printf("line %d, station 1\n", route);//线路为上一层传入的route，站点必然为1 else {//根据route=1 or 2,查表l1[n]或l2[n] if(route == 1){recursive_print(l1[n], n-1);//递归调用,将本层的l1[n]信息传入下一层递归,且规模-1 printf("line %d, station %d\n", route, n);//输出本层信息      }else if(route == 2){recursive_print(l2[n], n-1);printf("line %d, station %d\n", route, n);      }} 
}