動(dòng)態(tài)程序設(shè)計(jì)專題

1、動(dòng)態(tài)程序設(shè)計(jì)是一種重要的算法動(dòng)態(tài)程序設(shè)計(jì)是一種重要的算法設(shè)計(jì)技術(shù)。使用這種技術(shù)設(shè)計(jì)算法，設(shè)計(jì)技術(shù)。使用這種技術(shù)設(shè)計(jì)算法，能夠高效地解決一類最優(yōu)化問題。通能夠高效地解決一類最優(yōu)化問題。通常情況下，使用通常的遞歸策略求解常情況下，使用通常的遞歸策略求解這類最優(yōu)化問題的時(shí)間復(fù)雜度是指數(shù)這類最優(yōu)化問題的時(shí)間復(fù)雜度是指數(shù)級(jí)的，而使用動(dòng)態(tài)程序設(shè)計(jì)方法解決級(jí)的，而使用動(dòng)態(tài)程序設(shè)計(jì)方法解決它們的復(fù)雜度往往是多項(xiàng)式級(jí)的。那它們的復(fù)雜度往往是多項(xiàng)式級(jí)的。那么到底什么是動(dòng)態(tài)規(guī)劃，它能解決哪么到底什么是動(dòng)態(tài)規(guī)劃，它能解決哪類最優(yōu)化問題，它為什么有這么高的類最優(yōu)化問題，它為什么有這么高的效率，如何實(shí)現(xiàn)它呢？效率，如何實(shí)

2、現(xiàn)它呢？一、什么是動(dòng)態(tài)程序設(shè)計(jì)一、什么是動(dòng)態(tài)程序設(shè)計(jì)動(dòng)態(tài)程序設(shè)計(jì)方法是一個(gè)多階段最優(yōu)化決策的過程。在現(xiàn)實(shí)生活中有一類特殊的活動(dòng)，可將它的全過程分成若干個(gè)互相聯(lián)系的階段，在每一階段都需要根據(jù)當(dāng)前的狀態(tài)做出決策，當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線，目的是要使整個(gè)過程達(dá)到最佳的效果。這就是多階段最優(yōu)化決策過程。在多階段決策問題中，各個(gè)階段采取的決策，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動(dòng)態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)方法。二、簡單的動(dòng)態(tài)規(guī)劃二、簡單的動(dòng)態(tài)規(guī)劃例1、數(shù)字

3、三角形如圖所示的一個(gè)數(shù)字三角形。請(qǐng)編一個(gè)程序計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最大。每一步可沿左斜線向下或右斜線向下走。1三角形行數(shù)100，三角形中的數(shù)字為整數(shù)0，1，99。輸入數(shù)據(jù)：由INPUT.TXT文件中首先讀到的是三角形的行數(shù)。例子中INPUT.TXT表示如下：573 88 1 02 7 4 44 5 2 6 5輸出數(shù)據(jù)：把最大總和（整數(shù)）寫入OUTPUT.TXT文件。上例為：30分析 根據(jù)給定的輸入，我們考慮數(shù)據(jù)的存放采用二維數(shù)組，從中間的任意一點(diǎn)ai,j分析，到達(dá)該點(diǎn)的路徑最大值取決于ai-1,j-1和ai-1,j兩者的最大值，即 ai,j=ai,j+max(

4、ai-1,j-1,ai-1,j)，對(duì)于初始值（起點(diǎn)）a1,1已知，該題可解。對(duì)例改變走向例2、更改上題條件每一步可以向下或向右走，我們分析對(duì)于任意一點(diǎn)ai,j來說，到達(dá)該點(diǎn)的路徑最大值ai,j=ai,j+max(ai-,k)(1=k=j)。例3、導(dǎo)彈攔截某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈數(shù)量N(1N1000)和導(dǎo)彈依次飛來的高度hi(雷達(dá)給出的高度不大于300

5、00的正整數(shù))。計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次打印輸出被攔截導(dǎo)彈的高度。分析：對(duì)于序列中任意一枚導(dǎo)彈i，假設(shè)它是一個(gè)可行序列中的最后一枚導(dǎo)彈，那么這個(gè)可行序列是前面到i這些枚導(dǎo)彈中滿足高度小于這枚導(dǎo)彈的高度的最長序列。設(shè)ai為每個(gè)導(dǎo)彈的高度，fi為以ai高度為序列中最后一枚導(dǎo)彈的最長序列，則fi=max(fk+1)1=k=i-1,滿足akai例4：合唱隊(duì)形【問題描述】N位同學(xué)站成一排，音樂老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左到右依次編號(hào)為1, 2, , K，他們的身高分別為T1, T2, , TK，則他們的身高滿

6、足T1 T2 Ti+1 TK (1 = i = K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計(jì)算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。【輸入文件】輸入文件chorus.in的第一行是一個(gè)整數(shù)N（2 = N = 100），表示同學(xué)的總數(shù)。第一行有n個(gè)整數(shù)，用空格分隔，第i個(gè)整數(shù)Ti（130 = Ti = 230）是第i位同學(xué)的身高（厘米）?！据敵鑫募枯敵鑫募horus.out包括一行，這一行只包含一個(gè)整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186 186 150 200 160 130 197 220【樣例輸出】4【數(shù)據(jù)規(guī)模】對(duì)于50%的數(shù)據(jù)，保證有n = 20；對(duì)于全部

7、的數(shù)據(jù)，保證有n = 100。分析：對(duì)于每個(gè)人來說，假設(shè)他是隊(duì)伍中最高的，分析：對(duì)于每個(gè)人來說，假設(shè)他是隊(duì)伍中最高的，求出他前面的最長上升序列個(gè)數(shù)求出他前面的最長上升序列個(gè)數(shù)ai，求出他后面，求出他后面下降序列序列的最長個(gè)數(shù)下降序列序列的最長個(gè)數(shù)bi，從而求出他作為隊(duì)，從而求出他作為隊(duì)伍最高應(yīng)出隊(duì)人數(shù)伍最高應(yīng)出隊(duì)人數(shù)n-ai-bi+1，這樣找出，這樣找出n個(gè)人個(gè)人的最小值問題解決的最小值問題解決三、背包問題三、背包問題在動(dòng)態(tài)程序設(shè)計(jì)中，有一類問題看起來搜索策略可以完成，但分析數(shù)據(jù)規(guī)模，搜索難以承受。仔細(xì)分析對(duì)于每一個(gè)涉及到的個(gè)體，要么被取，要么不取，要么可以重復(fù)取多次，而對(duì)于達(dá)到的狀態(tài)，存在從

8、這些狀況中的最優(yōu)解。即屬于背包問題例、例1、有一個(gè)箱子容量為v(正整數(shù)，ov20000)，同時(shí)有n個(gè)物品(on30)，每個(gè)物品有一個(gè)體積 (正整數(shù))。要求從 n 個(gè)物品中，任取若千個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。 樣例輸入：24 一個(gè)整數(shù)，表示箱子容量6 一個(gè)整數(shù)，表示有n個(gè)物品8 接下來n行，分別表示這n個(gè)物品的各自體積。312797輸出： 0一個(gè)整數(shù)，表示箱子剩余空間。例2：改變上題條件，每個(gè)物品有足夠多（即可重復(fù)性背包問題）已知道空的豬豬背囊的重量空的豬豬背囊的重量E和裝滿金幣的背囊的重量裝滿金幣的背囊的重量F。還知道一共有一共有N種金幣種金幣，其中第第i種金幣的面值為種金幣的面值為

9、Pi，重量為，重量為Wi。知道了這些數(shù)據(jù)，請(qǐng)計(jì)算出豬豬背囊里的金幣至少是多少錢。輸入：輸入：輸入文件第一行為兩個(gè)正整數(shù)E,F(1=E=F=1000)，E為空的豬豬背囊的重量，F(xiàn)為裝滿金幣的豬豬背囊的重量。第二行為一個(gè)正整數(shù)N(1=N=50)，表示金幣的種類。接下來的N行，每行包含兩個(gè)整數(shù)，第i+2行的兩個(gè)數(shù)Pi和Wi分別表示第i種金幣的面值和重量，1=Pi=60，1=Wi=100。輸出：輸出： 輸出文件僅一行，如果所要求的最少錢數(shù)存在，則輸出一個(gè)整數(shù)，為錢數(shù)X。否則，輸出一行This is impossible. 。 樣例輸入：樣例輸入：pocket.in10 11021 130 50樣例輸出

10、：樣例輸出：pocket.out60 四、動(dòng)態(tài)規(guī)劃的深入探討例1、 問題問題C:K好數(shù)（好數(shù)（K-Good Number）問題描述：問題描述：如果一個(gè)自然數(shù)N的K進(jìn)制表示中任意的相鄰的兩位都不是相鄰的數(shù)字，那么我們就說這個(gè)數(shù)是K好數(shù)。求L位K進(jìn)制數(shù)中K好數(shù)的數(shù)目。例如K = 4，L = 2的時(shí)候，所有K好數(shù)為11、13、20、22、30、31、33 共7個(gè)。給定K、L，求L位K好數(shù)的數(shù)目。輸入格式：輸入格式：從文件讀入數(shù)據(jù)，第一行為K、，其中K=16，L=10。輸出格式：輸出格式：將結(jié)果輸出到 KGOOD.OUT 輸入：4 2輸出：7樣例解釋：11 13 20 22 30 31 33分析分析：設(shè)fx,d為x位最后一位為數(shù)字d的k好數(shù)的個(gè)數(shù)，轉(zhuǎn)移方程fx,d=sum(fx-1,j)(0=j=k-1且j與d不相鄰)例2、乘積最大設(shè)有一個(gè)長度N的數(shù)字串，要求選手使用K個(gè)乘號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲?。同時(shí)，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個(gè)例子：有一個(gè)數(shù)字串: 312，當(dāng)N=3，K=1時(shí)會(huì)有以下兩種分法：1）3*12=362