23-算法设计

4.5.2　算法设计

采用自底向上的方法求最优值，分为不同规模的子问题，对于每一个小的子问题都求最优值，记录最优策略，具体策略如下。

（1）确定合适的数据结构

采用二维数组r[][]输入数据，二维数组m[][]存放各个子问题的最优值，二维数组s[][]存放各个子问题的最优决策（停靠站点）。

（2）初始化

根据递推公式，可以把m[i][j]初始化为r[i][j]，然后再找有没有比m[i][j]小的值，如果有，则记录该最优值和最优解即可。初始化为：m[i][j]=r[i][j]，s[i][j]=0，其中，i=1，2，…，n，j=i+1，i+2，…，n。

（3）循环阶段

• 按照递归关系式计算3个站点i，i+1，j（j=i+2）的最优值，并将其存入m[i][j]，同时将最优策略记入s[i][j]，i=1，2，…，n−2。
• 按照递归关系式计算4个站点i，i+1，i+2，j（j=i+3）的最优值，并将其存入m[i][j]，同时将最优策略记入s[i][j]，i=1，2，…，n−3。
• 以此类推，直到求出n个站点的最优值m[1][n]。

（4）构造最优解

根据最优决策信息数组s[][]递归构造最优解。s[1][n]是第1个站点到第n个站点（1，2，…，n）的最优解的停靠站点，即停靠了第s[1][n]个站点，我们在递归构造两个子问题（1，2，…，k）和（k，k +1，…，n）的最优解停靠站点，一直递归到子问题只包含一个站点为止。