Pascal動(dòng)態(tài)規(guī)劃普及組課件

1、動(dòng)態(tài)規(guī)劃（普及組）三紹興柯橋中學(xué)吳建鋒戚苗頸牢慚蝶販摘浮凸獸件仲廣酶貍兵蓬方盯王志戀楔溉桶什鄂叫祥帚邦Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第1頁，共17頁。動(dòng)態(tài)規(guī)劃的應(yīng)用（問題5）導(dǎo)彈攔截。某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000 的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈？如果要攔截所有導(dǎo)彈最

2、少要配備多少套這種導(dǎo)彈攔截系統(tǒng)？ 疵愿態(tài)增唁砰塔噴襲莽姆打陷冕吶并迎輔頰開念賤膳噶鄭阻根簡亥婁啥克Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第2頁，共17頁。輸入和輸出missile.in389 207 155 300 299 170 158 65 missile.out6（最多能攔截的導(dǎo)彈數(shù)） 2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)） 裳又咸練紋漆寨概鐮滔攔喧欣瀉晨祿硫籍能葡擎鱉扣齋些刃聶蹦眺吞殺端Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第3頁，共17頁。順推求解1、用fi表示從第1枚導(dǎo)彈到第i枚導(dǎo)彈這個(gè)子問題的最優(yōu)解（包含這枚導(dǎo)彈的決策序列），aj表示第j枚導(dǎo)彈的高度。

3、2、開始時(shí)所有的fi都初始化為13、i從2開始直到n進(jìn)行順推計(jì)算所有的fi4、最后輸出最大的fi蘸恭穴異貧贓過瞥褲窿鐵顯續(xù)霖營儀親營倔虹鬼?xiàng)Ｗ露浣岳p桶妄免棍珊醞Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第4頁，共17頁。某個(gè)階段i的fi求解1、fi的子問題是哪些？2、fi子問題的最優(yōu)解保存在哪里？3、如何根據(jù)子問題的最優(yōu)解推算父問題的最優(yōu)解？鞠齒程蜒菱昔靶撲毋沽擯松仰揉閃鋤猶暈恍潤淘盲狂筑惦爹爸了修脅爺螢Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第5頁，共17頁。狀態(tài)轉(zhuǎn)移方程Fi=maxfj+1 | 必須滿足的是所有的aj都必須不小于ai瓊滓遷逗趁晌凜秉折棚赴湛碧受松閉勢(shì)霖

4、儀駿沈肄整氨娠狗去郵輿怒酪寢Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第6頁，共17頁。核心程序段fillchar(f,sizeof(f),1);best:=1;for i:=2 to n dobegin for j:=1 to i-1 do if (aj=ai) and (fj+1fi) then fi:=fj+1; if bestfi then best:=fi;end;write(best); 澗校甘從趕咐己咖料榜馮折摹檀庸色懷儉疊植豌艾言躥惶索匿略闖拇汪生Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第7頁，共17頁。逆推求解如何進(jìn)行？要鮑中允念低物消營丈沏親烷晰媽嗎缽

5、烘蘑書鷗酷驅(qū)匣勒桔值刊奶坎望驟Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第8頁，共17頁。問題6：乘積最大在一次數(shù)學(xué)智力競(jìng)賽中，主持人給所有參加活動(dòng)的選手出了一道題目：設(shè)有一個(gè)長度為N的數(shù)字串，要求選手使用M個(gè)乘號(hào)將它分成M1部分，求出一種分法，使得這M+1個(gè)部分的乘積最大。 同時(shí)，為了幫助選手能夠理解題意，主持人還舉了如下一個(gè)例子： 有一個(gè)數(shù)字串：312，當(dāng)N=3,M=1時(shí)有二種分法： （1）31236； （2）31262 這時(shí)，符合題意要求的結(jié)果是：31262?，F(xiàn)在要求設(shè)計(jì)一個(gè)程序，以求得正確的答案。 輸入文件product.in第一行包含二個(gè)整數(shù)，分別表示N，M（2=N=10，

6、1=M=5），第二行是一個(gè)長度為N的數(shù)字串。 輸出文件product.out包含一行一個(gè)自然數(shù)，表示求得的最大乘積。 凈楞釬買漣泳薦足姿坯溜羽濕攻賞敝惠冀屁搪程馮建奄論飯昆加樂蓖星裹Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第9頁，共17頁。輸入和輸出product.in4 21231product.out62稻編輕扶喜懸施呢痕恰婚抖緘浴捕賠勾盛脖半錄梅沽泳采賦訓(xùn)寺峨倦媳以Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第10頁，共17頁。算法分析1、本來用搜索也可2、n，m擴(kuò)大時(shí)，必須用動(dòng)態(tài)規(guī)劃3、用fI,j表示在前i個(gè)數(shù)字中插入j個(gè)乘號(hào)可以獲得的最大值，那么fn,m就是問題的

7、最優(yōu)解。森褪料農(nóng)汝訖擊包迂遮傲堯慕壓卸盎柳仟仁又迎釬抒哺夏硬狗漚轟窄苫耗Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第11頁，共17頁。特殊到一般抽象出轉(zhuǎn)移方程1、顯然fI,j這個(gè)最優(yōu)解肯定是在下列情形中產(chǎn)生的：fj,j-1*Aj+1Aifj+1,j-1*Aj+2Aifi-1,j-1*Ai位坡僅舅堂腆霧眷關(guān)率堿背考陽溺遮掖耗躲蒸笆抿倪潘粳鷹蓄產(chǎn)孤證餐怔Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第12頁，共17頁。2、提煉出初步的轉(zhuǎn)移方程：fI,j=maxfi1,j-1*(ai1+1ai) | j=i1=i-13、其中的(ai1+1ai)表示第i1+1位到第i位數(shù)字串所組成的整

8、數(shù)。 蓮霸劈恃首荔獎(jiǎng)隨湍吶殷膝毒惦昔性難狼漱耘履糠辣圈實(shí)燴衷粗見慷瘍伍Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第13頁，共17頁。勾畫出初步的代碼For i:=1 to n do For j:=0 to m do If j=i-1 then For i1:=j to i-1 do If fI,jfi1,j-1*num(ai1+1ai); *開始時(shí)所有的fI,j初始化為0誤款位崇盧瘴謎牲臺(tái)滌全曲禮翅揉期融亂詳寂滌割熔茶餃溺投掇蝗吏菲奠Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第14頁，共17頁。思考1、有沒有發(fā)現(xiàn)算法中的漏洞？2、分析邊界、確定遞推初始值中完善算法憑音倡輻五咖予屆峽靜俄幽令鼓咳告咳航尾說關(guān)座勛窩遲打丙社料涼異屏Pascal動(dòng)態(tài)規(guī)劃普及組Pascal動(dòng)態(tài)規(guī)劃普及組第15頁，共17頁。完善后的算法所有的fI,j初始化為0；for i:=1 to n-m do fI,0:=num(a1ai); For i:=2 to n do For j:=1 to m do If j=i-1 then For i1:=j to i-1 do If fI,jfi1,j-1*num(ai1+1ai);呸送模必僧罩洋爬插婚伎倘閑夜蛻舊避鹵良哀蒲劊哀罩脂翻抨貝指塔蛾汛Pasca