實驗二動態(tài)規(guī)劃

1、實驗二：動態(tài)規(guī)劃實驗二：動態(tài)規(guī)劃實驗?zāi)康模豪斫鈩討B(tài)規(guī)劃的基本思想，理解動態(tài)規(guī)劃算法的兩個基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)。熟練掌握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析問題的一般方法，對較簡單的問題能正確分析，設(shè)計出動態(tài)規(guī)劃算法，并能快速編程實現(xiàn)。實驗內(nèi)容：編程實現(xiàn)講過的例題：最長公共子序列問題、投資問題等。1最長公共子序列一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=，則另一序列Z=是X的

2、子序列是指存在一個嚴(yán)格遞增的下標(biāo)序列，使得對于所有j=12…k有解答如下：a)最長公共子序列的結(jié)構(gòu)若用窮舉搜索法，耗時太長，算法需要指數(shù)時間。易證最長公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=和Y=的一個最長公共子序列Z=，則：i.若xm=yn，則zk=xm=yn且Zk1是Xm1和Yn1的最長公共子序列；ii.若xm≠yn且zk≠xm，則Z是Xm1和Y的最長公共子序列；iii.若xm≠yn且zk≠yn，則Z是X和Yn1的最長公共子序列。

3、其中Xm1=，Yn1=，Zk1=。最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。注意：需要輸出最長公共子序列A:備忘錄方法B動態(tài)規(guī)劃算法程序如下：#include#includeintlcs_length(x[]y[])intmain()x[100]y[100]intlenwhile(1)A:遞歸方法（自頂向下）備忘錄#includeusingnamespacestdintValue[3][5]=475159717649526171784670

4、768888intMaxValue(intStageintMoney)intsplitmoney=0inttempmax=0inttemp=0if(Stage==1)邊界條件returnValue[0][Money]f(splitmoney=0splitmoney=Moneysplitmoney)temp=MaxValue(Stage1splitmoney)Value[Stage][splitmoney]if(tempmaxtemp)t