動(dòng)態(tài)規(guī)劃法課件

算法與算法復(fù)雜性王濤1PPT學(xué)習(xí)交流第六章動(dòng)態(tài)規(guī)劃法6.1概

述

6.2圖問題中的動(dòng)態(tài)規(guī)劃法6.3組合問題中的動(dòng)態(tài)規(guī)劃法6.4查找問題中的動(dòng)態(tài)規(guī)劃法2PPT學(xué)習(xí)交流6.1概

述

6.1.1最優(yōu)化問題6.1.2最優(yōu)性原理6.1.3動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想3PPT學(xué)習(xí)交流動(dòng)態(tài)規(guī)劃(Dynamicprogramming)是一種算法設(shè)計(jì)技術(shù)，是用來解決一種多段決策過程最優(yōu)的通用方法。動(dòng)態(tài)規(guī)劃方法是一種對具有交疊子問題進(jìn)行求解的技術(shù)。動(dòng)態(tài)規(guī)劃建議，對交疊子問題的每個(gè)較小子問題求解一次后記錄在表中，就可以從表中得到原始問題的解。對一個(gè)最優(yōu)問題應(yīng)用動(dòng)態(tài)規(guī)劃方法要求該問題滿足最優(yōu)性原則：一個(gè)最優(yōu)問題的任何實(shí)例的最優(yōu)解是由該實(shí)例的子實(shí)例的最優(yōu)解組成的。4PPT學(xué)習(xí)交流付款問題：超市的自動(dòng)柜員機(jī)（POS機(jī)）要找給顧客數(shù)量最少的現(xiàn)金。例如，要找4元6角現(xiàn)金，如果POS機(jī)送出一大堆硬幣，比如46個(gè)1角錢，就讓人笑話了，而最好找2個(gè)2元、1個(gè)5角和1個(gè)1角。假定POS機(jī)中有n張面值為pi(1≤i≤n)的貨幣，用集合P={p1,p2,…,pn}表示，如果POS機(jī)需支付的現(xiàn)金為A，那么，它必須從P中選取一個(gè)最小子集S，使得

（式6.1）如果用向量X=(x1,x2,…,xn)表示S中所選取的貨幣，則

（式6.2）

6.1.1最優(yōu)化問題5PPT學(xué)習(xí)交流那么，POS機(jī)支付的現(xiàn)金必須滿足（式6.3）集合P是該問題的輸入，滿足式6.1的解稱為可行解，式6.2是解的表現(xiàn)形式，因?yàn)橄蛄縓中有n個(gè)元素，每個(gè)元素的取值為0或1，所以，可以有2n個(gè)不同的向量，所有這些向量的全體構(gòu)成該問題的解空間，式6.3是該問題的約束條件，式6.4是該問題的目標(biāo)函數(shù)，使式6.4取得極小值的解稱為該問題的最優(yōu)解。

并且

（式6.4）

6PPT學(xué)習(xí)交流該問題有n個(gè)輸入，它的解由這n個(gè)輸入的一個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的條件，這些條件稱為約束條件，滿足約束條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個(gè)，為了衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，這些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得極值（極大或極?。┑目尚薪夥Q為最優(yōu)解，這類問題就稱為最優(yōu)化問題。7PPT學(xué)習(xí)交流6.1.2最優(yōu)性原理

對于一個(gè)具有n個(gè)輸入的最優(yōu)化問題，其求解過程往往可以劃分為若干個(gè)階段，每一階段的決策僅依賴于前一階段的狀態(tài)，由決策所采取的動(dòng)作使?fàn)顟B(tài)發(fā)生轉(zhuǎn)移，成為下一階段決策的依據(jù)。如圖6.1所示，S0是初始狀態(tài)，依據(jù)此狀態(tài)作出決策P1，按照P1所采取的動(dòng)作，使?fàn)顟B(tài)轉(zhuǎn)換為S1，依據(jù)狀態(tài)S1作出決策P2，按照P2所采取的動(dòng)作，使?fàn)顟B(tài)S1轉(zhuǎn)換為S2，……，經(jīng)過一系列的決策和狀態(tài)轉(zhuǎn)換，到達(dá)最終狀態(tài)Sn，從而，一個(gè)決策序列在不斷變化的狀態(tài)中產(chǎn)生。這個(gè)決策序列產(chǎn)生的過程稱為多階段決策過程。S0P1P2Pn圖6.1多階段決策過程S1S2Sn-1Sn8PPT學(xué)習(xí)交流例最優(yōu)性原理（OptimalPrinciple）：無論決策過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的當(dāng)前狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。換言之，在多階段決策中，各子問題的解只與它前面的子問題的解相關(guān)，而且各子問題的解都是相對于當(dāng)前狀態(tài)的最優(yōu)解，整個(gè)問題的最優(yōu)解是由各個(gè)子問題的最優(yōu)解構(gòu)成。如果一個(gè)問題滿足最優(yōu)性原理通常稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。9PPT學(xué)習(xí)交流最優(yōu)性原理無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列。原理告訴我們，一個(gè)最優(yōu)問題的任何實(shí)例的最優(yōu)解是由該實(shí)例的子實(shí)例的最優(yōu)解組成。一般來說，如果所求解問題對于最優(yōu)性原理成立，則說明用動(dòng)態(tài)規(guī)劃方法有可能解決該問題。而解決問題的關(guān)鍵在于獲取各階段問的遞推關(guān)系式。10PPT學(xué)習(xí)交流6.1.3動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

動(dòng)態(tài)規(guī)劃法將待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對應(yīng)決策過程的一個(gè)階段，一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。為了達(dá)到這個(gè)目的，可以用一個(gè)表來記錄所有已解決的子問題的解，這就是動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想。具體的動(dòng)態(tài)規(guī)劃法是多種多樣的，但他們具有相同的填表形式。11PPT學(xué)習(xí)交流原問題的解原問題圖6.3動(dòng)態(tài)規(guī)劃法的求解過程……

填表子問題1子問題2子問題n12PPT學(xué)習(xí)交流劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。選擇狀態(tài)：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。確定決策并寫出狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。寫出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。動(dòng)態(tài)規(guī)劃算法的基本步驟13PPT學(xué)習(xí)交流可以用動(dòng)態(tài)規(guī)劃法求解的問題除了能夠分解為相互重疊的若干子問題外，還要滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)），這類問題具有如下特征：該問題的最優(yōu)解中也包含著其子問題的最優(yōu)解。在分析問題是否滿足最優(yōu)性原理時(shí)，通常先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。動(dòng)態(tài)規(guī)劃法利用問題的最優(yōu)性原理，以自底向上的方式從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。應(yīng)用動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段：（1）分段：將原問題分解為若干個(gè)相互重疊的子問題；（2）分析：分析問題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推式；（3）求解：利用遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。

14PPT學(xué)習(xí)交流6.2圖問題中的動(dòng)態(tài)規(guī)劃法

6.2.1TSP問題

6.2.2多段圖的最短路徑問題15PPT學(xué)習(xí)交流6.2.1TSP問題

TSP問題是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。各個(gè)城市間的距離可以用代價(jià)矩陣來表示，如果(i,j)E，則cij＝∞。16PPT學(xué)習(xí)交流假設(shè)從頂點(diǎn)i出發(fā)，令d(i,V')表示從頂點(diǎn)i出發(fā)經(jīng)過V'中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)i的最短路徑長度，開始時(shí)，V'＝V－{i}，于是，TSP問題的動(dòng)態(tài)規(guī)劃函數(shù)為：d(i,V')=min{cik+d(k,V－{k})}(k∈V')（式6.5）d(k,{})=cki(k≠i)（式6.6）17PPT學(xué)習(xí)交流從城市0出發(fā)，經(jīng)城市1、2、3然后回到城市0的最短路徑長度是：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}這是最后一個(gè)階段的決策，它必須依據(jù)d(1,{2,3})、d(2,{1,3})和d(3,{1,2})的計(jì)算結(jié)果，而：18PPT學(xué)習(xí)交流d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}這一階段的決策又依賴于下面的計(jì)算結(jié)果：d(1,{2})=c12+d(2,{})d(2,{3})=c23+d(3,{})d(3,{2})=c32+d(2,{})d(1,{3})=c13+d(3,{})d(2,{1})=c21+d(1,{})d(3,{1})=c31+d(1,{})而下式可以直接獲得（括號中是該決策引起的狀態(tài)轉(zhuǎn)移）：d(1,{})=c10=5(1→0)d(2,{})=c20=6(2→0)d(3,{})=c30=3(3→0)19PPT學(xué)習(xí)交流再向前推導(dǎo)，有：d(1,{2})=c12+d(2,{})=2+6=8(1→2)d(1,{3})=c13+d(3,{})=3+3=6(1→3)d(2,{3})=c23+d(3,{})=2+3=5(2→3)d(2,{1})=c21+d(1,{})=4+5=9(2→1)d(3,{1})=c31+d(1,{})=7+5=12(3→1)d(3,{2})=c32+d(2,{})=5+6=11(3→2)再向推導(dǎo)，有：d(1,{2,3})=min{c12+d(2,{3}),c13+d(3,{2})}=min{2+5,3+11}=7(1→2)d(2,{1,3})=min{c21+d(1,{3}),c23+d(3,{1})}=min{4+6,2+12}=10(2→1)20PPT學(xué)習(xí)交流d(3,{1,2})=min{c31+d(1,{2}),c32+d(2,{1})}=min{7+8,5+9}=14(3→2)最后有：d(0,{1,2,3})=min{c01+d(1,{2,3}),c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)從頂點(diǎn)0出發(fā)的TSP問題的最短路徑長度為10，路徑是0→1→2→3→0。21PPT學(xué)習(xí)交流假設(shè)對n個(gè)頂點(diǎn)分別用0～n-1的數(shù)字編號，考慮從頂點(diǎn)0出發(fā)求解TSP問題的填表形式。首先，按個(gè)數(shù)為1、2、…、n-1的順序生成1～n-1個(gè)元素的子集存放在數(shù)組V[2n-1]中，例如當(dāng)n=4時(shí)，V[1]={1},V[2]={2},V[3]={3},V[4]={1,2},V[5]={1,3},V[6]={2,3},V[7]={1,2,3}。設(shè)數(shù)組d[n][2n-1]存放迭代結(jié)果，其中d[i][j]表示從頂點(diǎn)i經(jīng)過子集V[j]中的頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)0的最短路徑長度。首先，根據(jù)式6.6將數(shù)組d的第0列初始化，然后根據(jù)式6.5逐列計(jì)算，其填表過程如圖所示。ji{}{1}{2}{3}{1,2}{1,3}{2,3}{1,2,3}0

1015

86

7

269

5

10

331211

14

圖6.7動(dòng)態(tài)規(guī)劃法的填表過程22PPT學(xué)習(xí)交流設(shè)頂點(diǎn)之間的代價(jià)存放在數(shù)組c[n][n]中，動(dòng)態(tài)規(guī)劃法求解TSP問題的算法如下：

算法6.1——TSP問題

1．for(i=1;i<n;i++)//初始化第0列

d[i][0]=c[i][0];2．for(j=1;j<2n-1-1;j++)for(i=1;i<n;i++)//依次進(jìn)行第i次迭代

if(子集V[j]中不包含i)

對V[j]中的每個(gè)元素k，計(jì)算d[i][j]=min(c[i][k]+d[k][j-1]);3．對V[2n-1-1]中的每一個(gè)元素k，計(jì)算d[0][2n-1-1]=min(c[0][k]+d[k][2n-1-2]);4．輸出最短路徑長度d[0][2n-1-1];偽代碼算法6.1的時(shí)間復(fù)雜性為O(2n)。和蠻力法相比，動(dòng)態(tài)規(guī)劃法求解TSP問題，把原來的時(shí)間復(fù)雜性是O(n!)的排列問題，轉(zhuǎn)化為組合問題，從而降低了算法的時(shí)間復(fù)雜性，但它仍需要指數(shù)時(shí)間。

23PPT學(xué)習(xí)交流6.2.2多段圖的最短路徑問題設(shè)圖G=(V,E)是一個(gè)帶權(quán)有向連通圖，如果把頂點(diǎn)集合V劃分成k個(gè)互不相交的子集Vi（2≤k≤n,1≤i≤k），使得E中的任何一條邊(u,v)，必有u∈Vi，v∈Vi+m（1≤i＜k,

1＜i+m≤k），則稱圖G為多段圖，稱s∈V1為源點(diǎn)，t∈Vk為終點(diǎn)。多段圖的最短路徑問題是求從源點(diǎn)到終點(diǎn)的最小代價(jià)路徑。

由于多段圖將頂點(diǎn)劃分為k個(gè)互不相交的子集，所以，多段圖劃分為k段，每一段包含頂點(diǎn)的一個(gè)子集。根據(jù)多段圖的定義，每個(gè)子集中的頂點(diǎn)互不鄰接。不失一般性，將多段圖的頂點(diǎn)按照段的順序進(jìn)行編號，同一段內(nèi)頂點(diǎn)的相互順序無關(guān)緊要。假設(shè)圖中的頂點(diǎn)個(gè)數(shù)為n，則源點(diǎn)s的編號為0，終點(diǎn)t的編號為n-1，并且，對圖中的任何一條邊(u,v)，頂點(diǎn)u的編號小于頂點(diǎn)v的編號。24PPT學(xué)習(xí)交流2120345678949387684756866537圖6.8一個(gè)多段圖25PPT學(xué)習(xí)交流設(shè)G是一個(gè)有向加權(quán)圖，則G從頂點(diǎn)i到頂點(diǎn)j之間的最短路徑問題滿足最優(yōu)性原理。證明：設(shè)i～ip～iq～j是一條最短路徑，但其中子路徑ip～iq～j不是最優(yōu)的，假設(shè)最優(yōu)的路徑為ip～iq’～j，則我們重新構(gòu)造一條路徑：i～ip～iq’～j顯然該路徑長度小于i～ip～iq～j，與i～ip～iq～j是頂點(diǎn)i到頂點(diǎn)j的最短路徑相矛盾.所以，原問題滿足最優(yōu)性原理。26PPT學(xué)習(xí)交流對多段圖的邊(u,v)，用cuv表示邊上的權(quán)值，將從源點(diǎn)s到終點(diǎn)t的最短路徑記為d(s,t)，則從源點(diǎn)0到終點(diǎn)9的最短路徑d(0,9)由下式確定：d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}

這是最后一個(gè)階段的決策，它依賴于d(1,9)、d(2,9)和d(3,9)的計(jì)算結(jié)果，而d(1,9)=min{c14+d(4,9),c15+d(5,9)}d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}d(3,9)=min{c35+d(5,9),c36+d(6,9)}

這一階段的決策又依賴于d(4,9)、d(5,9)和d(6,9)的計(jì)算結(jié)果：27PPT學(xué)習(xí)交流d(4,9)=min{c47+d(7,9),c48+d(8,9)}d(5,9)=min{c57+d(7,9),c58+d(8,9)}d(6,9)=min{c67+d(7,9),c68+d(8,9)}

這一階段的決策依賴于d(7,9)和d(8,9)的計(jì)算，而d(7,9)和d(8,9)可以直接獲得（括號中給出了決策產(chǎn)生的狀態(tài)轉(zhuǎn)移）：d(7,9)=c79＝7(7→9)d(8,9)=c89＝3(8→9)

再向前推導(dǎo)，有：d(6,9)=min{c67+d(7,9),c68+d(8,9)}=min{6+7,5+3}=8(6→8)d(5,9)=min{c57+d(7,9),c58+d(8,9)}=min{8+7,6+3}=9(5→8)d(4,9)=min{c47+d(7,9),c48+d(8,9)}=min{5+7,6+3}=9(4→8)28PPT學(xué)習(xí)交流d(3,9)=min{c35+d(5,9),c36+d(6,9)}=min{4+9,7+8}=13(3→5)d(2,9)=min{c24+d(4,9),c25+d(5,9),c26+d(6,9)}=min{6+9,7+9,8+8}=15(2→4)d(1,9)=min{c14+d(4,9),c15+d(5,9)}=min{9+9,8+9}=17(1→5)d(0,9)=min{c01+d(1,9),c02+d(2,9),c03+d(3,9)}=min{4+17,2+15,3+13}=16(0→3)得到最短路徑為0→3→5→8→9，長度為16。

29PPT學(xué)習(xí)交流下面考慮多段圖的最短路徑問題的填表形式。用一個(gè)數(shù)組cost[n]作為存儲(chǔ)子問題解的表格，cost[i]表示從頂點(diǎn)i到終點(diǎn)n-1的最短路徑，數(shù)組path[n]存儲(chǔ)狀態(tài)，path[i]表示從頂點(diǎn)i到終點(diǎn)n-1的路徑上頂點(diǎn)i的下一個(gè)頂點(diǎn)。則：

cost[i]=min{cij+cost[j]}(i≤j≤n且頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn))（式6.7）path[i]=使cij+cost[j]最小的j（式6.8）30PPT學(xué)習(xí)交流算法6.2——多段圖的最短路徑

1．初始化：數(shù)組cost[n]初始化為最大值，數(shù)組path[n]初始化為-1；

2．for(i=n-2;i>=0;i--)2.1對頂點(diǎn)i的每一個(gè)鄰接點(diǎn)j，根據(jù)式6.7計(jì)算cost[i];2.2根據(jù)式6.8計(jì)算path[i];3．輸出最短路徑長度cost[0];4.輸出最短路徑經(jīng)過的頂點(diǎn)：

4.1i=04.2循環(huán)直到path[i]=n-14.2.1輸出path[i];4.2.2i=path[i];偽代碼動(dòng)態(tài)規(guī)劃法求解多段圖的最短路徑問題的算法31PPT學(xué)習(xí)交流練32PPT學(xué)習(xí)交流6.3組合問題中的動(dòng)態(tài)規(guī)劃法6.3.10/1背包問題

6.3.2最長公共子序列問題33PPT學(xué)習(xí)交流6.3.10/1背包問題

給定n種物品和一個(gè)背包，物品i的重量是wi，其價(jià)值為vi，背包的容量為C。背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?如果在選擇裝入背包的物品時(shí)，對每種物品i只有兩種選擇：裝入背包或不裝入背包，即不能將物品i裝入背包多次，也不能只裝入物品i的一部分，則稱為0/1背包問題。34PPT學(xué)習(xí)交流在0/1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的情況，則當(dāng)xi=0時(shí)，表示物品i沒有被裝入背包，xi=1時(shí)，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標(biāo)函數(shù)：

（式6.9）（式6.10）問題歸結(jié)為尋找一個(gè)滿足約束條件式6.9，并使目標(biāo)函數(shù)式6.10達(dá)到最大的解向量X=(x1,x2,…,xn)。35PPT學(xué)習(xí)交流首先證明0/1背包問題滿足最優(yōu)性原理。設(shè)(x1,x2,…,xn)是所給0/1背包問題的一個(gè)最優(yōu)解，則(x2,…,xn)是下面一個(gè)子問題的最優(yōu)解：如若不然，設(shè)(y2,…,yn)是上述子問題的一個(gè)最優(yōu)解，則，且。因此，，這說明(x1,y2,…,yn)是所給0/1背包問題比(x1,x2,…,xn)更優(yōu)的解，從而導(dǎo)致矛盾。

36PPT學(xué)習(xí)交流0/1背包問題可以看作是決策一個(gè)序列(x1,x2,…,xn)，對任一變量xi的決策是決定xi=1還是xi=0。在對xi-1決策后，已確定了(x1,…,xi-1)，在決策xi時(shí)，問題處于下列兩種狀態(tài)之一：a.背包容量不足以裝入物品i，則xi=0背包不增加價(jià)值；b.背包容量可以裝入物品i，則xi=1背包的價(jià)值增加了vi。這兩種情況下背包價(jià)值的最大者應(yīng)該是對xi決策后的背包價(jià)值。令V(i,j)表示在前i(1≤i≤n)個(gè)物品中能夠裝入容量為j（1≤j≤C）的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)：

V(i,0)=V(0,j)=0（式6.11）37PPT學(xué)習(xí)交流式6.11表明：把前面i個(gè)物品裝入容量為0的背包和把0個(gè)物品裝入容量為j的背包，得到的價(jià)值均為0。式6.12的第一個(gè)式子表明：如果第i個(gè)物品的重量大于背包的容量，則裝入前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)值是相同的，即物品i不能裝入背包；第二個(gè)式子表明：如果第i個(gè)物品的重量小于背包的容量，則會(huì)有以下兩種情況：（1）如果把第i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把前i-1個(gè)物品裝入容量為j-wi的背包中的價(jià)值加上第i個(gè)物品的價(jià)值vi；（2）如果第i個(gè)物品沒有裝入背包，則背包中物品的價(jià)值就等于把前i-1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。顯然，取二者中價(jià)值較大者作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。

38PPT學(xué)習(xí)交流第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-wn的背包中；否則，第n個(gè)物品沒有被裝入背包，前n-1個(gè)物品被裝入容量為C的背包中。依此類推，直到確定第1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)：

39PPT學(xué)習(xí)交流例如，有5個(gè)物品，其重量分別是{2,2,6,5,4}，價(jià)值分別為{6,3,5,4,6}，背包的容量為10，求裝入背包的物品和獲得的最大價(jià)值。

根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè)(n+1)×(C+1)的二維表V，V[i][j]表示把前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，根據(jù)式6.11把表的第0行和第0列初始化為0，然后一行一行地計(jì)算V[i][j]，如圖6.9所示。

40PPT學(xué)習(xí)交流圖6.90/1背包求解（填表）過程x5=1x4=0x3=0x2=1x1=1

012345678910

00000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=5v5=650066991212151515可以看到，裝入背包的物品的最大價(jià)值是15，根據(jù)式6.13，裝入背包的物品為X={1,1,0,0,1}。41PPT學(xué)習(xí)交流設(shè)n個(gè)物品的重量存儲(chǔ)在數(shù)組w[n]中，價(jià)值存儲(chǔ)在數(shù)組v[n]中，背包容量為C，數(shù)組V[n+1][C+1]存放迭代結(jié)果，其中V[i][j]表示前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值，數(shù)組x[n]存儲(chǔ)裝入背包的物品，動(dòng)態(tài)規(guī)劃法求解0/1背包問題的算法如下：

42PPT學(xué)習(xí)交流算法6.3——0/1背包問題

intKnapSack(intn,intw[],intv[]){for(i=0;i<=n;i++)//初始化第0列

V[i][0]=0;for(j=0;j<=C;j++)//初始化第0行

V[0][j]=0;for(i=1;i<=n;i++)//計(jì)算第i行，進(jìn)行第i次迭代

for(j=1;j<=C;j++)if(j<w[i])V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);j=C;//求裝入背包的物品

for(i=n;i>0;i--){if(V[i][j]>V[i-1][j]){x[i]=1;j=j-w[i];}elsex[i]=0;}returnV[n][C];//返回背包取得的最大價(jià)值}C++描述43PPT學(xué)習(xí)交流6.3.2最長公共子序列問題

對給定序列X=(x1,x2,…,xm)和序列Z=(z1,z2,…,zk)，Z是X的子序列當(dāng)且僅當(dāng)存在一個(gè)嚴(yán)格遞增下標(biāo)序列(i1,i2,…,ik)，使得對于所有j=1,2,…,k，有zj=xij（1≤ij≤m）。例如，對于序列X=(a,b,c,b,d,a,b)，序列(b,c,d,b)是X的一個(gè)長度為4的子序列，相應(yīng)的遞增下標(biāo)序列為(2,3,5,7)，序列(a,c,b,d,b)是X的一個(gè)長度為5的子序列，相應(yīng)的遞增下標(biāo)序列為(1,3,4,5,7)?？梢?，一個(gè)給定序列的子序列可以有多個(gè)。給定兩個(gè)序列X和Y，當(dāng)另一個(gè)序列Z既是X的子序列又是Y的子序列時(shí)，稱Z是序列X和Y的公共子序列。例如，序列X=(a,b,c,b,d,b)，Y=(a,c,b,b,a,b,d,b,b)，序列(a,c,b)是序列X和Y的一個(gè)長度為3的公共子序列，序列(a,b,b,d,b)是序列X和Y的一個(gè)長度為5的公共子序列。最長公共子序列問題就是在序列X和Y的公共子序列中查找長度最長的公共子序列。

44PPT學(xué)習(xí)交流

設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，記Xk為序列X中前k個(gè)連續(xù)字符組成的子序列，Yk為序列Y中前k個(gè)連續(xù)字符組成的子序列，Zk為序列Z中前k個(gè)連續(xù)字符組成的子序列，顯然有下式成立：（1）若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列；（2）若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列；（3）若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列?？梢姡瑑蓚€(gè)序列的最長公共子序列包含了這兩個(gè)序列的前綴序列的最長公共子序列。因此，最長公共子序列問題滿足最優(yōu)性原理。要找出序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列，可按下述遞推方式計(jì)算：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-145PPT學(xué)習(xí)交流的最長公共子序列，然后在其尾部加上xm即可得到X和Y的最長公共子序列；當(dāng)xm≠yn時(shí)，必須求解兩個(gè)子問題：找出Xm-1和Y的最長公共子序列以及Xm和Yn-1的最長公共子序列，這兩個(gè)公共子序列中的較長者即為X和Y的最長公共子序列。用L[i][j]表示子序列Xi和Yj的最長公共子序列的長度，可得如下動(dòng)態(tài)規(guī)劃函數(shù)：L[0][0]=L[i][0]=L[0][j]=0(1≤i≤m,1≤j≤n)（式6.14）

（式6.15）

由此，把序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列的搜索分為m個(gè)階段，第1階段，按照式6.15計(jì)算X1和Yj的最長公共子序列長度L[1][j]（1≤j≤n），第2階段，按照式6.15計(jì)算X2和Yj的最長公共子序列長度L[2][j]（1≤j≤n），依此類推，最后在第m階段，計(jì)算Xm和Yj的最長公共子序列長度L[m][j]（1≤j≤n），則L[m][n]就是序列Xm和Yn的最長公共子序列的長度。

46PPT學(xué)習(xí)交流

為了得到序列Xm和Yn具體的最長公共子序列，設(shè)二維表S[m+1][n+1]，其中S[i][j]表示在計(jì)算L[i][j]的過程中的搜索狀態(tài)，并且有：

若S[i][j]=1，表明ai=bj，則下一個(gè)搜索方向是S[i-1][j-1]；若S[i][j]=2，表明ai≠bj且L[i][j-1]≥L[i-1][j]，則下一個(gè)搜索方向是S[i][j-1]；若S[i][j]=3，表明ai≠bj且L[i][j-1]＜L[i-1][j]，則下一個(gè)搜索方向是S[i-1][j]。

如：序列X=(a,b,c,b,d,b)，Y=(a,c,b,b,a,b,d,b,b)，建立兩個(gè)(m+1)×(n+1)的二維表L和表S，分別存放搜索過程中得到的子序列的長度和狀態(tài)。首先把表L和表S的第0行和第0列初始化為0，然后根據(jù)式6.15和6.16逐行計(jì)算填入表L和表S中。計(jì)算結(jié)果如圖6.10所示。

47PPT學(xué)習(xí)交流(a)長度矩陣L(b)狀態(tài)矩陣S圖6.10最長公共子序列求解示意圖0123456789012345678900000000000000000000010111111111101222122222011222222220321121211301222222223031222222240123333333403311313115012333344450333222122601234444556033113121148PPT學(xué)習(xí)交流6.4查找問題中的動(dòng)態(tài)規(guī)劃法

6.4.1最優(yōu)二叉查找樹

6.4.2近似串匹配問題49PPT學(xué)習(xí)交流

設(shè){r1,r2,…,rn}是n個(gè)記錄的集合，其查找概率分別是{p1,p2,…,pn}，最優(yōu)二叉查找樹（OptimalBinarySearchTrees）是以這n個(gè)記錄構(gòu)成的二叉查找樹中具有最少平均比較次數(shù)的二叉查找樹，即最小，其中pi是記錄ri的查找概率，ci是在二叉查找樹中查找ri的比較次數(shù)。例如，集合{A,B,C,D}的查找概率是{0.1,0.2,0.4,0.3}，圖6.11給出了三棵二叉查找樹，在查找成功的情況下，二叉查找樹(a)的平均比較次數(shù)是0.1×1＋0.2×2+0.4×3+0.3×4=2.9，二叉查找樹(b)的平均比較次數(shù)是0.1×2＋0.2×1+0.4×2+0.3×3=2.1，最優(yōu)二叉查找樹是(c)，平均比較次數(shù)是0.1×3＋0.2×2+0.4×1+0.3×2=1.7。

6.4.1最優(yōu)二叉查找樹

50PPT學(xué)習(xí)交流ABCD(a)(b)(c)圖6.11二叉查找樹示例BCDAABCD

將由{r1,r2,…,rn}構(gòu)成的二叉查找樹記為T(1,n)，其中rk（1≤k≤n）是T(1,n)的根結(jié)點(diǎn)，則其左子樹T(1,k-1)由{r1,…,rk-1}構(gòu)成，其右子樹T(k+1,n)由{rk+1,…,rn}構(gòu)成，如圖6.12所示。顯然，若T(1,n)是最優(yōu)二叉查找樹，則其左子樹T(1,k-1)和右子樹T(k+1,n)也是最優(yōu)二叉查找樹，如若不然，假設(shè)T'(1,k-1)是比T(1,k-1)更優(yōu)的二叉查找樹，則T'(1,k-1)的平均比較次數(shù)小于T(1,k-1)的平均比較次數(shù)，從而由T'(1,k-1)、rk和T(k+1,n)構(gòu)成的二叉查找樹T'(1,n)的平均比較次數(shù)小于T(1,n)的平均比較次數(shù)，這與T(1,n)是最優(yōu)二叉查找樹的假設(shè)相矛盾。因此最優(yōu)二叉查找樹滿足最優(yōu)性原理。

51PPT學(xué)習(xí)交流rkT(1,n)圖6.12以rk為根的二叉查找樹T(k+1,n)T(1,k-1)

設(shè)T(i,j)是由記錄{ri,…,rj}(1≤i≤j≤n)構(gòu)成的二叉查找樹，C(i,j)是這棵二叉查找樹的平均比較次數(shù)。雖然最后的結(jié)果是C(1,n)，但遵循動(dòng)態(tài)規(guī)劃法的求解方法,需要求出所有較小子問題C(i,j)的值，考慮從{ri,…,rj}中選擇一個(gè)記錄rk作為二叉查找樹的根結(jié)點(diǎn)，可以得到如下關(guān)系：

52PPT學(xué)習(xí)交流

因此，得到如下動(dòng)態(tài)規(guī)劃函數(shù)：

C(i,i-1)=0(1≤i≤n+1)（式6.17）C(i,