第4章動(dòng)態(tài)規(guī)劃

1、1 學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn): :理解動(dòng)態(tài)規(guī)劃算法的概念。理解動(dòng)態(tài)規(guī)劃算法的概念。掌握動(dòng)態(tài)規(guī)劃算法的基本要素掌握動(dòng)態(tài)規(guī)劃算法的基本要素（1 1）最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)子結(jié)構(gòu)性質(zhì)（2 2）重疊子問(wèn)題性質(zhì)）重疊子問(wèn)題性質(zhì)掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟。(1)(1)找出找出最優(yōu)解最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)(2)遞歸地定義最優(yōu)值。遞歸地定義最優(yōu)值。(3)(3)以以自底向上自底向上的方式計(jì)算出最優(yōu)值。的方式計(jì)算出最優(yōu)值。(4)(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。2n1951年美國(guó)數(shù)學(xué)家年美國(guó)數(shù)學(xué)家RBe

2、llman等人，根據(jù)一類多等人，根據(jù)一類多階段問(wèn)題的特點(diǎn)，把階段問(wèn)題的特點(diǎn)，把多階段決策問(wèn)題多階段決策問(wèn)題變換為一系變換為一系列互相聯(lián)系的列互相聯(lián)系的單階段問(wèn)題單階段問(wèn)題，然后逐個(gè)加以解決。，然后逐個(gè)加以解決。n同時(shí)，提出了解決這類問(wèn)題的同時(shí)，提出了解決這類問(wèn)題的“最優(yōu)化原最優(yōu)化原理理”(PrincipleofOptimality)。n“最優(yōu)化原理最優(yōu)化原理”用數(shù)學(xué)化的語(yǔ)言來(lái)描述：假設(shè)為用數(shù)學(xué)化的語(yǔ)言來(lái)描述：假設(shè)為了解決某一優(yōu)化問(wèn)題，需要依次作出了解決某一優(yōu)化問(wèn)題，需要依次作出n個(gè)決策個(gè)決策D1，D2，Dn，如若這個(gè)決策序列是最優(yōu)的，對(duì)于，如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)任何一個(gè)整數(shù)

3、k，1kn，不論前面，不論前面k個(gè)決策是個(gè)決策是怎樣的，以后的最優(yōu)決策怎樣的，以后的最優(yōu)決策只取決于由前面決策所只取決于由前面決策所確定的當(dāng)前狀態(tài)確定的當(dāng)前狀態(tài)，即以后的決策，即以后的決策Dk+1，Dk+2，Dn也是最優(yōu)的。也是最優(yōu)的。3n最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。任何一個(gè)問(wèn)題，最優(yōu)化原理是動(dòng)態(tài)規(guī)劃的基礎(chǔ)。任何一個(gè)問(wèn)題，如果失去了這個(gè)最優(yōu)化原理的支持，就不可能用如果失去了這個(gè)最優(yōu)化原理的支持，就不可能用動(dòng)態(tài)規(guī)劃方法計(jì)算。能采用動(dòng)態(tài)規(guī)劃求解的問(wèn)題動(dòng)態(tài)規(guī)劃方法計(jì)算。能采用動(dòng)態(tài)規(guī)劃求解的問(wèn)題都需要滿足一定的條件：都需要滿足一定的條件：(1)問(wèn)題中的狀態(tài)必須滿足最優(yōu)化原理；問(wèn)題中的狀態(tài)必須滿足最優(yōu)化

4、原理；(2)問(wèn)題中的狀態(tài)必須滿足無(wú)后效性。問(wèn)題中的狀態(tài)必須滿足無(wú)后效性。n所謂的無(wú)后效性是指：所謂的無(wú)后效性是指：“下一時(shí)刻的狀態(tài)只與當(dāng)下一時(shí)刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)前狀態(tài)有關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無(wú)關(guān)，而和當(dāng)前狀態(tài)之前的狀態(tài)無(wú)關(guān)，當(dāng)當(dāng)前的狀態(tài)是對(duì)以往決策的總結(jié)前的狀態(tài)是對(duì)以往決策的總結(jié)”。4n動(dòng)態(tài)規(guī)劃法的定義：在求解問(wèn)題中，對(duì)于每一動(dòng)態(tài)規(guī)劃法的定義：在求解問(wèn)題中，對(duì)于每一步?jīng)Q策步?jīng)Q策，列出各種可能的局部解，再依據(jù)某種，列出各種可能的局部解，再依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解判定條件，舍棄那些肯定不能得到最優(yōu)解的局的局部解，在每一步都經(jīng)過(guò)篩選，以每一步都是最部解，在每一步都經(jīng)過(guò)篩

5、選，以每一步都是最優(yōu)解來(lái)保證全局是最優(yōu)解。優(yōu)解來(lái)保證全局是最優(yōu)解。n動(dòng)態(tài)規(guī)劃通常應(yīng)用于最優(yōu)化問(wèn)題，即做出一組動(dòng)態(tài)規(guī)劃通常應(yīng)用于最優(yōu)化問(wèn)題，即做出一組選擇以達(dá)到一個(gè)最優(yōu)解。選擇以達(dá)到一個(gè)最優(yōu)解。關(guān)鍵關(guān)鍵是是存儲(chǔ)子問(wèn)題的存儲(chǔ)子問(wèn)題的每一個(gè)解每一個(gè)解，以備它重復(fù)出現(xiàn)。，以備它重復(fù)出現(xiàn)。5n動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。n但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法

6、求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。次。6動(dòng)態(tài)規(guī)劃設(shè)計(jì)一般要經(jīng)歷以下幾個(gè)步驟：動(dòng)態(tài)規(guī)劃設(shè)計(jì)一般要經(jīng)歷以下幾個(gè)步驟：1 1、劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若、劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。干個(gè)階段。2 2、確定狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處的各種客觀情、確定狀態(tài)：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處的各種客觀情況用不同的狀態(tài)表示出來(lái)。況用不同的狀態(tài)表示出來(lái)。3 3、確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有、確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)著天然

7、的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)，所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也導(dǎo)出本階段的狀態(tài)，所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可以寫(xiě)出。就可以寫(xiě)出。4 4、尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需、尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。要一個(gè)遞推的終止條件或邊界條件。5 5、程序設(shè)計(jì)實(shí)現(xiàn)：動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，、程序設(shè)計(jì)實(shí)現(xiàn)：動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。71 1、階段：把問(wèn)題分成幾個(gè)相互聯(lián)系的有順序的幾、階段：把問(wèn)題分成幾個(gè)相

8、互聯(lián)系的有順序的幾個(gè)個(gè)環(huán)節(jié)環(huán)節(jié)，這些環(huán)節(jié)即稱為階段。，這些環(huán)節(jié)即稱為階段。2 2、狀態(tài)：某一階段的出發(fā)、狀態(tài)：某一階段的出發(fā)位置位置稱為狀態(tài)。稱為狀態(tài)。3 3、決策：從某階段的一個(gè)狀態(tài)演變到下一個(gè)階段、決策：從某階段的一個(gè)狀態(tài)演變到下一個(gè)階段某狀態(tài)的某狀態(tài)的選擇選擇。4 4、狀態(tài)轉(zhuǎn)移方程：前一階段的終點(diǎn)就是后一階段、狀態(tài)轉(zhuǎn)移方程：前一階段的終點(diǎn)就是后一階段的起點(diǎn)，前一階段的決策選擇導(dǎo)出了后一階段的狀的起點(diǎn)，前一階段的決策選擇導(dǎo)出了后一階段的狀態(tài)，這種關(guān)系描述了由態(tài)，這種關(guān)系描述了由k k階段到階段到k+1k+1階段狀態(tài)的演變階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。8n動(dòng)態(tài)

9、規(guī)劃與一般搜索技術(shù)最大不同的地方就是動(dòng)態(tài)規(guī)劃與一般搜索技術(shù)最大不同的地方就是記錄了已求解過(guò)的問(wèn)題的結(jié)果。記錄了已求解過(guò)的問(wèn)題的結(jié)果。n子問(wèn)題的記錄：子問(wèn)題的記錄：q最重要、最為復(fù)雜最重要、最為復(fù)雜q狀態(tài)表示狀態(tài)表示q用一個(gè)數(shù)、一組數(shù)或一個(gè)向量來(lái)實(shí)現(xiàn)狀態(tài)表示用一個(gè)數(shù)、一組數(shù)或一個(gè)向量來(lái)實(shí)現(xiàn)狀態(tài)表示n子問(wèn)題結(jié)果的記錄子問(wèn)題結(jié)果的記錄9n問(wèn)題一：存在一個(gè)數(shù)字三角形，從頂?shù)降子卸鄺l路徑，：存在一個(gè)數(shù)字三角形，從頂?shù)降子卸鄺l路徑， 每每一步可沿一步可沿左斜線向下或垂直向下左斜線向下或垂直向下。路徑所經(jīng)過(guò)的數(shù)字之和稱為。路徑所經(jīng)過(guò)的數(shù)字之和稱為路徑得分，要求求出最小路徑得分。路徑得分，要求求出最小路徑得分

10、。n狀態(tài)表示1-1 用一元組D（X）描述問(wèn)題，D（X）表示從頂?shù)竭_(dá)第X層的得分。但是一元組D（X）描述的子問(wèn)題不能滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，因?yàn)镈（X）的最優(yōu)解可能不包含子問(wèn)題D（X-I）的最優(yōu)解。這樣，動(dòng)態(tài)規(guī)劃方法是無(wú)法在狀態(tài)表示1-1上應(yīng)用。 n狀態(tài)表示 1-2 用二元組D（X，Y）描述問(wèn)題，D（X，Y）表示到達(dá)第X層第Y個(gè)位置時(shí)的得分，那么 D（X，Y）的最優(yōu)解包含了子問(wèn)題D（X-1，Y）或D（X-1，Y-1）的最優(yōu)解，狀態(tài)轉(zhuǎn)移方程為 D（X，Y）= Min D（X+1，Y），D（X+1，Y-1） + AX，Y D（4，1）= A4,1最小路徑得分=6動(dòng)態(tài)規(guī)劃對(duì)狀態(tài)表示的要求動(dòng)態(tài)規(guī)劃對(duì)狀態(tài)表示

11、的要求 10D(i,j)12345671672566836345534381238111聲明部分；聲明部分；輸入輸入a數(shù)組數(shù)組,M行行N列；列；/下標(biāo)從下標(biāo)從1開(kāi)始開(kāi)始for(j=1;j=1;i-)/自底向上自底向上DPfor(j=M-i+1,n=1;n=2*i;j+,n+)Dij=min(Di+1j,Di+1,j-1)+aij;coutB2一一C4D3E。最短路程長(zhǎng)度為最短路程長(zhǎng)度為13。15每個(gè)階段中，都求出本階段的各個(gè)初始狀態(tài)到每個(gè)階段中，都求出本階段的各個(gè)初始狀態(tài)到過(guò)程終點(diǎn)過(guò)程終點(diǎn)E的最短路徑和最短距離，當(dāng)?shù)淖疃搪窂胶妥疃叹嚯x，當(dāng)逆序倒逆序倒推推到過(guò)程起點(diǎn)到過(guò)程起點(diǎn)A時(shí)，便得到了全過(guò)程

12、的最短路時(shí)，便得到了全過(guò)程的最短路徑及最短距離，同時(shí)附帶得到了一組最優(yōu)結(jié)果徑及最短距離，同時(shí)附帶得到了一組最優(yōu)結(jié)果(即各階段的各狀態(tài)到終點(diǎn)即各階段的各狀態(tài)到終點(diǎn)E的最優(yōu)結(jié)果的最優(yōu)結(jié)果)。16思考與練習(xí)：若城市路徑示意圖如圖所示，圖若城市路徑示意圖如圖所示，圖中，每條邊上的數(shù)字是這段道路的長(zhǎng)度。條件：中，每條邊上的數(shù)字是這段道路的長(zhǎng)度。條件：從從A地出發(fā)，只允許向右或向上走。試尋找一條地出發(fā)，只允許向右或向上走。試尋找一條從從A地到地到B地的最短路徑和長(zhǎng)度。地的最短路徑和長(zhǎng)度。17n找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。n遞歸地定義最優(yōu)值遞歸地定義最優(yōu)值。n以以

13、自底向上自底向上的方式計(jì)算出最優(yōu)值。的方式計(jì)算出最優(yōu)值。n根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。在動(dòng)態(tài)規(guī)劃中，可將一個(gè)問(wèn)題的解決方案視為一系列決策的結(jié)果。不同的是，在貪婪算法中，每采用一次貪婪準(zhǔn)則便做出一個(gè)不可撤回的決策，而在動(dòng)態(tài)規(guī)劃中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)子序列。18動(dòng)態(tài)規(guī)劃設(shè)計(jì)的一般模式：動(dòng)態(tài)規(guī)劃設(shè)計(jì)的一般模式：fork:=階段最小值階段最小值to階段最大值階段最大值do/順推每一個(gè)階段順推每一個(gè)階段fori:=狀態(tài)最小值狀態(tài)最小值to狀態(tài)最大值狀態(tài)最大值do/枚舉階段枚舉階段k的每一個(gè)狀態(tài)的每一個(gè)狀態(tài)forj:=決策最小值決

14、策最小值to決策最大值決策最大值do/枚舉階段枚舉階段k中狀態(tài)中狀態(tài)i可選擇的每一種決策可選擇的每一種決策fik:=min（max）fik-1+aik-1，jk-1|ik-1通過(guò)決策通過(guò)決策jk-1可可達(dá)達(dá)ik19某個(gè)問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。這種性質(zhì)稱為最最優(yōu)子結(jié)構(gòu)性質(zhì)優(yōu)子結(jié)構(gòu)性質(zhì)。同一個(gè)問(wèn)題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問(wèn)題的維度低）例如圖中，若路線I和J是A到C的最優(yōu)路徑，則根據(jù)最優(yōu)化原理，路線J必是從B到C的最優(yōu)路線。這可用反證法證明：假設(shè)有另一路徑J是B到C的最優(yōu)路徑，則A到C的路線取I和J比I和J更優(yōu)，矛盾。從而證明J必是B到C

15、的最優(yōu)路徑。最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解最優(yōu)子結(jié)構(gòu)是問(wèn)題能用動(dòng)態(tài)規(guī)劃算法求解的前提。的前提。20遞歸算法求解問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問(wèn)題的重疊性質(zhì)子問(wèn)題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問(wèn)題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問(wèn)題時(shí)，只是簡(jiǎn)單地用常數(shù)時(shí)間查看一下結(jié)果。 通常不同的子問(wèn)題個(gè)數(shù)隨問(wèn)題的大小呈多項(xiàng)式增長(zhǎng)。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。 21備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個(gè)解過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，避免了相同子問(wèn)題的重

16、復(fù)求解。步驟： 為每個(gè)問(wèn)題建立一個(gè)記錄項(xiàng)，初值設(shè)為一個(gè)特殊值（表未求解） 每個(gè)待求解子問(wèn)題，首先查記錄項(xiàng)，有解答則直接選取，否則求解該子問(wèn)題。22LIS（Longest Increasing Subsequence）【問(wèn)題描述問(wèn)題描述】給出一個(gè)序列給出一個(gè)序列a1,a2,a3,a4,a5,a6,a7.an,求它的一個(gè)子序列求它的一個(gè)子序列（設(shè)為（設(shè)為s1,s2,.sn），使得這個(gè)子序列滿足這樣），使得這個(gè)子序列滿足這樣的性質(zhì)，的性質(zhì)，s1S2S3.n;for(i=1;iai;memset(b,0,sizeof(a);memset(c,0,sizeof(c);/求最長(zhǎng)上升子序列求最長(zhǎng)上升子序列O

17、(n2)b1=1;prei=0;/i=1-nfor(i=2;i=1;j-)if(ajmax)max=bj;prei=j;bi=max+1;26LISi1234567ai1735948bi1223434prei011343627/lab:max所對(duì)應(yīng)所對(duì)應(yīng)a數(shù)組元素下標(biāo)數(shù)組元素下標(biāo)O(n)max=b1;for(i=2;imax)max=bi;lab=i;printf(%dn,max);/輸出數(shù)列輸出數(shù)列O(n)i=lab;num=max;while(num0)printf(“%dt,ai);i=prei;num-;28LIS(完整算法)#include#include#defineMAXN200

18、main()intn,aMAXN,bMAXN,cMAXN,i,j,max,lab,preMAXN;scanf(%d,&n);for(i=1;i=n;i+)/O(n)scanf(%d,&ai);memset(b,0,sizeof(a);memset(c,0,sizeof(c);/求最長(zhǎng)上升子序列求最長(zhǎng)上升子序列O(n2)b1=1;pre1=0;for(i=2;i=1;j-)if(ajmax)max=bj;prei=j;bi=max+1;/lab:max所對(duì)應(yīng)所對(duì)應(yīng)a數(shù)組元素下標(biāo)數(shù)組元素下標(biāo)O(n)max=b1;for(i=2;imax)max=bi;lab=i;printf(%d

19、n,max);/輸出數(shù)列輸出數(shù)列O(n)i=lab;num=max;while(num0)printf(“%dt,ai);i=prei;num-;29【問(wèn)題描述問(wèn)題描述】N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，使得剩下的位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊(duì)位同學(xué)排成合唱隊(duì)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)形。合唱隊(duì)形是指這樣的一種隊(duì)形：設(shè)K位同學(xué)從左位同學(xué)從左到右依次編號(hào)為到右依次編號(hào)為1,2,K，他們的身高分別為，他們的身高分別為T1,T2,TK，則他們的身高滿足，則他們的身高滿足T1T2Ti+1TK(1=i=K)?！救蝿?wù)任務(wù)】已知所有

20、已知所有N位同學(xué)的身高，計(jì)算位同學(xué)的身高，計(jì)算最少需要幾位最少需要幾位同學(xué)出列同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊(duì)形。，可以使得剩下的同學(xué)排成合唱隊(duì)形?！緲永斎霕永斎搿?186186150200160130197220【樣例輸出樣例輸出】4【說(shuō)明說(shuō)明】該樣例中，可以要隊(duì)頭身高該樣例中，可以要隊(duì)頭身高186的兩個(gè)人出列的兩個(gè)人出列,以及隊(duì)尾以及隊(duì)尾197和和220的人出列的人出列,共共4人出列人出列,所以輸出所以輸出4.30【算法分析算法分析】：先分別從左到右求：先分別從左到右求最大上升子序列最大上升子序列，從右到左求從右到左求最大下降子序列最大下降子序列，再枚舉中間最高的一，再枚舉中間最

21、高的一個(gè)人。算法時(shí)間復(fù)雜度個(gè)人。算法時(shí)間復(fù)雜度O(N2)。【思路思路】：遞推關(guān)系式：遞推關(guān)系式bi=maxbj(1=jaj+1ci=maxcj(i=jaj+1合唱隊(duì)人數(shù)：合唱隊(duì)人數(shù)：maxbi+ci-1(ai被重復(fù)計(jì)算了一被重復(fù)計(jì)算了一次次)出列人數(shù)：出列人數(shù)：N-（maxbi+ci-1）31i12345678ai186186150200160130197220bi11122134ci33232111bi+ci44354245最長(zhǎng)隊(duì)列長(zhǎng)度-1#include#include#defineMAXN200main()intn,aMAXN,bMAXN,cMAXN,i,j,max;scanf(%d,&

22、amp;n);for(i=1;i=n;i+)O(n)scanf(%d,&ai);memset(b,0,sizeof(a);memset(c,0,sizeof(c);/求左側(cè)的最長(zhǎng)上升子序求左側(cè)的最長(zhǎng)上升子序列列O(n2)b1=1;for(i=2;i=1;j-)if(ajmax)max=bj;bi=max+1;/求右側(cè)的最長(zhǎng)上升子序列求右側(cè)的最長(zhǎng)上升子序列O(n2)cn=1;for(i=n-1;i0;i-) max=0;for(j=i+1;j=n;j+)if(ajmax)max=cj;ci=max+1;/求需要出列人數(shù)求需要出列人數(shù)O(n)max=b1+c1;for(i=2;imax)m

23、ax=bi+ci;printf(%dn,n-max+1);思考：如何判斷哪些人出隊(duì)列？35n題目：在一個(gè)長(zhǎng)度為題目：在一個(gè)長(zhǎng)度為N的數(shù)字串中插入的數(shù)字串中插入k-1個(gè)乘號(hào)，個(gè)乘號(hào)，將將N分成分成k部分部分，找出一種分法，使得這，找出一種分法，使得這k個(gè)部分個(gè)部分的乘積最大。的乘積最大。na1a2.ai.aj.ann例如有一個(gè)數(shù)字串例如有一個(gè)數(shù)字串: 312，當(dāng)，當(dāng)N=3，K=2時(shí)會(huì)有以時(shí)會(huì)有以下兩種分法：下兩種分法： 1）3*12=36 2）31*2=62這時(shí)，符合題目要求的結(jié)果是：這時(shí)，符合題目要求的結(jié)果是： 31*2=6236n若要求出分為若要求出分為k個(gè)部分的最大乘積，則只需個(gè)部分的最大

24、乘積，則只需窮舉窮舉分為分為k-1部分，乘號(hào)的插入位置部分，乘號(hào)的插入位置d。打擂臺(tái)選出。打擂臺(tái)選出d在各個(gè)位置時(shí)得到的最大乘積即為問(wèn)題的解。在各個(gè)位置時(shí)得到的最大乘積即為問(wèn)題的解。n依此類推，把依此類推，把k-1的問(wèn)題歸結(jié)為的問(wèn)題歸結(jié)為k-2的情況的情況n.求在任意一段中插入求在任意一段中插入0個(gè)乘號(hào)個(gè)乘號(hào)的最大乘積的最大乘積n.在任意一段中插入在任意一段中插入0個(gè)乘號(hào)時(shí)的最大乘積，而個(gè)乘號(hào)時(shí)的最大乘積，而此時(shí)的值即為該段的數(shù)值。此時(shí)的值即為該段的數(shù)值。1 2dd+1i11 W(d+1,i)aa .aa. aj 分為段,m(d,j-1)最后段37設(shè)設(shè)w(h1,h2):從第從第h1位到第位到第

25、h2位所組成的十進(jìn)制位所組成的十進(jìn)制數(shù)。數(shù)。h2h1才有意義才有意義W為為N行行N列右上三角矩陣列右上三角矩陣38設(shè)設(shè)m(i,j)表示：前表示：前i位位(從從1.i)分成分成j段所得的最段所得的最大乘積大乘積,則可得到如下的則可得到如下的DP方程：方程：if(j=1)m(i,1)=w(1,i);if(j=1&j=k)m(i,j)=maxm(d,j-1)*w(d+1,i)/1=di(即從即從1開(kāi)始直到開(kāi)始直到i-1中找最大值）中找最大值）elseif(ij)m(i,j)=0;394041問(wèn)題描述問(wèn)題描述給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問(wèn)應(yīng)如何選擇裝

26、入背包的物品，使得裝入背包中物品的總價(jià)值最大? 0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題。niiixv1maxnixCxwiniii1,1 , 01421、減小規(guī)模m(i，j)是背包容量為j，可選擇物品為i，i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。m(i+1，j)可選擇物品為i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。m(n，j)可選擇物品為n時(shí)0-1背包問(wèn)題的最優(yōu)值。規(guī)模已經(jīng)為1nnnwjwjvjnm00),(2、推導(dǎo)遞歸式，判斷第i件？1）不放，背包當(dāng)前產(chǎn)生價(jià)值仍為m(i+1，j)；2）放入，調(diào)整背包容量j-wi，背包當(dāng)前產(chǎn)生價(jià)值為m(i+1,j-wi)+Vi43m(i，j)是背包容量為j，可選擇物品為

27、i，i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值。由0-1背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式如下。iiiiwjwjjimvwjimjimjim0), 1(), 1(), 1(max),(nnnwjwjvjnm00),( voidKnapSack(intv,intw,intc,intn,intm11)int jMax=min(wn,c);for (j=0;jjMax;j+) /當(dāng) 0=jwn時(shí), m(n,j)=0 mnj=0;for (j=wn;j=wn時(shí), m(n,j)=vnmnj=vn;for (i=n-1;i=1;i-) /DP int jMax=min(wi,c); for

28、 (j=0;jjMax;j+) /m(i,j)=m(i+1,j) 當(dāng)0=jwi mij=mi+1j; for (j=wi;j=wn mij=max(mi+1j,mi+1j-wi+vi);cout2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。 m(i,j)值0 1 2 3 4 5 6 7 8 9 1012345N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,6m(i，j)是背包容量為j，可選擇物品為i，i+1，n時(shí)0-1背包問(wèn)題的最優(yōu)值47用倒推法來(lái)求出每種物品是否選中。選中用倒推法來(lái)求出每種物品是否選中。選中1，2，5三件物三件物品，最高價(jià)值品，最高價(jià)值15，總重，總重8。void tra

29、ceback(int m11,int w,int c,int n,int x)for(i=1;i0 ? 1:0);N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,648某工廠預(yù)計(jì)明年有某工廠預(yù)計(jì)明年有A,B,C,D四個(gè)新四個(gè)新建項(xiàng)目，每個(gè)項(xiàng)目的投資額建項(xiàng)目，每個(gè)項(xiàng)目的投資額 wk及其及其投資后的收益投資后的收益 vk如下表所示。投資如下表所示。投資總額為總額為30萬(wàn)元，問(wèn)如何選擇項(xiàng)目才萬(wàn)元，問(wèn)如何選擇項(xiàng)目才能使總收益最大。能使總收益最大。n上述問(wèn)題的靜態(tài)規(guī)劃模型如下：上述問(wèn)題的靜態(tài)規(guī)劃模型如下：項(xiàng)目項(xiàng)目wkvkA1512B108C129D85 項(xiàng)入選項(xiàng)入選項(xiàng)未入選項(xiàng)未入選1030

30、)(maxkkxxwxvxfkkkkkkk491、描述該問(wèn)題的最優(yōu)解、描述該問(wèn)題的最優(yōu)解若若x1x2.xn是使總收益最大的最優(yōu)解是使總收益最大的最優(yōu)解(xi0,1)，此時(shí)總投，此時(shí)總投資額為資額為C，投資項(xiàng)目的選擇范圍為，投資項(xiàng)目的選擇范圍為1n，我們將這個(gè)最優(yōu)解記為，我們將這個(gè)最優(yōu)解記為m1c;則則x2x3.xn也必定是在總投資額為也必定是在總投資額為c-w1x1(當(dāng)當(dāng)x1=0時(shí)為時(shí)為c，x1=1時(shí)為時(shí)為c-w1)，投資項(xiàng)目的選擇范圍為，投資項(xiàng)目的選擇范圍為2n時(shí)的子問(wèn)題的最優(yōu)解，時(shí)的子問(wèn)題的最優(yōu)解，我們將其記為我們將其記為m2c-w1x1;此時(shí)我們需要證明這一結(jié)論，用反證法即可。此時(shí)我們需

31、要證明這一結(jié)論，用反證法即可。證明：證明：假設(shè)假設(shè)x2x3.xn不是當(dāng)前狀態(tài)的最優(yōu)解，則必定存在一個(gè)解不是當(dāng)前狀態(tài)的最優(yōu)解，則必定存在一個(gè)解z2z3.zn為最優(yōu)解，這樣對(duì)于整個(gè)問(wèn)題的最優(yōu)解就應(yīng)該是為最優(yōu)解，這樣對(duì)于整個(gè)問(wèn)題的最優(yōu)解就應(yīng)該是x1z2z3.Zn。這顯然與這顯然與x1x2.xn為最優(yōu)解相矛盾，故假設(shè)不成立，為最優(yōu)解相矛盾，故假設(shè)不成立，得證。得證。2、遞歸定義最優(yōu)解、遞歸定義最優(yōu)解若我們把投資總額為若我們把投資總額為j，投資項(xiàng)目的選擇范圍為，投資項(xiàng)目的選擇范圍為in時(shí)的問(wèn)時(shí)的問(wèn)題的最優(yōu)解定義為題的最優(yōu)解定義為mij；顯然，按照第一步的模式，顯然，按照第一步的模式，m1c的子問(wèn)題的最優(yōu)

32、解為的子問(wèn)題的最優(yōu)解為m2c-w1x1，那么，那么mij的子問(wèn)題的最優(yōu)解就應(yīng)該為的子問(wèn)題的最優(yōu)解就應(yīng)該為mi+1j-wixi；于是我們可以把這個(gè)問(wèn)題遞歸定義為：于是我們可以把這個(gè)問(wèn)題遞歸定義為：mij=maxmi+1j,mi+1j-wi+vi（這兩項(xiàng)是由（這兩項(xiàng)是由xi的兩種的兩種取值不同而來(lái)的）取值不同而來(lái)的）再根據(jù)再根據(jù)j的取值范圍我們便可以得到這個(gè)問(wèn)題的遞歸式：的取值范圍我們便可以得到這個(gè)問(wèn)題的遞歸式：iiiiwjwjjimvwjimjimjim011,1maxnnnwjwjvjnm00邊界條件為：513、以自底向上的方式計(jì)算出最優(yōu)值、以自底向上的方式計(jì)算出最優(yōu)值void KnapSac

33、k(int v,int w,int c,int n,int m11)intjMax=min(wn-1,c);for(j=0;j=jMax;j+)mnj=0;for(j=wn;j1;i-)intjMax=min(wi-1,c);for(j=0;j=jMax;j+) mij=mi+1j;for(j=wi;j=w1)m1c=max(m1c,m2c-w1+v1);52【問(wèn)題描述】想以最美觀的方式布置花店的櫥窗。想以最美觀的方式布置花店的櫥窗。n有有F束花，每束花的品種都不一樣，同時(shí)束花，每束花的品種都不一樣，同時(shí)至少有同至少有同樣數(shù)量的花瓶樣數(shù)量的花瓶。n花瓶從左到右按花瓶從左到右按1到到V編號(hào)。編號(hào)

34、。n花束可以移動(dòng)，并且每束花用花束可以移動(dòng)，并且每束花用1到到F的整數(shù)唯一標(biāo)識(shí)，的整數(shù)唯一標(biāo)識(shí)，花束的整數(shù)決定了花束在花瓶中的排列的順序，如花束的整數(shù)決定了花束在花瓶中的排列的順序，如果果ij，則花束，則花束i必須放在花束必須放在花束j左邊的花瓶中。左邊的花瓶中。n如果花瓶的數(shù)目大于花束的數(shù)目，則多余的花瓶必如果花瓶的數(shù)目大于花束的數(shù)目，則多余的花瓶必須空，即須空，即每個(gè)花瓶只能放一束花每個(gè)花瓶只能放一束花。53當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)效果，并以美學(xué)值（一個(gè)整數(shù)）來(lái)表示，效果，并以美學(xué)值（一個(gè)整數(shù)）來(lái)表示，空花瓶的美空花瓶的美

35、學(xué)值為學(xué)值為0。假設(shè)有假設(shè)有3束花，束花，5個(gè)花瓶?；ㄆ颗c花束不同的搭配所具個(gè)花瓶。花瓶與花束不同的搭配所具有的美學(xué)值，可以用如下的表格表示：有的美學(xué)值，可以用如下的表格表示：pij：第：第i束花插入第束花插入第j個(gè)花瓶的好看程度個(gè)花瓶的好看程度pFV 花瓶花瓶 花束花束123451723-5-24162521-410233-215-4-202054qij表示表示1.i束鮮花插入束鮮花插入1.j個(gè)花瓶所能得到的最個(gè)花瓶所能得到的最大好看程度大好看程度n1.j束鮮花插入到前面的束鮮花插入到前面的1.j只花瓶中只花瓶中,所得到的好看所得到的好看程度是程度是qjj=p11+p22+.+pjj.n第第

36、i束鮮花若放入第束鮮花若放入第j號(hào)花瓶號(hào)花瓶,最大好看程度是最大好看程度是qi-1j-1+pij;n第第i束鮮花若放入前束鮮花若放入前j-1個(gè)花瓶中的某一個(gè)個(gè)花瓶中的某一個(gè),所得的好所得的好看程度是看程度是qij-1,n插入第插入第i束鮮花所能得到的最大好看程度束鮮花所能得到的最大好看程度為為:qij=MAX(qi-1j-1+pij,qij-1)55qij表示表示1.i束鮮花插入束鮮花插入1.j個(gè)花瓶所能得到的最個(gè)花瓶所能得到的最大好看程度大好看程度規(guī)劃方程為規(guī)劃方程為:qij=MAX(qi-1j-1+pij,qij-1)邊界條件為：邊界條件為：q00=0；q0j=0(1=j=v)56/沒(méi)有一

37、束花插入花瓶時(shí)沒(méi)有一束花插入花瓶時(shí),好看程度為好看程度為0q00=0;/v束鮮花分別插入束鮮花分別插入v個(gè)花瓶時(shí)最大好看程度個(gè)花瓶時(shí)最大好看程度f(wàn)or(j=1;j=V;j+)q0j=0;/設(shè)置第設(shè)置第j束鮮花放入第束鮮花放入第j號(hào)花瓶中的最大好看程度號(hào)花瓶中的最大好看程度qjj=qj-1j-1+pjj;i j012345000000010720028300024qij57for(j=1;j=V;j+)for(i=1;i0;i-)/i代表花束編號(hào)代表花束編號(hào)while(qi-1newv-1+pinewvqinewv)newv-;/確定鮮花確定鮮花i插在花瓶插在花瓶newv中中,并準(zhǔn)備考慮前一只花

38、瓶并準(zhǔn)備考慮前一只花瓶wayi=newv;newv-；i j012345000000010723232323200282833463000242453qijqFV59田忌賽馬田忌賽馬問(wèn)題描述問(wèn)題描述田忌與齊王賽馬，雙方各有田忌與齊王賽馬，雙方各有n匹馬參賽匹馬參賽（naici,10 ,b1aii1,n1, b1ai62田忌賽馬田忌賽馬a1.5 10090605045b1.5 9080756040ci,j123451-120314151c(i，j):齊王齊王的的i.j匹馬與匹馬與田忌的第田忌的第j匹匹馬比賽，田馬比賽，田忌所獲得的忌所獲得的最大收益最大收益63田忌賽馬田忌賽馬for(i=n-1;

39、i=1;i-)for(j=2;j=n-i+1;j+)if(ai+j-1bj)cij=ci+1j-1-1;if(ai+j-1=bj)cij=max(ci+1j-1-1,cij-1)；a1.510090605045b1.59080756040ci,j123451-1-101220123031230041200051000064田忌賽馬田忌賽馬a1.5 10090605045b1.5 9080756040ci,j123451-1-1012201230312300412000510000c(i，j):齊王齊王的從第的從第i匹馬匹馬開(kāi)始的開(kāi)始的j匹馬匹馬與田忌的最與田忌的最快的快的j匹馬比匹馬比賽，田忌

40、所賽，田忌所獲得的獲得的最大最大收益收益65練習(xí)66提示：for(r=n-2;r=0;r-)for(c=0;ctr+1c+1)trc+=tr+1c;elsetrc+=tr+1c+1;781074 43452 6 567問(wèn)題描述在一個(gè)在一個(gè)圓形圓形操場(chǎng)的四周擺放著操場(chǎng)的四周擺放著N堆石子堆石子(N=100),現(xiàn)要將石子有次序地合并成一堆現(xiàn)要將石子有次序地合并成一堆.規(guī)定每規(guī)定每次只能選取次只能選取相鄰相鄰的兩堆合并成新的一堆的兩堆合并成新的一堆,并將新的一并將新的一堆的石子數(shù)記為堆的石子數(shù)記為該次合并的得分該次合并的得分.編寫(xiě)一程序編寫(xiě)一程序,讀入讀入堆棧數(shù)堆棧數(shù)N及每堆棧的石子數(shù)及每堆棧的石子

41、數(shù)(=20).選擇一種合并石子的方案選擇一種合并石子的方案,做做N-1次合并次合并,使所有得分使所有得分的總和最?。ㄗ畲螅５目偤妥钚。ㄗ畲螅?23868方法一每次找相鄰最小的兩堆合并從最左上面的一堆開(kāi)始從最左上面的一堆開(kāi)始,沿順時(shí)針?lè)较蚺懦梢粋€(gè)序列沿順時(shí)針?lè)较蚺懦梢粋€(gè)序列.合并的過(guò)程如下合并的過(guò)程如下:每次合并得分每次合并得分:第一次合并第一次合并3465425第二次合并第二次合并546549第三次合并第三次合并96549第四次合并第四次合并96915第五次合并第五次合并15924總得分總得分=5+9+9+15+24=62例如有6堆石子,每堆石子數(shù)依次為3 4 6 5 4 2. 要求做5次

42、合并,得分的總和最小.貪心法：每一次選擇得分最小的相鄰兩堆合并,不一定保證余下的合并過(guò)程能導(dǎo)致最優(yōu)解. 69方法二：另外方法逐次合并合并的過(guò)程如下合并的過(guò)程如下:每次合并得分每次合并得分:第一次合并第一次合并3465427第二次合并第二次合并7654213第三次合并第三次合并135426第四次合并第四次合并135611第五次合并第五次合并131124總得分總得分=7+13+6+11+24=61例如有6堆石子,每堆石子數(shù)依次為3 4 6 5 4 2. 要求做5次合并,得分的總和最小.如果N-1次合并的全局最優(yōu)解包含了每一次合并的子問(wèn)題的最優(yōu)解,那么經(jīng)這樣的N-1次合并后的得分總和必然是最優(yōu)的.

43、70例如上例中第五次合并石子數(shù)分別為例如上例中第五次合并石子數(shù)分別為13和和11的相鄰兩堆的相鄰兩堆.這這兩堆石頭分別由最初的第兩堆石頭分別由最初的第1,2,3堆堆(石頭數(shù)分別為石頭數(shù)分別為3,4,6)和第和第4,5,6堆堆(石頭數(shù)分別為石頭數(shù)分別為5,4,2)經(jīng)經(jīng)4次合并后形成的次合并后形成的.于是問(wèn)題又歸結(jié)為如何使得這兩個(gè)子序列的于是問(wèn)題又歸結(jié)為如何使得這兩個(gè)子序列的N-2次合并的得次合并的得分總和最優(yōu)分總和最優(yōu).為了實(shí)現(xiàn)這一目標(biāo)為了實(shí)現(xiàn)這一目標(biāo),我們將第我們將第1個(gè)序列又一分為二個(gè)序列又一分為二:第第1、2堆構(gòu)成子序列堆構(gòu)成子序列1,第第3堆為子序列堆為子序列2.第一次合并子序列第一次合

44、并子序列1中的兩堆中的兩堆,得分得分7;第二次再將之與子序列第二次再將之與子序列2的一堆合并的一堆合并,得分得分13.顯然對(duì)于第顯然對(duì)于第1個(gè)子序列來(lái)說(shuō)個(gè)子序列來(lái)說(shuō),這樣的合并方案是最優(yōu)的這樣的合并方案是最優(yōu)的.同樣同樣,我們將第我們將第2個(gè)子序列也一分為二個(gè)子序列也一分為二:第第4堆為子序列堆為子序列1,第第5,6堆構(gòu)堆構(gòu)成子序列成子序列2.第三次合并子序列第三次合并子序列2中的中的2堆堆,得分得分6;第四次再將第四次再將之與子序列之與子序列1中的一堆合并中的一堆合并,得分得分13.顯然對(duì)于第二個(gè)子序列來(lái)顯然對(duì)于第二個(gè)子序列來(lái)說(shuō)說(shuō),這樣的合并方案也是最優(yōu)的這樣的合并方案也是最優(yōu)的.由此得出一

45、個(gè)結(jié)論由此得出一個(gè)結(jié)論:6堆石子堆石子經(jīng)過(guò)這樣的經(jīng)過(guò)這樣的5次合并后次合并后,得分的總和最小得分的總和最小.71動(dòng)態(tài)規(guī)劃思路：動(dòng)態(tài)規(guī)劃思路：階段i：石子的每一次合并過(guò)程，先兩兩合并，再三三合：石子的每一次合并過(guò)程，先兩兩合并，再三三合并，并，.最后最后N堆合并堆合并狀態(tài)s：每一階段中各個(gè)不同合并方法的石子合并總得分。：每一階段中各個(gè)不同合并方法的石子合并總得分。決策：把當(dāng)前階段的合并方法細(xì)分成前一階段已計(jì)算出的：把當(dāng)前階段的合并方法細(xì)分成前一階段已計(jì)算出的方法，選擇其中的最優(yōu)方案。方法，選擇其中的最優(yōu)方案。采用動(dòng)態(tài)規(guī)劃求解的關(guān)鍵是確定所有石子堆子序列的最佳合并方案。采用動(dòng)態(tài)規(guī)劃求解的關(guān)鍵是確定

46、所有石子堆子序列的最佳合并方案。這這些石子堆子序列包括：些石子堆子序列包括：第堆、第堆、第堆、第堆、第第堆、第堆、第堆、第堆、第N堆、第堆；堆、第堆；第堆、第堆、第堆、第堆、第堆、第堆、第堆、第堆、第堆、第堆、第堆、第堆、第第N堆、第堆、第堆；堆、第堆、第堆；第堆、第堆、第、第N堆第堆第2堆、堆、第、第N堆、第堆堆、第堆第第N堆、第堆、堆、第堆、第、第N堆堆72為了便于運(yùn)算，我們用為了便于運(yùn)算，我們用i，j表示一個(gè)從第表示一個(gè)從第i堆數(shù)起，堆數(shù)起，順時(shí)針數(shù)順時(shí)針數(shù)j堆時(shí)的子序列堆時(shí)的子序列第第i堆、第堆、第i堆、堆、第（、第（ij1）modn堆堆設(shè)設(shè)fi，j將子序列將子序列i，j中的中的j堆石

47、子合并成一堆的堆石子合并成一堆的最佳得分和；最佳得分和；ci，j將將i，j一分為二，其中子序列的堆數(shù)；一分為二，其中子序列的堆數(shù)；（iN，jN）顯然，對(duì)每一堆石子來(lái)說(shuō)，它的顯然，對(duì)每一堆石子來(lái)說(shuō)，它的fi，1因?yàn)橐婚_(kāi)始還沒(méi)有合并，所以這些值應(yīng)該因?yàn)橐婚_(kāi)始還沒(méi)有合并，所以這些值應(yīng)該全部為全部為0。ci，(1iN)73規(guī)劃的方向是順推規(guī)劃的方向是順推。先考慮含二堆石子的。先考慮含二堆石子的N個(gè)子序列（各子序列分別從個(gè)子序列（各子序列分別從第堆、第堆、第堆、第堆、第、第N堆數(shù)起，順時(shí)針數(shù)堆）的合并方案堆數(shù)起，順時(shí)針數(shù)堆）的合并方案f，f，fN，c，c，cN，然后考慮含三堆石子的個(gè)子序列（各子序列分別

48、從第堆、第然后考慮含三堆石子的個(gè)子序列（各子序列分別從第堆、第堆、堆、第堆數(shù)起，順時(shí)針數(shù)堆）的合并方案、第堆數(shù)起，順時(shí)針數(shù)堆）的合并方案f，f，fN，c，c，cN，依次類推，直至考慮了含依次類推，直至考慮了含N堆石子的堆石子的N個(gè)子序列（各子序列分別從第個(gè)子序列（各子序列分別從第堆、第堆、堆、第堆、第、第N堆數(shù)起，順時(shí)針數(shù)堆數(shù)起，順時(shí)針數(shù)N堆）的合并方案堆）的合并方案f，N，f，N，fN，Nc，N，c，N，cN，N最后，在子序列最后，在子序列，N，N，N，N中，選擇得中，選擇得分總和（分總和（f值）最?。ɑ蜃畲螅┑囊粋€(gè)子序列值）最小（或最大）的一個(gè)子序列i，N（iN），由此），由此出發(fā)出發(fā)倒推

49、合并過(guò)程倒推合并過(guò)程。74動(dòng)態(tài)規(guī)劃方程和倒推合并過(guò)程動(dòng)態(tài)規(guī)劃方程和倒推合并過(guò)程對(duì)子序列對(duì)子序列(i,j)最后一次合并最后一次合并,其得分為第其得分為第i堆數(shù)起堆數(shù)起,順時(shí)針數(shù)順時(shí)針數(shù)j堆堆的石子總數(shù)的石子總數(shù)t.被合并的兩堆石子是由子序列被合并的兩堆石子是由子序列(i,k)和和(i+k-1)modn+1,j-k)(1kj-1)經(jīng)有限次合并形成的經(jīng)有限次合并形成的.為了求出最佳合并方案中的為了求出最佳合并方案中的k值值,我們定義一個(gè)動(dòng)態(tài)規(guī)劃方程我們定義一個(gè)動(dòng)態(tài)規(guī)劃方程:當(dāng)求最大得分總和時(shí)當(dāng)求最大得分總和時(shí)f(i,j)=maxf(i,k)+f(x,j-k)+t1kj-1c(i,j)=kf(i,j)

50、=f(i,k)+f(x,j-k)+t2jn,1in當(dāng)求最小得分總和時(shí)當(dāng)求最小得分總和時(shí)f(i,j)=minf(i,k)+f(x,j-k)+t1kj-1c(i,j)=kf(i,j)=f(i,k)+f(x,j-k)+t2jn,1in其中其中x=(i+k-1)modn+1,即第即第i堆數(shù)起堆數(shù)起,順時(shí)針數(shù)順時(shí)針數(shù)k+1堆的堆序號(hào)堆的堆序號(hào).75 j i12345610720 36 51 612010 25 38 48 623011 24 34 45 6140917 28 41 6150614 26 43 6160514 29 45 62fi,jci,j j i12345610122332012222

51、3011122401112350112346012333f(i,j)=minf(i,k)+f(x,j-k)+t 1kj-1c(i,j)=k f(i,j)=f(i,k)+f(x,j-k)+t 2jn,1inx=(i+k-1)modn+17677上述倒推過(guò)程上述倒推過(guò)程,可由一個(gè)可由一個(gè)print(子序列子序列)的遞歸算法描述的遞歸算法描述:voidprint(i,j)if(j!=1)/*繼續(xù)倒推合并過(guò)程繼續(xù)倒推合并過(guò)程*/print(i,c(i,j);/*倒推子序列倒推子序列1的合并過(guò)程的合并過(guò)程*/print(i+c(i,j)-1)%(n+1),j-c(i,j);/*倒推子序列倒推子序列2的合

52、并過(guò)程的合并過(guò)程*/for(k=1;kN;k+)if(第第K堆石子未從圈內(nèi)去除堆石子未從圈內(nèi)去除)if(K=i|K=X)置第置第K堆石子待合并標(biāo)志堆石子待合并標(biāo)志;else第第K堆石子未被合并堆石子未被合并;第第i堆石子數(shù)堆石子數(shù)第第i堆石子數(shù)堆石子數(shù)+第第X堆石子數(shù)堆石子數(shù);將第將第X堆石子從圈內(nèi)去除堆石子從圈內(nèi)去除;78791 1、二叉搜索樹(shù)、二叉搜索樹(shù)是一棵二元樹(shù)，或者為空，或者每個(gè)結(jié)點(diǎn)含有一個(gè)可比較大小的數(shù)據(jù)元素。并且：（1）若它的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；（2）若它的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；（3 它的左、右子樹(shù)也分別為二叉

53、排序樹(shù)注：樹(shù)中所有結(jié)點(diǎn)互異451253337241006190783451253372410061907880查找過(guò)程查找過(guò)程：(1)若若T是空樹(shù)，則搜索失敗，否則：是空樹(shù)，則搜索失敗，否則：(2)若若x等于等于T的根結(jié)點(diǎn)的數(shù)據(jù)域之值，則查找成功；的根結(jié)點(diǎn)的數(shù)據(jù)域之值，則查找成功；否則：否則：(3)若若x小于小于T的根結(jié)點(diǎn)的數(shù)據(jù)域之值，則搜索左子樹(shù)；的根結(jié)點(diǎn)的數(shù)據(jù)域之值，則搜索左子樹(shù)；否則：否則：(4)查找右子樹(shù)。查找右子樹(shù)。2 2、在二叉搜索樹(shù)、在二叉搜索樹(shù)T T中查找標(biāo)識(shí)符中查找標(biāo)識(shí)符x x81n設(shè)設(shè)S=x1,x2,.,xn是一個(gè)有序集，且是一個(gè)有序集，且x1x2.xn。表示有序集。表示有

54、序集S的二叉搜索樹(shù)，利用二叉樹(shù)的結(jié)點(diǎn)來(lái)存儲(chǔ)有序集中的元素。的二叉搜索樹(shù)，利用二叉樹(shù)的結(jié)點(diǎn)來(lái)存儲(chǔ)有序集中的元素。二叉搜索樹(shù)的葉結(jié)點(diǎn)是形如二叉搜索樹(shù)的葉結(jié)點(diǎn)是形如(xi，xi+1)的開(kāi)區(qū)間。在表示的開(kāi)區(qū)間。在表示S的的二叉搜索樹(shù)中搜索一個(gè)元素二叉搜索樹(shù)中搜索一個(gè)元素x，返回的結(jié)果有兩種情形：，返回的結(jié)果有兩種情形：q在二叉搜索樹(shù)的內(nèi)結(jié)點(diǎn)中找到在二叉搜索樹(shù)的內(nèi)結(jié)點(diǎn)中找到x=xi。q在二叉搜索樹(shù)的葉結(jié)點(diǎn)中確定在二叉搜索樹(shù)的葉結(jié)點(diǎn)中確定x(xi，xi+1)。n設(shè)第一種情形中找到元素設(shè)第一種情形中找到元素x=xi的概率為的概率為bi；在第二種情形中；在第二種情形中確定確定x(xi，xi+1)的概率為的概率

55、為ai。并約定。并約定x0=-，xn+1=+。顯然。顯然有有；，；，njbniaji10000d1d2d3d4d5d1k2k3k4k5kn搜索成功與不成功的概率搜索成功與不成功的概率1ab10niniii表示內(nèi)部結(jié)點(diǎn)，包含了關(guān)鍵碼集合中的某一個(gè)關(guān)鍵碼；表示外部結(jié)點(diǎn)，代表了造成搜索失敗的各關(guān)鍵碼間隔中的不在關(guān)鍵碼集合中的關(guān)鍵碼。 在每?jī)蓚€(gè)外部結(jié)點(diǎn)之間必然存在一個(gè)內(nèi)部結(jié)點(diǎn)。82n(a0,b1,a1,.,bn,an)稱為集合稱為集合S的存取概率分布。的存取概率分布。n在表示在表示S的二叉搜索樹(shù)的二叉搜索樹(shù)T中，設(shè)存儲(chǔ)元素中，設(shè)存儲(chǔ)元素xi的結(jié)點(diǎn)深度為的結(jié)點(diǎn)深度為ci；存儲(chǔ)葉結(jié)點(diǎn)；存儲(chǔ)葉結(jié)點(diǎn)(xj,x

56、j+1)的結(jié)點(diǎn)的結(jié)點(diǎn)深度為深度為dj，則，則次數(shù)點(diǎn)時(shí)時(shí)所需的關(guān)鍵碼比搜索:1)1 (10結(jié)該ininjjjiicdacbpn上式表示在二叉搜索樹(shù)T中作一次搜索所需要的平均比較次數(shù)。P又稱為二叉搜索樹(shù)T的平均路長(zhǎng)。在一般情況下，不同的二叉樹(shù)的平均路長(zhǎng)是不相同的。0d1d2d3d4d5d1k2k3k4k5k832.40 Total0.30 0.10 3 0.15 0.05 3 0.15 0.05 3 0.15 0.05 3 0.20 0.10 2 0.10 0.05 2 0.60 0.20 2 0.20 0.10 1 0.15 0.05 2 0.10 0.10 0 0.30 0.15 1 onco

57、ntributiy probabilit depth node54321 054321ddddddkkkkk0d1d2d3d4d5d1k2k3k4k5kninjjjiidacbp10)1 (84最優(yōu)二叉搜索樹(shù)問(wèn)題最優(yōu)二叉搜索樹(shù)問(wèn)題是對(duì)于有序集是對(duì)于有序集S及其存取概率及其存取概率分布分布(a0,b1,a1,.,bn,an)，在所有表示有序集，在所有表示有序集S的二叉的二叉搜索樹(shù)中找出一棵具有最小平均路長(zhǎng)的二叉搜索樹(shù)。搜索樹(shù)中找出一棵具有最小平均路長(zhǎng)的二叉搜索樹(shù)。85對(duì)于任一棵子樹(shù)對(duì)于任一棵子樹(shù)Tj，它由，它由keyi+1,keyi+2,keyj組組成，成，其內(nèi)部結(jié)點(diǎn)的權(quán)值為其內(nèi)部結(jié)點(diǎn)的權(quán)值為pi+1,pi+2,pj外部結(jié)點(diǎn)的權(quán)值為外部結(jié)點(diǎn)的權(quán)值為q,qi+1,qi+2,qj使用數(shù)