實(shí)驗(yàn)二動(dòng)態(tài)規(guī)劃

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

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

3、其中Xm1=，Yn1=，Zk1=。最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。注意：需要輸出最長(zhǎng)公共子序列A:備忘錄方法B動(dòng)態(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