动态规划matlab例程.doc

《动态规划matlab例程.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、待求问题：651713567123495在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。求解思路：利用二维数组D来存放数字三角形，用D(r,j)来表示第r行第j个数字(r,j从1开始算)，maxsum(r,j)表示从D(r,j)到底边的各条路径中最佳路径的数字之和，rout用于存放最佳路径，rout的元素个数与数字三角形行数相同，第i个元素的值m代表最佳路径经过数字三角形第i行的第n个数字。由此可以将原问题转化为求maxsum(1,1)。Matlab程序代码：//main.mclearall;globalD;globalr

2、out;D=[60000;51000;71300;56710;23495];m=maxsum(1,1)rout//maxsum.mfunction[MaxSum]=maxsum(m,n)globalD;globalrout;maxsum=zeros(5);fori=5:-1:1ifi==5forj=1:5maxsum(i,j)=D(i,j);rout(i,j)=j;endelseforj=1:imaxsum(i,j)=max(maxsum(i+1,j),maxsum(i+1,j+1))+D(i,j);ifmax(maxsum(i+1,j),maxsum(i+1,j+1))==maxsum(

3、i+1,j)rout(i,j)=j;elserout(i,j)=j+1;endendendendMaxSum=maxsum(m,n);end