算法設(shè)計(jì)與分析耿國(guó)華第三章

第三章動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)與分析主編耿國(guó)華本章內(nèi)容Chapter3

3.1

動(dòng)態(tài)規(guī)劃基礎(chǔ)3.1.1動(dòng)態(tài)規(guī)劃的基本思想3.1.2動(dòng)態(tài)規(guī)劃的基本要素3.1.3動(dòng)態(tài)規(guī)劃的基本步驟3.1.4動(dòng)態(tài)規(guī)劃示例——組合數(shù)問(wèn)題3.2線性動(dòng)態(tài)規(guī)劃——合唱隊(duì)形問(wèn)題3.3區(qū)域動(dòng)態(tài)規(guī)劃——矩陣連乘問(wèn)題3.4背包動(dòng)態(tài)規(guī)劃——0-1背包問(wèn)題3.5樹形動(dòng)態(tài)規(guī)劃——最優(yōu)二叉搜索樹問(wèn)題3.6本章小結(jié)

引言

本章給出的動(dòng)態(tài)規(guī)劃技術(shù)可使用較少的時(shí)間求解此類問(wèn)題。與分治法不同，在求解過(guò)程中動(dòng)態(tài)規(guī)劃方法采用自底向上的遞推方式，將原問(wèn)題分解為互不獨(dú)立的小規(guī)模子問(wèn)題，根據(jù)子問(wèn)題的相關(guān)性從已知的各個(gè)局部解中選出能產(chǎn)生最佳解的部分，并將計(jì)算過(guò)程填表，只要某個(gè)子問(wèn)題被解決，它將不會(huì)被重復(fù)求解，從而減少了算法的時(shí)間復(fù)雜度，適合動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題，可以在多項(xiàng)式時(shí)間內(nèi)被求解出來(lái)，常用于最優(yōu)（最大/最小）問(wèn)題的求解過(guò)程.Chapter3本章將針對(duì)線性動(dòng)態(tài)規(guī)劃、區(qū)域動(dòng)態(tài)規(guī)劃、背包動(dòng)態(tài)規(guī)劃、樹形動(dòng)態(tài)規(guī)劃四類具體實(shí)例給出問(wèn)題求解的技術(shù)方法。3.1動(dòng)態(tài)規(guī)劃基礎(chǔ)

3.1.1動(dòng)態(tài)規(guī)劃的基本思想3.1.2動(dòng)態(tài)規(guī)劃的基本要素3.1.3動(dòng)態(tài)規(guī)劃的基本步驟3.1.4動(dòng)態(tài)規(guī)劃示例——組合數(shù)問(wèn)題Chapter93.1.1動(dòng)態(tài)規(guī)劃的基本思想

多階段最優(yōu)化決策解決問(wèn)題的過(guò)程稱為動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃通常是用遞歸程序?qū)崿F(xiàn)的，遞推關(guān)系是實(shí)現(xiàn)由分解后的子問(wèn)題向最終問(wèn)題求解轉(zhuǎn)化的紐帶。3.1.1動(dòng)態(tài)規(guī)劃的基本思想指導(dǎo)思想：動(dòng)態(tài)規(guī)劃是建立在最優(yōu)原則的基礎(chǔ)上，在每一決策步上列出各種可能局部解，按某些條件舍棄肯定不能得到最優(yōu)解的局部解，這是一個(gè)尋找最優(yōu)判斷序列的過(guò)程，即不論初始策略如何，下一次決策必須相對(duì)前一次決策產(chǎn)生的新?tīng)顟B(tài)構(gòu)成最優(yōu)序列。這樣，在每一步都經(jīng)過(guò)篩選，以每一步的最優(yōu)性來(lái)保證全局的最優(yōu)性。基本思想：記錄子問(wèn)題并不斷填表。即將待求解的問(wèn)題分成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。適合動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題，經(jīng)分解后不是互相獨(dú)立的，即它們可以在多項(xiàng)式時(shí)間內(nèi)被求解出來(lái)

Chapter33.1.1動(dòng)態(tài)規(guī)劃的基本思想

多階段最優(yōu)化決策解決問(wèn)題的過(guò)程稱為動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃通常是用遞歸程序?qū)崿F(xiàn)的，遞推關(guān)系是實(shí)現(xiàn)由分解后的子問(wèn)題向最終問(wèn)題求解轉(zhuǎn)化的紐帶，3.1.1動(dòng)態(tài)規(guī)劃的基本思想指導(dǎo)思想：動(dòng)態(tài)規(guī)劃是建立在最優(yōu)原則的基礎(chǔ)上，在每一決策步上列出各種可能局部解，按某些條件舍棄肯定不能得到最優(yōu)解的局部解，這是一個(gè)尋找最優(yōu)判斷序列的過(guò)程，即不論初始策略如何，下一次決策必須相對(duì)前一次決策產(chǎn)生的新?tīng)顟B(tài)構(gòu)成最優(yōu)序列。這樣，在每一步都經(jīng)過(guò)篩選，以每一步的最優(yōu)性來(lái)保證全局的最優(yōu)性?；舅枷耄河涗涀訂?wèn)題并不斷填表。即將待求解的問(wèn)題分成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。適合動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題，經(jīng)分解后不是互相獨(dú)立的，即它們可以在多項(xiàng)式時(shí)間內(nèi)被求解出來(lái)

Chapter33.1.2動(dòng)態(tài)規(guī)劃的基本要素3.1.2動(dòng)態(tài)規(guī)劃的基本要素一個(gè)可用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題必須具備以下三要素：1、最優(yōu)子結(jié)構(gòu)當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)。一般在分析問(wèn)題的最優(yōu)子結(jié)構(gòu)時(shí)，采用反證法。首先假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的，然后再設(shè)法證明在這個(gè)假設(shè)下可以構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。Chapter32、無(wú)后效性(馬爾可夫性)

一旦某階段狀態(tài)已經(jīng)確定，它以前各階段的狀態(tài)無(wú)法直接影響它未來(lái)的決策，且當(dāng)前的狀態(tài)只是對(duì)以往決策的總結(jié)。若將動(dòng)態(tài)規(guī)劃問(wèn)題進(jìn)行抽象，用結(jié)點(diǎn)表示狀態(tài)，邊表示狀態(tài)之間的關(guān)系，這樣的圖必將是一個(gè)有向無(wú)環(huán)圖，即各狀態(tài)之間有著嚴(yán)格的遞推關(guān)系。3.1.2動(dòng)態(tài)規(guī)劃的基本要素

3.1.2動(dòng)態(tài)規(guī)劃的基本要素3、子問(wèn)題重疊性

可用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題，應(yīng)具備的最后一個(gè)基本性質(zhì)是子問(wèn)題的重疊性。在用遞歸算法自頂向下解此問(wèn)題時(shí)，每次產(chǎn)生的子問(wèn)題并不總是新問(wèn)題，有些子問(wèn)題被反復(fù)計(jì)算多次。動(dòng)態(tài)規(guī)劃算法正是利用這種子問(wèn)題的重疊性質(zhì)，對(duì)每個(gè)子問(wèn)題都只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此問(wèn)題時(shí)，只是簡(jiǎn)單的查看一下結(jié)果，從而得到較高的解題效率。題的最優(yōu)解時(shí)，就稱該問(wèn)題具有最優(yōu)子結(jié)構(gòu)。

Chapter33.1.3動(dòng)態(tài)規(guī)劃的基本步驟

3.1.3動(dòng)態(tài)規(guī)劃的基本步驟在求解具體問(wèn)題時(shí)，通常按照以下步驟求解動(dòng)態(tài)規(guī)劃問(wèn)題：(1)找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；(2)遞歸的定義最優(yōu)值；(3)自底向上的方式計(jì)算出最優(yōu)值；(4)根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。如果該問(wèn)題只需求出最優(yōu)值，則可省去步驟（4）；若要進(jìn)一步求出問(wèn)題的最優(yōu)解，則必須執(zhí)行步驟（4），此時(shí)需要記錄更多算法執(zhí)行過(guò)程中的中間數(shù)據(jù)，以便根據(jù)這些數(shù)據(jù)構(gòu)造出最優(yōu)解。Chapter33.1.4動(dòng)態(tài)規(guī)劃的例子

3.1.4動(dòng)態(tài)規(guī)劃的例子

下面就以具體的例子來(lái)說(shuō)明可用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題所應(yīng)具備的基本特征，以及如何運(yùn)用動(dòng)態(tài)規(guī)劃算法來(lái)求解問(wèn)題。例3-1：對(duì)斐波納契數(shù)列F(n)，用動(dòng)態(tài)規(guī)劃算法求出它的第n項(xiàng)。問(wèn)題求解步驟如下：步驟1：最優(yōu)子結(jié)構(gòu)的性質(zhì)用F(n)表示在斐波納契數(shù)列中第n個(gè)數(shù)的值，由于F(n)=F(n-1)+F(n-2),計(jì)算F(n-1),又要知道F(n-2)和F(n-3)的值，這樣整個(gè)問(wèn)題的求解會(huì)導(dǎo)致很多重復(fù)的計(jì)算量，為避免重復(fù)，應(yīng)該將計(jì)算過(guò)的值記錄下來(lái)，下次用到的時(shí)候直接讀出即可。即將原問(wèn)題自底向上分解為若干個(gè)子問(wèn)題，從斐波納契數(shù)列的第一項(xiàng)開(kāi)始，依次遞推計(jì)算前n-1項(xiàng)的值并存儲(chǔ)在一個(gè)數(shù)組中，第n項(xiàng)的值即可用與其相鄰的前兩項(xiàng)的值相加得到，從而保證當(dāng)每個(gè)子問(wèn)題用最優(yōu)的方法求解，故原問(wèn)題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。Chapter33.1.4動(dòng)態(tài)規(guī)劃的例子3.1.4動(dòng)態(tài)規(guī)劃的例子步驟2：建立遞歸方程步驟3：以自底向上的方法來(lái)計(jì)算最優(yōu)解表3-1斐波納契數(shù)列計(jì)算動(dòng)態(tài)規(guī)劃表步驟4：在數(shù)組中分析構(gòu)造出問(wèn)題的解，具體算法如下所示：constintN=100;int

Fib(intn){intF[N]={1,1};

for(inti=2;i<=n;i++)

F[i]=F[i-1]+F[i-2];}Chapter3n01234567F(n)11235813213.1.4動(dòng)態(tài)規(guī)劃的例子

3.1.4動(dòng)態(tài)規(guī)劃的例子例3-2：分別用遞歸和動(dòng)態(tài)規(guī)劃算法解。遞歸：重復(fù)求解子問(wèn)題，如算法3.1所示?！舅惴?.1用遞歸求解組合問(wèn)題】/*功能：求解。輸入：正整數(shù)n,m

輸出：輸出的結(jié)果*/

int

ComB(int

n,intm){if(m==0||n==m)

return(1);elsereturn(ComB(n-1,m-1))+return(ComB(n-1,m));}

Chapter33.1.4動(dòng)態(tài)規(guī)劃的例子3.1.4動(dòng)態(tài)規(guī)劃的例子例3-2：分別用遞歸和動(dòng)態(tài)規(guī)劃算法解。(2)動(dòng)態(tài)規(guī)劃：記錄子問(wèn)題，如算法3.2所示。步驟1：分析最優(yōu)子結(jié)構(gòu)計(jì)算組合數(shù)，可將原問(wèn)題分解為求解兩個(gè)子問(wèn)題，要采用自底向上的方法，先計(jì)算出(i=1…n)，然后用公式（i=1…n，初值）……，依次計(jì)算出其他各項(xiàng)值并填表，當(dāng)子問(wèn)題被求解，原問(wèn)題得解。由于采用了填表技術(shù)，子問(wèn)題被求解后就不用重復(fù)計(jì)算，達(dá)到子問(wèn)題最優(yōu)求解方式，具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。步驟2：建立遞歸關(guān)系根據(jù)公式可以用

C[i][j](i=1~n,j=1~m)來(lái)記錄，即用一張表來(lái)記錄重復(fù)子問(wèn)題的結(jié)果。

Chapter3步驟2：建立遞歸關(guān)系3.1.4動(dòng)態(tài)規(guī)劃的例子

3.1.4動(dòng)態(tài)規(guī)劃的例子例3-2：分別用遞歸和動(dòng)態(tài)規(guī)劃算法解。步驟3：計(jì)算最優(yōu)值如求解(n=5，m=3)，通過(guò)動(dòng)態(tài)規(guī)劃算法來(lái)記錄（其中），結(jié)果如表3-1所示,如計(jì)算表中第四行第二列的值，可以用第三行第一列的與第三行第二列的求和得到，即=6表3-2組合數(shù)計(jì)算動(dòng)態(tài)規(guī)劃表Chapter3步驟2：建立遞歸關(guān)系i=1i=2i=3j=1100j=2210j=3331j=4464j=5510103.1.4動(dòng)態(tài)規(guī)劃的例子

3.1.4動(dòng)態(tài)規(guī)劃的例子例3-2：分別用遞歸和動(dòng)態(tài)規(guī)劃算法解。步驟4：算法描述及分析【算法3.2用動(dòng)態(tài)規(guī)劃求解組合問(wèn)題】/*功能：求解。輸入：正整數(shù)n,m

輸出：輸出的結(jié)果*/int

ComB(intn,intm){intC[n+1][m+1],i,j;/*為更加簡(jiǎn)潔，本例數(shù)組下標(biāo)從1開(kāi)始*/for(j=1;j<=m;j++)C[1][j]=0;for(i=1;i<=n;i++)C[i][1]=i;for(i=2;i<=n;i++)for(j=2;j<=m;j++)

if(i<j)C[i][j]=0;elseC[i][j]=C[i-1][j-1]+C[i-1][j];

return(C[n][m]);}Chapter33.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

Chapter3本節(jié)內(nèi)容1.問(wèn)題描述2.分析最優(yōu)子結(jié)構(gòu)3.建立遞歸關(guān)系4.計(jì)算最優(yōu)值5.程序描述及算法分析3.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

建立在線性結(jié)構(gòu)或圖結(jié)構(gòu)的基礎(chǔ)之上的線性動(dòng)態(tài)規(guī)劃算法，可解決的問(wèn)題具有線性遞推的特點(diǎn)，通常以某一結(jié)點(diǎn)為狀態(tài)，向兩個(gè)方向：即由前向后或者由后向前線性遍歷每個(gè)狀態(tài)，從中找出具有最優(yōu)值的狀態(tài)從而得到問(wèn)題的解，下面我們就用合唱隊(duì)形問(wèn)題來(lái)解決線性動(dòng)態(tài)規(guī)劃問(wèn)題。1.問(wèn)題描述N位同學(xué)站成一排，音樂(lè)老師要請(qǐng)其中的(N-K)位同學(xué)出列，而不改變其他同學(xué)的位置，使得剩下的K位同學(xué)排成合唱隊(duì)形。Chapter33.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

問(wèn)題描述1.問(wèn)題描述合唱隊(duì)形要求：設(shè)K位同學(xué)從左到右依次編號(hào)為1，2，...，K，他們的身高分別為T1,T2，...，TK，則他們的身高滿足T1<...<Ti,且Ti>Ti+1>...>TK(1<=i<=K)。當(dāng)給定隊(duì)員人數(shù)N和每個(gè)學(xué)生的身高T[i]時(shí)，計(jì)算需要多少學(xué)生出列，可以得到最長(zhǎng)的合唱隊(duì)形。如下圖所示：

Chapter3編號(hào):12345…………i-1ii+1…..N3.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

分析最優(yōu)子結(jié)構(gòu)

2.分析最優(yōu)子結(jié)構(gòu)假設(shè)第i位同學(xué)為最高個(gè)，則對(duì)其左邊序列求最長(zhǎng)遞增序列長(zhǎng)度，對(duì)其右邊序列求最長(zhǎng)遞減序列長(zhǎng)度，然后兩者相加再減1（因?yàn)榈趇位同學(xué)被重復(fù)計(jì)算了一次）即可得到整個(gè)合唱隊(duì)形的長(zhǎng)度。設(shè)f1(i)（1=<i<=n）為前i個(gè)同學(xué)的最大上升子序列的長(zhǎng)度，計(jì)算f1(i)的值時(shí)，必須先求得f1(1),f1(2),…,f1(i-1)，再選擇一個(gè)最大的f1(j)（j<i），在前j個(gè)數(shù)中的最大上升序后再加一，就可以得到前i個(gè)數(shù)的最大上升子序列的長(zhǎng)度f(wàn)1(i)。Chapter3由此可見(jiàn)，原問(wèn)題的解即最長(zhǎng)的合唱隊(duì)形取決于最大上升子序列和最大下降子序列的長(zhǎng)度，具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。由于在某一時(shí)刻，它是單向的從一個(gè)狀態(tài)線性遞推到下一個(gè)狀態(tài)，屬于線性動(dòng)態(tài)規(guī)劃問(wèn)題。3.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

建立遞歸關(guān)系3.建立遞歸關(guān)系當(dāng)組成最大上升子序列時(shí)，得到遞歸方程：f1(i)=max{f1(j)+1}(j<i,Tj<Ti)

f1(1)=1;//遞歸出口

設(shè)f2(i)為后面N-i+1位排列的最大下降子序列長(zhǎng)度，用同樣的方法可以得到遞歸方程：f2(i)=max{f2(j)+1}(i<j,Tj<Ti)f2(N)=1;//邊界值

Chapter33.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

計(jì)算最優(yōu)值

4.計(jì)算最優(yōu)值首先用數(shù)組a保存所有人的身高，第一遍正向掃描,從左到右求最大上升子序列的長(zhǎng)度，然后反向掃描，從右到左求最大下降子序列的長(zhǎng)度，然后依次枚舉由前i個(gè)學(xué)生組成的最大上升自序列的長(zhǎng)度和由后N-i+1個(gè)學(xué)生組成的最大下降自序列的和，則N次枚舉后得到N個(gè)合唱隊(duì)形的長(zhǎng)度，取其中的最大值，然后用學(xué)生總數(shù)n減去該最大值即可得到原問(wèn)題的解。例3-3：已知8個(gè)學(xué)生的身高：176、163、150、180、170、130、167、160，計(jì)算他們所組成的最長(zhǎng)合唱隊(duì)形的長(zhǎng)度。

Chapter33.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

計(jì)算最優(yōu)值

4.計(jì)算最優(yōu)值先從左到右求最大上升子序列的長(zhǎng)度，通過(guò)比較8個(gè)同學(xué)的身高，得到f1表如3-3（a）所示,然后從右到左求最大下降子序列的長(zhǎng)度,通過(guò)比較8個(gè)同學(xué)的身高，得到f2如表3-3（b）所示，最后將兩個(gè)表中對(duì)應(yīng)的元素相加減1（兩表中的值相加，第i位同學(xué)被重復(fù)計(jì)算了一次），得到最終問(wèn)題的解表如3-3（c）所示：

表3-3合唱隊(duì)形問(wèn)題動(dòng)態(tài)規(guī)劃表(a)最大上升子序列的長(zhǎng)度表f1

(b)最大下降子序列的長(zhǎng)度表f2

Chapter3i=1i=2i=3i=4i=5i=6i=7i=8f1[i]11122122i=1i=2i=3i=4i=5i=6i=7i=8f2[i]432431213.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

程序描述及算法分析Chapter35.程序描述及算法分析(c)最終結(jié)果表ans由此可見(jiàn)，當(dāng)i取4，即以身高為180的同學(xué)為中心位置，所形成的合唱隊(duì)形的長(zhǎng)度最長(zhǎng)為5，需要8-5=3個(gè)人出列，最終形成的合唱隊(duì)形為：176,180,170,167,160?！舅惴?.3用動(dòng)態(tài)規(guī)劃求解合唱隊(duì)形問(wèn)題】{/*功能：從n個(gè)同學(xué)中取出k個(gè)，求他們所組成的合唱隊(duì)形輸入：隊(duì)員人數(shù)n和每個(gè)學(xué)生身高a[i]輸出：最長(zhǎng)的合唱隊(duì)形的長(zhǎng)度ans*/

i=1i=2i=3i=4i=5i=6i=7i=8ans432541323.2線性動(dòng)態(tài)規(guī)劃-----合唱隊(duì)形問(wèn)題

程序描述及算法分析int*ans

ChorusRank(intn,inta[100]){for(inti=1;i<=n;i++){intf1[maxn];intf2[maxn];f1[i]=1;for(intj=1;j<i;j++)if(a[j]<a[i]&&f1[i]<f1[j]+1)f1[i]=f1[j]+1;//從左到右求最大上升子序列

}for(inti=n;i>=1;i--){f2[i]=1;for(intj=i+1;j<=n;j++)if(a[j]<a[i]&&f2[i]<f2[j]+1)f2[i]=f2[j]+1;//從右到左求最大下降子序列}

int

ans=0;for(inti=1;i<=n;i++)if(ans<f1[i]+f2[i]-1)

ans=f1[i]+f2[i]-1;//枚舉中間最高值returnans;//返回最長(zhǎng)合唱隊(duì)形的長(zhǎng)度}Chapter3算法分析

由于解決該問(wèn)題時(shí)使用了兩次動(dòng)態(tài)規(guī)劃方法來(lái)求解，即第一次求最大上升子序列的長(zhǎng)度，第二次求最大下降子序列的長(zhǎng)度，再枚舉中間最高的一個(gè)人所在隊(duì)形的長(zhǎng)度。算法實(shí)現(xiàn)所需的時(shí)間復(fù)雜度O(n2)，空間復(fù)雜度為O(n)。3.3區(qū)域動(dòng)態(tài)規(guī)劃-----矩陣連乘問(wèn)題

Chapter3本節(jié)內(nèi)容1.問(wèn)題描述2.窮舉法解決3.動(dòng)態(tài)規(guī)劃法解決

3.1分析最優(yōu)子結(jié)構(gòu)3.2建立遞歸關(guān)系3.3計(jì)算最優(yōu)值3.4程序描述及算法分析4.類似問(wèn)題的解決——凸多邊形的最優(yōu)三角剖分3.3

區(qū)域動(dòng)態(tài)規(guī)劃

——矩陣連乘問(wèn)題（最佳次序）

Chapter3

可用區(qū)域動(dòng)態(tài)規(guī)劃法解決的問(wèn)題的特點(diǎn)是：對(duì)整個(gè)問(wèn)題設(shè)置最優(yōu)值，枚舉剖分（合并）點(diǎn)，將問(wèn)題分解為左右兩部分，合并兩部分的最優(yōu)值得到原問(wèn)題的最優(yōu)值。如求從i到j(luò)的最優(yōu)值，枚舉剖分(合并)點(diǎn)，將（i，j）分成左右兩個(gè)區(qū)間，分別求左右兩邊的最優(yōu)值，如下圖：圖3-2圖圖圖3-2區(qū)域動(dòng)態(tài)規(guī)劃示意圖遞歸方程一般為：其中k為劃分點(diǎn)。3.3

矩陣連乘問(wèn)題（最佳次序）

------問(wèn)題描述

Chapter3

對(duì)于任意兩個(gè)矩陣，

它們相乘得到矩陣，即

。由于計(jì)算

的標(biāo)準(zhǔn)算法中，主要計(jì)算量在三重循環(huán)，具體值為

。當(dāng)計(jì)算三個(gè)矩陣的連乘積

，假設(shè)

是個(gè)

的矩陣，

是個(gè)

的矩陣，

是個(gè)

的矩陣，可知：

由此可見(jiàn)，通過(guò)為矩陣乘法加括號(hào)，不同的計(jì)算次序所產(chǎn)生的計(jì)算量是不同的，因此應(yīng)該從不同計(jì)算量中找出最少計(jì)算量，從而確定最優(yōu)計(jì)算次序，即尋找矩陣連乘問(wèn)題的最優(yōu)完全加括號(hào)方式。1.問(wèn)題描述3.3.1

矩陣連乘問(wèn)題

-----窮舉法解決2. 解決方法一【窮舉法】 列出矩陣連乘問(wèn)題的所有計(jì)算次序，設(shè)P(n)為n個(gè)矩陣連乘積可能的運(yùn)算順序的數(shù)目，則有如下遞推關(guān)系：Chapter3解此遞歸方程可得，P(n)實(shí)際上是Catalan數(shù)，即：

由此可見(jiàn)，窮舉法的時(shí)間復(fù)雜度為n的指數(shù)函數(shù)。3.3矩陣連乘問(wèn)題

-----窮舉法解決Chapter3例3-3：求四個(gè)矩陣連乘的組合數(shù)目。由此說(shuō)明3個(gè)矩陣連乘有2種組合，即與。而4個(gè)矩陣連乘有5種組合：、Chapter3

解決方法二【動(dòng)態(tài)規(guī)劃法】

1、分析最優(yōu)子結(jié)構(gòu)以四個(gè)矩陣連乘最優(yōu)順序?yàn)槔毫谐錾鲜鏊械?種不同的乘積結(jié)合次序。矩陣連乘問(wèn)題就是從這5種方式中找出乘法次數(shù)最少的連乘方式，即找到一個(gè)最優(yōu)的計(jì)算次序。當(dāng)矩陣個(gè)數(shù)增加到n個(gè)，計(jì)算這n個(gè)矩陣的連乘積，簡(jiǎn)寫為M[1:n]。3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

分析最優(yōu)子結(jié)構(gòu)

當(dāng)在計(jì)算M[1:n]的一個(gè)最優(yōu)計(jì)算次序時(shí)，設(shè)這個(gè)最優(yōu)計(jì)算次序在矩陣和之間將矩陣鏈斷開(kāi)，則完全加括號(hào)方式為，最終的結(jié)果M[1:n]的最優(yōu)計(jì)算次序取決于M[1:k]和M[k+1:n]的最優(yōu)計(jì)算次序。即矩陣連乘問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解，具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，同時(shí)這一性質(zhì)是這類問(wèn)題可以用動(dòng)態(tài)規(guī)劃算法解決的前提。Chapter32、建立遞歸關(guān)系設(shè)n個(gè)矩陣連乘，的行列數(shù)分別為，，設(shè)是計(jì)算的最小值，滿足最優(yōu)性，則有：3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

建立遞歸關(guān)系其中：是計(jì)算的最小耗費(fèi)；是計(jì)算的最小耗費(fèi)；和分別是矩陣的行數(shù)和列數(shù)，和分別是矩陣的行數(shù)和列數(shù)。給出了計(jì)算M[i:j]所需的最小數(shù)乘次數(shù)，同時(shí)還確定了計(jì)算M[i:j]的最優(yōu)次序時(shí)的最佳斷開(kāi)位置k。由于有三個(gè)變量i,j,k的三重循環(huán)，所示時(shí)間復(fù)雜度為：，比窮舉法所需的時(shí)間少。Chapter33.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

建立遞歸關(guān)系

解：Chapter3例3-4：計(jì)算矩陣連乘的最優(yōu)組合。有4個(gè)矩陣如下，3、計(jì)算最優(yōu)值例3-4：計(jì)算矩陣連乘的最優(yōu)組合。有4個(gè)矩陣如下，3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

計(jì)算最優(yōu)值Chapter3

由此可知，這四個(gè)矩陣連乘所用到的最小乘積次數(shù)是2200，最優(yōu)計(jì)算次序是。3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

計(jì)算最優(yōu)值在整個(gè)計(jì)算過(guò)程中可以填寫一下表格：

表3-4矩陣連乘問(wèn)題的遞推二維表Chapter3

4、程序描述及算法分析

要計(jì)算M[i:j]=M[i:k]*M[k+1:j]的值，首先輸入?yún)?shù){b0,b1,b2,...bn}存儲(chǔ)n個(gè)矩陣的階數(shù)下標(biāo)，并初始化M[i][i]=0，i=1,2,…,n。然后根據(jù)遞歸式，按矩陣鏈長(zhǎng)增長(zhǎng)的方式依次計(jì)算M[i][i+1]，i=1,2,…,n-13.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

程序描述及算法分析

陣鏈長(zhǎng)度為2)；M[i][i+2]，i=1,2,…,n-2(矩陣鏈長(zhǎng)度為3)；……，在計(jì)算M[i][j]時(shí)，只用到已計(jì)算出的M[i][k]和M[k+1][j]。具體如算法3.4所示。

算法3.4用動(dòng)態(tài)規(guī)劃求解矩陣連乘問(wèn)題

功能：找出n個(gè)矩陣的連乘積的一個(gè)所需數(shù)乘次數(shù)最少的連乘方式，即最優(yōu)的計(jì)算次序。Chapter3

3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

程序描述及算法分析輸入：n為連乘矩陣的個(gè)數(shù);{b0,b1,b2,...bn}存儲(chǔ)n個(gè)矩陣的階數(shù)下標(biāo)的數(shù)組；M[i][j]是計(jì)算的最小值；t[i][j]是連乘時(shí)的最佳斷開(kāi)位置。Chapter3voidMultiplyMatrix(int*b,intn,int**M,int**t){

//初始化

for(intk=1;k<=n;k++)

for(intj=1;j<=n;j++){

M[k][j]=0;

t[k][j]=0;}

for(intr=2;r<=n;r++)//r控制矩陣鏈長(zhǎng)度

for(inti=1;i<=n-r+1;i++){

輸出：最小計(jì)算次數(shù)矩陣M、最佳斷開(kāi)位置矩陣t。

3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

程序描述及算法分析Chapter3

intj=i+r-1;

M[i][j]=M[i+1][j]+b[i-1]*b[i]*b[j];

t[i][j]=i;//最佳斷開(kāi)位置為i

for(intk=i+1;k<j;k++)//改變k,即改變斷開(kāi)位置{

intl=M[i][k]+M[k+1][j]+b[i-1]*b[k]*b[j];

if(l<M[i][j]){

M[i][j]=l;

t[i][j]=k;//將矩陣斷開(kāi)的最佳位置存入數(shù)組t中}}}}

3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

程序描述及算法分析Chapter3

算法的主要計(jì)算量取決于程序中對(duì)r，i和k的三重循環(huán)，循環(huán)體內(nèi)的計(jì)算量為，容易得出其時(shí)間復(fù)雜度為。算法所占用的空間顯然為。3.3矩陣連乘問(wèn)題-----動(dòng)態(tài)規(guī)劃法解決

程序描述及算法分析3.3

區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

問(wèn)題描述

連接一個(gè)多邊形邊界上或其內(nèi)部的任意兩點(diǎn)，若該連線上的所有的點(diǎn)都在多邊形內(nèi)部或邊界上，則該多邊形為凸多邊形。通常，可以用多邊形頂點(diǎn)的逆時(shí)針序列來(lái)表示它，即表示有條邊的一個(gè)凸多邊形，其中約定。對(duì)平面上的一個(gè)凸多邊形進(jìn)行三角剖分，即通過(guò)多邊形的若干條不相交的弦將多邊形分割成互不重疊的若干個(gè)三角形，如圖3-2所示。Chapter3

圖3-2凸多邊形的兩個(gè)不同三角剖分1.問(wèn)題描述3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

問(wèn)題描述

凸多邊形最優(yōu)三角剖分問(wèn)題描述：給定一個(gè)凸多邊形，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)。要求確定該凸多邊形的一個(gè)三角剖分，使得該三角剖分對(duì)應(yīng)的權(quán)即剖分中諸三角形上的權(quán)之和為最小。三角形的權(quán)函數(shù)的定義方式很多，如：定義，其中，是點(diǎn)到點(diǎn)的歐氏距離，對(duì)應(yīng)于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長(zhǎng)三角剖分。Chapter3

凸多邊形的三角剖分與矩陣連乘積的最優(yōu)計(jì)算次序問(wèn)題之間具有十分緊密的聯(lián)系，這些問(wèn)題之間的相關(guān)性可從它們所對(duì)應(yīng)的完全二叉樹的同構(gòu)性得到。1.問(wèn)題描述3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題

Chapter3

2.三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題三角剖分問(wèn)題和矩陣連乘問(wèn)題（表達(dá)式的完全加括號(hào)問(wèn)題）都可以表述成一個(gè)完全二叉樹（不含度為1的結(jié)點(diǎn)的二叉樹）,如圖3-3所示：圖3-3表達(dá)式語(yǔ)法樹與三角剖分的對(duì)應(yīng)3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題

Chapter3

一個(gè)表達(dá)式的完全加括號(hào)方式相應(yīng)于一棵完全二叉樹，稱為表達(dá)式的語(yǔ)法樹。例如，完全加括號(hào)的矩陣連乘積所相應(yīng)的語(yǔ)法樹如圖3-3(a)所示。這里有n=6個(gè)矩陣連乘，其中的每個(gè)矩陣對(duì)應(yīng)于凸(n+1)邊形中的一條邊上的結(jié)點(diǎn)。

凸多邊形的三角剖分也可以用語(yǔ)法樹表示。例如，圖3-3(b)中凸多邊形的三角剖分，與圖3-3(a)很類似。(b)圖語(yǔ)法樹的根結(jié)點(diǎn)為邊上的圓形結(jié)點(diǎn)，且該語(yǔ)法樹的其他內(nèi)部結(jié)點(diǎn)都是用小圓形表示的，并被放置在新增剖分虛線上，(b)圖語(yǔ)法樹的葉子結(jié)點(diǎn)使用小方塊表示，被放置在剖分前凸多邊形的各條邊上。多邊形中3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

三角剖分的結(jié)構(gòu)及其相關(guān)問(wèn)題

除邊外的每一條邊是語(yǔ)法樹的一個(gè)葉結(jié)點(diǎn)。樹根是三角形的一條邊，該三角形將原多邊形分為三角形,凸多邊形和凸多邊形三個(gè)部分。三角形的另外兩條邊，即弦和為根的兩個(gè)兒子。以它們?yōu)楦淖訕浞謩e表示凸多邊形和凸多邊形的三角剖分。Chapter3

矩陣連乘積中的每個(gè)矩陣對(duì)應(yīng)于凸(n+1)邊形中的一條邊。三角剖分中的一條弦，對(duì)應(yīng)于矩陣連乘積。由此可見(jiàn)，n個(gè)矩陣的完全加括號(hào)乘積與凸(n+1)邊形的三角剖分之間存在著一一對(duì)應(yīng)的關(guān)系。3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

最優(yōu)子結(jié)構(gòu)性質(zhì)

3.最優(yōu)子結(jié)構(gòu)性質(zhì)

凸多邊形的最優(yōu)三角剖分問(wèn)題有最優(yōu)子結(jié)構(gòu)性質(zhì)。證明：（反證法）事實(shí)上，若凸(n+1)邊形的最優(yōu)三角剖分T包含三角形，，則T的權(quán)為三角形的權(quán)、子多邊形和三個(gè)部分權(quán)之和。另外可以斷定由T所確定的這兩個(gè)子多邊形的三角剖分也是最優(yōu)的。因?yàn)槿粲谢虻母?quán)的三角剖分將導(dǎo)致T不是最優(yōu)三角剖分的矛盾。Chapter3

3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

遞歸結(jié)構(gòu)Chapter3

定義,為凸子多邊形的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見(jiàn)，設(shè)退化的多邊形具有權(quán)值0。據(jù)此定義，要計(jì)算的凸(n+1)邊形T的最優(yōu)權(quán)值為

。

的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計(jì)算。當(dāng)j-i≥1時(shí)，凸子多邊形至少有3個(gè)頂點(diǎn)。由最優(yōu)子結(jié)構(gòu)性質(zhì)，的值應(yīng)為的值加上的值，再加上三角形的權(quán)值，其中i≤k≤j-1。由于在計(jì)算時(shí)還不知道k的確切位置，而k的所有可能位置只有j-i個(gè)，因此可以在這j-i個(gè)位置中選出使值達(dá)到最小的位置。由此，可遞歸地定義為：4.最優(yōu)三角剖分的遞歸結(jié)構(gòu)3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計(jì)算最優(yōu)值

可見(jiàn)除了權(quán)函數(shù)的定義外，與矩陣連乘的遞歸式完全相同。因此只要對(duì)計(jì)算的算法做很小的修改就完全適用于計(jì)算。Chapter35.計(jì)算最優(yōu)值及構(gòu)造最優(yōu)三角剖分算法3.5用動(dòng)態(tài)規(guī)劃求解凸多邊形最優(yōu)三角剖分問(wèn)題功能：將一個(gè)凸多邊形進(jìn)行最優(yōu)三角剖分。輸入：凸多邊形頂點(diǎn)個(gè)數(shù)m，各個(gè)頂點(diǎn)的坐標(biāo)。

3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計(jì)算最優(yōu)值

輸出：記錄最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值的矩陣t、記錄最優(yōu)三角剖分中所有三角形信息的矩陣s和凸(n+1)邊形的最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)值。Chapter3bool

CTriangle::MinWeightTriangulation(){ //計(jì)算最優(yōu)值 //初始化

for(inti=1;i<=n;i++) {

for(intj=1;j<=n;j++)

{

t[i][j]=0;

s[i][j]=0;

} }

3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計(jì)算最優(yōu)值

Chapter3for(intr=2;r<=n;r++)

for(inti=1;i<=n-r+1;i++) {

intj=i+r-1;

t[i][j]=t[i+1][j]+w(v[i-1],v[i],v[j]);

s[i][j]=i;//最佳剖分點(diǎn)為i

for(intk=i+1;k<i+r-1;k++)

{

intu=t[i][k]+t[k+1][j]+w(v[i-1],v[k],v[j]);//改變k，即改變

剖分點(diǎn)

if(u<t[i][j])

{

t[i][j]=u;

s[i][j]=k;//將凸多邊形的最佳剖分點(diǎn)存入數(shù)組s中

}

3.3區(qū)域動(dòng)態(tài)規(guī)劃—凸多邊形最優(yōu)三角剖分

計(jì)算最優(yōu)值Chapter3

與算法MultiplyMatrix一樣，算法MinWeightTriangulation占用空間，耗時(shí)。

}

}

returntrue;}3.4背包動(dòng)態(tài)規(guī)劃-----0-1背包問(wèn)題

Chapter3本節(jié)內(nèi)容1.問(wèn)題分類2.分析最優(yōu)子結(jié)構(gòu)3.建立遞歸關(guān)系4.計(jì)算最優(yōu)值5.程序描述及算法分析Chapter33.4背包動(dòng)態(tài)規(guī)劃-----0-1背包問(wèn)題

問(wèn)題分類1.背包動(dòng)態(tài)規(guī)劃問(wèn)題的分類<1>0-1背包問(wèn)題：這是最基本的背包問(wèn)題，特點(diǎn)是：每種物品只有一件，可以選擇放與不放。當(dāng)用子問(wèn)題定義狀態(tài)時(shí)，若f[i][v]表示前i件物品放入一個(gè)容量恰為v的背包中獲得的價(jià)值最大?？梢缘玫竭f歸方程為：f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+a[i]}(其中a[i]和w[i]分別為每個(gè)物體的價(jià)值和重量)最后要求f[n][v]的值，因?yàn)槿萘壳関。其他類型的背包問(wèn)題往往也是有0-1背包問(wèn)題轉(zhuǎn)化而來(lái)的。例如采藥、BuyLow，BuyLower、排隊(duì)買票問(wèn)題等。53<2>完全背包問(wèn)題：與0-1背包問(wèn)題類似，所不同的是每件物品有無(wú)限件。遞歸方程為：f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k*v[i]<=j)},在這類問(wèn)題中，如果當(dāng)前物品與其它物品相比價(jià)值低，體積大，就可以將其舍棄，這樣可以大大減少物品數(shù)。與此同類的問(wèn)題還有：總分、砝碼稱重、無(wú)限硬幣問(wèn)題等。<3>多重背包問(wèn)題：

與完全背包類似，所不同的是第i種物品可以使用s[i]次，遞歸方程：f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k<=s[i]&&k*v[i]<=j)},類似的問(wèn)題如郵票問(wèn)題。Chapter33.4背包動(dòng)態(tài)規(guī)劃—0-1背包問(wèn)題

問(wèn)題分類54<4>混合三種背包的問(wèn)題：

即有的物品只能使用一次，有的可以使用規(guī)定的次數(shù)，有的可以使用無(wú)限次。其實(shí)，只需加幾個(gè)判斷條件就可以了?？傮w的解決框架如下所示：

for(i=1;i<=n;i++)

for(j=1;j<=V;j++){if是0-1背包問(wèn)題

f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+a[i]}if是完全背包問(wèn)題

f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k*w[i]<=j)}if是多重背包問(wèn)題

f[i][j]=max{f[i-1][j-k*w[i]]+k*a[i](k<=s[i]&&k*w[i]<=j)}

}Chapter33.4背包動(dòng)態(tài)規(guī)劃—0-1背包問(wèn)題

問(wèn)題分類550-1背包動(dòng)態(tài)規(guī)劃問(wèn)題

現(xiàn)有n件物品，一個(gè)容量為c的背包。第i件物品重量為wi,價(jià)值為vi。已知對(duì)于一件物品必須選擇取或不取，且每件物品只能被取一次（這就是“0-1”的含義）。求放置那幾件物品進(jìn)背包，使得背包中物品價(jià)值最大？

此問(wèn)題可形式化表示為求解：物品價(jià)值：物品重量：

Chapter33.4

0-1背包問(wèn)題描述

-----問(wèn)題描述562.分析最優(yōu)子結(jié)構(gòu)

設(shè)（y1y2,…,yn）是所給0-1背包問(wèn)題的一個(gè)最優(yōu)解，則（y2,…,yn）是下面一個(gè)子問(wèn)題的最優(yōu)解：

如若不然，設(shè)（Z2,…,Zn)是上述子問(wèn)題的一個(gè)最優(yōu)解，則因此，這說(shuō)明（y1,Z2,…,Zn）是所給0-1背包問(wèn)題比（y1,y2,…,yn）更優(yōu)的解，從而導(dǎo)致矛盾。

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.40-1背包問(wèn)題描述

-----分析最優(yōu)子結(jié)構(gòu)

57

如果第i個(gè)物品的重量大于背包的容量，則不裝入物品i，計(jì)算從i到n的n-i+1個(gè)物品得到的最大值和計(jì)算i+1到n的n-i個(gè)物品得到的最大價(jià)值是相同的，即：m(i,j)=m(i+1,j)0≤j≤wi如果第i個(gè)物品的重量小于背包的容量，則會(huì)出現(xiàn)以下兩種情況：（1）若把第i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把后i+1個(gè)物品裝入容量為j-wi的背包中的價(jià)值再加上第i個(gè)物品的價(jià)值vi。（2）若第i個(gè)物品沒(méi)有裝入背包，則背包中物品的價(jià)值等于把后i+1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。顯然，應(yīng)兩者中值較大者作為把后i個(gè)物品裝入容量為j的背包總的最優(yōu)解，如下是所示：m(i,j)=max(m(i+1,j),m(i+1,j-wi)+vi)，j≥wi

3.建立遞歸關(guān)系

設(shè)所給0-1背包問(wèn)題的子問(wèn)題：0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.40-1背包問(wèn)題描述

-----建立遞歸關(guān)系58

下面通過(guò)實(shí)例對(duì)0-1背包的遞歸時(shí)進(jìn)行具體研究：例如，有5個(gè)物品，起重量分別是{2,2,6,5,4}，價(jià)值分別為{6,3,5,4,6}，背包的容量為10。要求如何是背包的容量最大？根據(jù)上面研究的遞歸式可以迅速建立一張二維表V，其建立結(jié)果如表3.5所示：

m（i，j）＝m(i+1,j)當(dāng)wi>j（不夠裝不裝）maxm(i+1,j)夠裝但不裝(性價(jià)比低)m(i+1,j-wi)+vi夠裝而且裝

最終建立如下計(jì)算m(i,j)的遞歸式如下：

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.40-1背包問(wèn)題描述

-----建立遞歸關(guān)系59

表3-10-1背包問(wèn)題的遞歸二維表

通過(guò)這張二維表，可以發(fā)現(xiàn)在背包裝到容量為8的時(shí)候，背包的價(jià)值是最大的。但是如何通過(guò)這張二維表確定那幾件物品被裝入背包？

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.40-1背包問(wèn)題描述

-----建立遞歸關(guān)系60

表3-10-1背包問(wèn)題的遞歸二維表

這里可以從m(n，c)的值向前推，如果m(n，c)>m(n-1，c),表明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-Wn的背包中；否則，第n個(gè)物品沒(méi)有被裝入背包，前n-1個(gè)物品被裝入容量為c的背包中。以此類推，直到確定第n個(gè)物品是否被裝入背包中為止。由此，得如下函數(shù)：

所以，上述0-1背包裝載序列是：當(dāng)背包所裝容量為8時(shí)，背包價(jià)值最大15。0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.40-1背包問(wèn)題描述

-----建立遞歸關(guān)系61

4.程序描述及算法分析

當(dāng)物體的重量為正數(shù)時(shí)，用二維數(shù)組來(lái)存儲(chǔ)嗎（i,j）的相應(yīng)，可以設(shè)計(jì)解0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法Beibao如算法3.5.【算法3.5用動(dòng)態(tài)規(guī)劃求0-1背包問(wèn)題】/*功能：找出裝入容量為c的背包中的，有最大價(jià)值的物品輸入：n是背包的物品種類

c是背包的容量

v數(shù)組是每個(gè)物品的價(jià)值w數(shù)組是每個(gè)物品的重量m數(shù)組是0-1背包的最優(yōu)質(zhì)輸出：背包的最大價(jià)值和以0-1方式顯示的裝入的物品*/0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----程序描述及算法分析

62

VoidBeibao(int

v,intw,intc,intn,int**m){

int

jmax=min(w[n]-1,c);

for(intj=0;j<=jmax;j++)

m[n][j]=0;//初始化數(shù)組mfor(intj=w[n];j<=c;j++)

m[n][j]=v[n];

for(inti=n-1;i>1;i--){jmax=min(w[i]-1,c);

for(intj=0;j<jmax;j++)

m[i][j]=m[i+1][j];

for(intj=w[i];j<=c;j++)

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+V[i]);//比較選擇當(dāng)前物品與沒(méi)有選擇當(dāng)前物品時(shí)背包所獲得的最大值}0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----程序描述及算法分析

m[1][c]=m[2][c];if(c>w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}Voidtaceback(int**m,int

w,int

c,int

n,intx){for(inti=1;i<n;i++)

if(m[i][c]==m[i+1][c])//表示序號(hào)為i的物品沒(méi)有被裝入背包

x[i]=0;else{x[i]=1;//表示序號(hào)為i的物品被裝入背包c(diǎn)-=w[i];}X[n]=(m[n][c])?1:0;}

從計(jì)算m(i,j)的遞歸公式容易看出，上述算法beibao的關(guān)鍵是二維表m(i,j)的建立，所以該算法的時(shí)間復(fù)雜度為O(n*c),而Traceback中有一個(gè)for循環(huán)，該算法的時(shí)間復(fù)雜度為O（n）。63

5.改進(jìn)的背包算法通過(guò)與現(xiàn)實(shí)生活相聯(lián)系發(fā)現(xiàn)，上述算法是極其特殊的情形，其中有兩個(gè)比較明顯的缺點(diǎn)。其一是算法要求所給背包重量C和物品重量Wi是整數(shù)，這在現(xiàn)實(shí)生活中基本上實(shí)行不通的。其次，當(dāng)背包容量很大時(shí)，算法需要計(jì)算的時(shí)間很多。例如當(dāng)c>時(shí)，算法的時(shí)間復(fù)雜度為O（n*),這個(gè)指數(shù)級(jí)得時(shí)間對(duì)于計(jì)算機(jī)來(lái)說(shuō)是一個(gè)很大的耗費(fèi)。由計(jì)算m(i,j)的遞歸式繪制當(dāng)i=1是的函數(shù)圖象，如下圖示：0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

64

通過(guò)觀察發(fā)現(xiàn)在變量j是連續(xù)的情況下，可以對(duì)每一個(gè)確定的i，用一個(gè)表p[i]來(lái)存儲(chǔ)函數(shù)m(i,j)的全部跳躍點(diǎn)。對(duì)每一個(gè)確定的實(shí)數(shù)j，可以通過(guò)查表p[i]來(lái)確定函數(shù)m(i,j)的值。p[i]中全部跳躍點(diǎn)（j,m(i,j))依j的值升序排列。由于函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)，故p[i]中全部跳躍點(diǎn)的m(i,j)值也是遞增排列的。所以可以記錄每一個(gè)i值的跳躍點(diǎn)，最后通過(guò)查找得出最優(yōu)解和裝載序列。下面構(gòu)造不同i值的跳躍點(diǎn)，在構(gòu)造之前需要明確下面量的含義：

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

65

（1）函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-Wi)+Vi做max運(yùn)算得到的。因此，函數(shù)m(i,j)的跳躍點(diǎn)p[i]包含于函數(shù)m(i+1,j)的跳躍點(diǎn)p[i+1]與函數(shù)m(i+1,j-Wi)+Vi的跳躍點(diǎn)集q[i+1]的并集中。其中q[i+1]=p[i+1]⊕(wi,vi)={j+wi,m(i,j)+vi|(j,m(i,j))∈p[i+1]}(其中“⊕”在這代表一個(gè)廣義的運(yùn)算符號(hào))（2）設(shè)(a,b)和(c,d)是p[i+1]和q[i+1]并集中的兩個(gè)跳躍點(diǎn)，則當(dāng)c>=a且d<b時(shí)，(c,d)受控于(a,b),從而(c,d)不是p(i)中的跳躍點(diǎn)。0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

66

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題

在遞歸地由表p[i+1]計(jì)算表p[i]時(shí)，可先由p[i+1]計(jì)算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點(diǎn)得到表p[i]。如當(dāng)n=5,c=10,W={2,2,6,5,4},v={6,3,5,4,6}時(shí)，構(gòu)造跳躍點(diǎn)的過(guò)程如下：初始時(shí)p[6]={(0,0)},(W5,V5)=(4,6)。因此，q[6]=p[6]⊕(W5,V5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5]⊕(W4,V4)={(5,4),(9,10)}。從跳躍點(diǎn)集p[5]與q[5]的并集p[5]Ｕq[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點(diǎn)(5,4)受控于跳躍點(diǎn)(4,6)。將受控跳躍點(diǎn)(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4]⊕(6,5)={(6,5),(10,11)}p[3]={(0,0),(4,6),(9,10),(10,11)}q[3]=p[3]⊕(2,3)={(2,3),(6,9)}0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

67

p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)}q[2]=p[2]⊕(2,6)={(2,6),(4,9),(6,12),(8,15)}p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)}p[1]的最后的那個(gè)跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。改進(jìn)后的算法代碼如算法3.6?！舅惴?.6改進(jìn)的用動(dòng)態(tài)規(guī)劃求0-1背包問(wèn)題】/*功能：找出裝入容量為c的背包中的，有最大價(jià)值的物品輸入：n是背包的物品種類C是背包的容量v數(shù)組是每個(gè)物體的價(jià)值w數(shù)組是每個(gè)物體的重量p數(shù)組為存放的跳躍點(diǎn)x是以0-1方式顯示的最優(yōu)值輸出：背包的最大價(jià)值和裝入的物品求最優(yōu)值時(shí)的跳躍點(diǎn)*/0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

68

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題intBeibao(intn,floatc,floatv[],floatw[],floatp[][2],intx[]){int*head=newint[n+2]head[n+1]=0;p[0][0]=0;p[0][1]=0;intleft=0,right=0,next=0;head[n]=1;for(inti=n;i>=1;i--){intk=left;for(intj=left;j<=right;j++){if(p[j][0]+w[i]>c)break;floaty=p[j][0]+w[i],m=p[j][1]+v[i];

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

while(k<=right&&p[k][0]<y){p[next][0]=p[k][0];p[next++][1]=p[k++][1];}if(k<=right&&p[k][0]==y){if(m<p[k][1])m=p[k][1];k++;}if(m>p[next-1][1]){p[next][0]=y;p[next++][1]=m;}69

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題while(k<=right&&p[k][1]<=p[next-1][1])k++;}while(k<=right){p[next][0]=p[k][0];p[next++][1]=p[k++][1];}left=right+1;right=next-1;head[i-1]=next;}traceback(n,w,v,p,head,x);cout<<“跳躍點(diǎn)是：”<<endl;intj=n;for(i=0;i<next;i++){cout<<"（"<<p[i][0]<<","<<p[i][1]<<"）";

0-1背包動(dòng)態(tài)規(guī)劃問(wèn)題Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

if(i==(head[j]-1)){cout<<endl;j--;}}returnp[next-2][1]+3;}voidtraceback(intn,floatw[],floatv[],floatp[][2],int*head,intx[]){floatj=p[head[0]-1][0];floatm=p[head[0]-1][1];for(inti=1;i<=n;i++){

x[i]=0;

for(intk=head[i+1];k<=head[i]-1;k++){if(p[k][0]+w[i]==j&&p[k][1]+v[i]==m)

x[i]=1;j=p[k][0];m=p[k][1];break;}}}}70

上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集p[i](1≤i≤n)。由于q[i+1]=p[i+1]⊕(wi，vi)，故計(jì)算q[i+1]需要O(|p[i+1]|)計(jì)算時(shí)間。合并p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要O(|p[i+1]|)計(jì)算時(shí)間。從跳躍點(diǎn)集p[i]的定義可以看出，p[i]中的跳躍點(diǎn)相應(yīng)于xi,…,xn的0/1賦值。因此，p[i]中跳躍點(diǎn)個(gè)數(shù)不超過(guò)。由此可見(jiàn)，算法計(jì)算跳躍點(diǎn)集p[i](1≤i≤n)所花費(fèi)的計(jì)算時(shí)間為Chapter33.4.0-1背包問(wèn)題描述

-----改進(jìn)的背包算法

從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O()。當(dāng)所給物品的重量wi(1≤i≤n)是整數(shù)時(shí)，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(min{nc,})。3.5樹形動(dòng)態(tài)規(guī)劃

------最優(yōu)二叉搜索樹Chapter3本節(jié)內(nèi)容1.問(wèn)題描述2.窮舉法解決3.動(dòng)態(tài)規(guī)劃法解決

3.1分析最優(yōu)子結(jié)構(gòu)3.2遞歸計(jì)算最優(yōu)值3.3程序描述及算法分析3.4構(gòu)造最優(yōu)值3.5改進(jìn)的算法3.5樹形動(dòng)態(tài)規(guī)劃------最優(yōu)二叉搜索樹

問(wèn)題描述

1.問(wèn)題描述

樹形動(dòng)態(tài)規(guī)劃是建立在樹結(jié)構(gòu)的基礎(chǔ)上的，當(dāng)動(dòng)態(tài)規(guī)劃的各階段形成一棵樹，利用各階段之間的關(guān)系（遞歸方程），從根傳遞有用信息給葉子節(jié)點(diǎn)，從而得到最優(yōu)解或者從葉節(jié)點(diǎn)（邊界）開(kāi)始逐步向上一層的節(jié)點(diǎn)（即父節(jié)點(diǎn)）進(jìn)行動(dòng)態(tài)規(guī)劃，直到動(dòng)規(guī)到根節(jié)點(diǎn)，（即原問(wèn)題），求的問(wèn)題的最優(yōu)解，下面我們就舉例說(shuō)明：Chapter3二叉搜索樹是一顆滿足如下條件的二叉樹：（1）若它的左子樹非空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；（2）若它的右子樹非空，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；（3）它的左、右子樹也分別為二叉搜索樹。0.1*1+0.2*2+0.4*3+0.3*4=2.90.1*2+0.2*1+0.4*3+0.3*2=2.20.1*2+0.2*1+0.4*2+0.3*3=2.10.1*3+0.2*4+0.4*2+0.3*1=2.2鍵的平均比較次數(shù)：

設(shè)二叉樹有n個(gè)帶權(quán)值的結(jié)點(diǎn)，則從根結(jié)點(diǎn)到各個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的積之和叫二叉搜索樹的帶權(quán)路徑長(zhǎng)度，給定一組有確定權(quán)值的結(jié)點(diǎn)，可以構(gòu)造出不同形態(tài)的帶權(quán)二叉樹.如概率分別為0.1，0.2，0.4，0.3。鍵值為3，7，9，12的二叉查找樹為：3Chapter3.5樹形動(dòng)態(tài)規(guī)劃------最優(yōu)二叉搜索樹

問(wèn)題描述3.5樹形動(dòng)態(tài)規(guī)劃------最優(yōu)二叉搜索樹

問(wèn)題描述Chapter3設(shè)S={x1,x2,...,xn}是一個(gè)有序集，且x1<x