資源描述：
《動(dòng)態(tài)規(guī)劃matlab例程.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、待求問題：651713567123495在上面的數(shù)字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經(jīng)過的數(shù)字之和最大。路徑上的每一步都只能往左下或右下走。求解思路：利用二維數(shù)組D來存放數(shù)字三角形，用D(r,j)來表示第r行第j個(gè)數(shù)字(r,j從1開始算)，maxsum(r,j)表示從D(r,j)到底邊的各條路徑中最佳路徑的數(shù)字之和，rout用于存放最佳路徑，rout的元素個(gè)數(shù)與數(shù)字三角形行數(shù)相同，第i個(gè)元素的值m代表最佳路徑經(jīng)過數(shù)字三角形第i行的第n個(gè)數(shù)字。由此可以將原問題轉(zhuǎ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
