實(shí)驗(yàn)報(bào)告2. 動(dòng)態(tài)規(guī)劃

1、WUHANTEXTILEUNIVERSITY算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱動(dòng)態(tài)規(guī)劃學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院班級(jí)信科00000學(xué)號(hào)6666666666姓名0000002016年學(xué)號(hào)姓名實(shí)驗(yàn)日期實(shí)驗(yàn)名稱動(dòng)態(tài)規(guī)劃【實(shí)驗(yàn)?zāi)康摹坷斫鈩?dòng)態(tài)規(guī)劃算法的思想，能靈活利用動(dòng)態(tài)規(guī)劃算法解決實(shí)際計(jì)算問(wèn)題?！緦?shí)驗(yàn)內(nèi)容】參考源碼MatrixChain.cpp,RecurveMatrixChain.cpp,lookupMatrixChain.cpp1閱讀參考代碼，理解動(dòng)態(tài)規(guī)劃算法的主要數(shù)據(jù)結(jié)構(gòu)；2比較動(dòng)態(tài)規(guī)劃算法和分治算法的異同；3比較規(guī)劃算法和備注算法的異同；4針對(duì)4.6,4.7兩節(jié)問(wèn)題，在已有動(dòng)態(tài)規(guī)劃算法基礎(chǔ)上，編程求解最

2、優(yōu)解；【實(shí)驗(yàn)原理】（含相關(guān)算法流程圖，可寫多頁(yè)）【實(shí)驗(yàn)環(huán)境】微型計(jì)算機(jī)；Windows7操作系統(tǒng)；Codeblocks、vs2012集成開(kāi)發(fā)環(huán)境?！緦?shí)驗(yàn)過(guò)程與結(jié)果】(附主要源碼及運(yùn)行結(jié)果截圖)最長(zhǎng)單調(diào)子序列問(wèn)題#include#defineMAXLENGTH1000usingnamespacestd;intLongestIncreasingSubsequence(intX,intn,intc,intline)intpathMAXLENGTH;for(inti=0;in;+i)pathi=i;c0=1;輸入數(shù)組for(inti=1;in;+i)ci=1;for(intj=0;j=Xj&cj+1c

3、i)ci=cj+1;pathi=j;intmax=0;intend=-1;得到最大和獲得最長(zhǎng)遞增子序列的最后一個(gè)元素的索引intcMAXLENGTH;intlineMAXLENGTH;while(cinn,n!=0)for(inti=0;iXi;intmax=LongestIncreasingSubsequence(X,n,c,line);coutLongestIncreasingSubsequencesLength:max=0;-i)coutlinei;coutendl;intresn+ln+l;memset(arr,-1,sizeof(int);memset(res,-1,sizeof(i

4、nt);for(inti=1;i=n;i+)for(intj=1;jarrij;/初始化res結(jié)果數(shù)組for(inti=1;i=1;i-)for(intj=1;j=i;j+)/動(dòng)規(guī)填表resij=max(resi+1j,resi+1j+1)+arrij;嚴(yán)/打印res數(shù)組for(inti=1;i=n;i+)for(intj=1;j=i;j+)coutresij;coutendl;coutendl;*/coutresllendl;/最大路徑和值/找出靠右路徑inty=1;coutarr1y;頂部最大for(inti=2;i=n;i+)/從上往下找，只需要比較y和y+1,相應(yīng)輸出“最大值下標(biāo)對(duì)應(yīng)的

5、”原值if(resiy=resiy+l)coutarriy+1:y=y+l;更新yelse廠噸;coutendl;return0;DiWpiirQliMMglNiPebiWvHE645方箱essreti.imMlQ(QiO)exiBBJLtinntijw:89.457ste-F?snvkeyto-critLrv.H-懊洎新音輸人古i:2I41&-4S-fik.中藥訶述【實(shí)驗(yàn)小結(jié)】分治法與動(dòng)態(tài)規(guī)劃主要共同點(diǎn)：一者都要求原問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，都是將原問(wèn)題分而治之,分解成若干個(gè)規(guī)模較?。ㄐ〉胶苋菀捉鉀Q的程序）的子問(wèn)題然后將子問(wèn)題的解合并，形成原問(wèn)題的解.分治法與動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)方法：分治法通常利用遞歸求解.動(dòng)態(tài)規(guī)劃通常利用迭代法自底向上求解,但也能用具有記憶功能的遞歸法自頂向下求解.分治法與動(dòng)態(tài)規(guī)劃主要區(qū)別：分治法將分解后的子問(wèn)題看成相互獨(dú)立的.動(dòng)態(tài)規(guī)劃將分解后的子問(wèn)題理解為相互間有聯(lián)系，有重疊部分.2.相同點(diǎn)解決的問(wèn)題都需要最優(yōu)子結(jié)構(gòu)備忘錄方法與動(dòng)態(tài)規(guī)劃和遞歸的區(qū)別：1、動(dòng)態(tài)規(guī)劃是自低向上，備忘錄方法是自頂向下，遞歸是