数塔问题 动态规划.doc

实验二 动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 2．算法描述： Stept1：存储信息，将数塔数据存放到二维数组data[][]中。 Stept2：阶段划分，对于数塔问题应该从上而下逐层决策。首先对第四层的每个数据都进行考虑，选出最优解，然后逐层向上决策，这样逐层递推求出最后结果。 Stept3：最优解和路径的存储，用maxvalue[][]存储各个路径的最优值，用path[][]存储路径。Maxvalue[i][j]初始化为data[i][j]，Path[i][j]初始化0，Path[i][j]=0为向左，等于1为向右。 Stept4：信息的输出，路径最优质为maxvalue[1][1]，路径输出为： j=1;for(i=1;i=n-1;i++) { coutdata[i][j]--; j=j+path[i][j]; } 3．测试数据 9 15 10 6 8 2 18 9 5 19 7 10 4 16 4实验结果如图： 5关键代码： #define NUM_MAX 50 void main() { int data[NUM_MAX][NUM_MAX];//数据 int maxvalue[NUM_MAX][NUM_MAX];//最大值 int path[NUM_MAX][NUM_MAX];;//路径 int i,j,n; coutplease input the number of rows:; cinn; coutplease input the date of several tower:endl; for(i=1;i=n;i++) { for(j=1;j=i;j++) { cindata[i][j]; maxvalue[i][j]=data[i][j]; path[i][j]=0; } } for(i=n-1;i=1;i--) { for(j=1;j=i;j++) { if(maxvalue[i+1][j]maxvalue[i+1][j+1]) { maxvalue[i][j]=maxvalue[i][j]+maxvalue[i+1][j]; path[i][j]=0; } else { maxvalue[i][j]=maxvalue[i][j]+maxvalue[i+1][j+1]; path[i][j]=1; } } } coutmaxvalue=maxvalue[1][1]endl; j=1; coutpath:; for(i=1;i=n-1;i++) { coutdata[i][j]--; j=j+path[i][j]; } coutdata[n][j]endl; }