計(jì)算理論與算法分析設(shè)計(jì)課件：動(dòng)態(tài)規(guī)劃法

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

2024/7/52of158方法概述:發(fā)展及研究?jī)?nèi)容動(dòng)態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過(guò)程(multistepdecisionprocess)的優(yōu)化問(wèn)題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，逐個(gè)求解，創(chuàng)立了解決這類(lèi)過(guò)程優(yōu)化問(wèn)題的新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃問(wèn)世以來(lái)，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線(xiàn)、資源分配、設(shè)備更新等問(wèn)題，用動(dòng)態(tài)規(guī)劃比用其它方法求解更為方便。2024/7/53of158方法概述:基本思想動(dòng)態(tài)規(guī)劃的思想實(shí)質(zhì)是分治思想和解決冗余。與分治法類(lèi)似的是，將原問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，經(jīng)分解的子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解，有些共同部分（子問(wèn)題或子子問(wèn)題）被重復(fù)計(jì)算了很多次。如果能夠保存已解決的子問(wèn)題的答案，在需要時(shí)再查找，這樣就可以避免重復(fù)計(jì)算、節(jié)省時(shí)間。動(dòng)態(tài)規(guī)劃法用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表方式。2024/7/54of158方法概述:求解步驟1、找出最優(yōu)解的性質(zhì)，并刻畫(huà)其結(jié)構(gòu)特征；2、遞歸地定義最優(yōu)值（寫(xiě)出動(dòng)態(tài)規(guī)劃方程）；3、以自底向上的方式計(jì)算出最優(yōu)值；4、根據(jù)計(jì)算最優(yōu)值時(shí)記錄的信息，構(gòu)造最優(yōu)解。注：－步驟1-3是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟4可以省略；－若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟4，步驟3中記錄的信息是構(gòu)造最優(yōu)解的基礎(chǔ)2024/7/55of158方法概述:適用條件

動(dòng)態(tài)規(guī)劃法的有效性依賴(lài)于問(wèn)題本身所具有的兩個(gè)重要性質(zhì)最優(yōu)子結(jié)構(gòu)：當(dāng)問(wèn)題的最優(yōu)解包含了其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(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è)表格中，在以后盡可能多地利用這些子問(wèn)題的解。2024/7/56of158方法概述:最優(yōu)性原理及舉例Bellman給出這個(gè)原理作為動(dòng)態(tài)規(guī)劃的適用條件，后來(lái)Morin在1982年證明了這只是一個(gè)充分條件而非必要條件。Bellman的原定義如下：

Anoptimalpolicyhasthepropertythatwhatevertheinitialstateandinitialdecisionare,thenremainingdecisionsmustconstituteanoptimalpolicywithregardtothestateresultingfromfirstdecision.

最優(yōu)性原理又稱(chēng)為最優(yōu)子結(jié)構(gòu)性質(zhì)：

如果有一決策序列包含有非最優(yōu)的決策子序列，則該決策序列一定不是最優(yōu)的。即一個(gè)最優(yōu)策略的子策略總是最優(yōu)的。2024/7/57of158例1：多段圖的最短路問(wèn)題多段圖：設(shè)G=<V,E>是一個(gè)有向連通圖，

其中|V|=n,|E|=m,V有劃分{V1,V2,···,Vk}，

這里V1={s},s稱(chēng)為源點(diǎn)，Vk={t},t稱(chēng)為

終點(diǎn)，其中k≥2。對(duì)于每條有向邊

<u,v>∈E都存在Vi

∈V，使得u∈Vi

和v∈Vi+1,其中1≤i<k且每條邊<u,v>均

附有代價(jià)C(u,v)，則稱(chēng)G是一個(gè)k段圖。2024/7/58of158123456789101112s97324212711118654356425V1V2V3V4V5t2024/7/59of158最短路：從源點(diǎn)s到終點(diǎn)t的整條路上的代價(jià)之和為最小。每個(gè)子集Vi構(gòu)成圖中的一段。由于E的約束，每條從s到t的路徑都是從第一段開(kāi)始，然后順次經(jīng)過(guò)第2段，第3段，···，最后在第k段終止。對(duì)于每條從s到t的路徑，可以把它看成在k-2個(gè)階段中做出的某個(gè)決策序列的相應(yīng)結(jié)果。2024/7/510of158假設(shè)s,v2,v3,···,vk-1,t是一條從s到t的最短路徑，還假定從源點(diǎn)s（初始狀態(tài)）開(kāi)始，已做出了到結(jié)點(diǎn)v2的決策（初始決策），因此v2就是初始決策所產(chǎn)生的狀態(tài)。如果把v2看成是原問(wèn)題的一個(gè)子問(wèn)題的初始狀態(tài)，解這個(gè)子問(wèn)題就是找出一條由v2到t的最短路徑。這條路徑顯然是v2,v3,···,vk-1,t，否則設(shè)v2,q3,···,qk-1,t是一條由v2到t的更短路徑，則s,v2,q3,···,qk-1,t是一條比路徑s,v2,v3,···,vk-1,t更短的由s到t的路徑，與假設(shè)矛盾，故最優(yōu)化原理成立。2024/7/511of158cost(i,j)=min{C(j,r)+cost(i+1,r)}

r∈Vi+1<j,r>∈EjrtViVi+1最短最短向前處理法：設(shè)P(i,j)是從Vi中的點(diǎn)j到t的一條最短路，cost(i,j)是這條路線(xiàn)的耗費(fèi)。由后向前推算，得到2024/7/512of158123456789101112s97324212711118654356425V1V2V3V4V5tcost(4,9)=4cost(i,j)=min{C(j,r)+cost(i+1,r)}

cost(4,10)=2cost(4,11)=5cost(3,6)=min{6+cost(4,9),5+cost(4,10)}=min{6+4,5+2}=7從第3段的頂點(diǎn)6到t的最短路徑是6-10-t5+22024/7/513of158123456789101112s97324212711118654356425V1V2V3V4V5tcost(3,7)=min{4+cost(4,9),3+cost(4,10)}=min{4+4,3+2}=5從第3段的頂點(diǎn)7到t的最短路徑是7-10-tcost(3,8)=7從第3段的頂點(diǎn)8到t的最短路徑是8-10-t2024/7/514of158123456789101112s97324212711118654356425V1V2V3V4V5tcost(2,2)=7從第2段頂點(diǎn)2到t的最短路是2-7-10-tcost(2,3)=9從第2段頂點(diǎn)3到t的最短路是3-6-10-tcost(2,4)=18從第2段頂點(diǎn)4到t的最短路是4-8-10-tcost(2,5)=15從第2段頂點(diǎn)5到t的最短路是5-8-10-tcost(1,1)=16從第1段頂點(diǎn)1到t的最短路徑由兩條：

1-2-7-10-t和1-3-6-10-t2024/7/515of158從s到t的一條最短路徑的代價(jià)為16。用D(i,j)表示使C(j,r)+cost(i+1,r)取得最小值

的r，則在上述求解過(guò)程中同時(shí)得到：D(3,6)=10,D(3,7)=10,D(3,8)=10D(2,2)=7,D(2,3)=6,D(2,4)=8D(2,5)=8,D(1,1)=2設(shè)從s到t的最短路徑為s,w2,w3,···,wk-1,t則有w2=D(1,1)=2w3=D(2,D(1,1))=D(2,2)=7w4=D(3,D(2,D(1,1)))=D(3,D(2,2))=D(3,7)=10所以這條路徑是1-2-7-10-t所以這條路徑是1-2-7-10-t2024/7/516of158為了便于描述算法，對(duì)一個(gè)k段圖的頂點(diǎn)，按段的順序給它的每個(gè)頂點(diǎn)編號(hào)。設(shè)圖中有n個(gè)頂點(diǎn)，則編號(hào)為1，2，···，n。首先，給s編為1號(hào)；然后給V2中的各個(gè)頂點(diǎn)分別編為2，3，···

，|V2|+1號(hào)；以此類(lèi)推，最后t編號(hào)為n。這樣編號(hào)使Vi+1中的任何頂點(diǎn)的編號(hào)大于Vi中所有頂點(diǎn)的編號(hào)。于是，可以按n-1,n-2,···,1的順序計(jì)算出cost(i,j)和D(i,j)。算法中可以利用順序編號(hào)的特點(diǎn)，而不再考慮頂點(diǎn)所在的段。2024/7/517of158設(shè)頂點(diǎn)的編號(hào)已知，邊已知及邊的代價(jià)函

數(shù)C(i,j)已知。用cost[i]表示頂點(diǎn)i到t的最小

代價(jià)，1≤i≤n。用D[i]表示從頂點(diǎn)i到t的最短路徑上頂點(diǎn)i的后繼頂點(diǎn)號(hào)，用P[i]表示最短路徑經(jīng)過(guò)第i級(jí)的頂點(diǎn)號(hào)，1≤i≤k2024/7/518of158求兩點(diǎn)間最短路徑的算法：ProcedureFgraph

1.{fori←1toncost[i]←0；

2.forj=n-1step–1to1do

{

3.找頂點(diǎn)r,使<j,r>∈E,且C(j,r)+cost[r]最?。?/p>

4.cost[j]←C(j,r)+cost[r];

5.D[j]←r;

}

6.P[1]←1;P[k]←n;

7.forj=2tok-1doP[j]←D[P[j-1]]

}O(n+|E|)2024/7/519of158123456789101112s97324212711118654356425V1V2V3V4V5t（從前）向后：設(shè)BPij是從源點(diǎn)s到Vi中頂點(diǎn)j的最小成本路徑，bcost(i,j)是這條路徑的代價(jià)bcost(i,j)=min{bcost(i-1,r)+C(r,j)}r∈Vi-1<r,j>∈E2024/7/520of158格路問(wèn)題：求從起點(diǎn)O(0,0)到終點(diǎn)E(m,n)的最短路。則分別用窮舉法和動(dòng)態(tài)規(guī)劃法的加法次數(shù)和比較次數(shù)各是多少？E(m,n)O(0,0)xy2024/7/521of158E(m,n)O(0,0)xy2024/7/522of158E(m,n)O(0,0)xymn個(gè)點(diǎn)2024/7/523of158例2：貨郎擔(dān)問(wèn)題1243105209128913156810∞1015205∞910613∞12889∞v1

v2v3v4v1v2v3v42024/7/524of158不失一般性，考慮以結(jié)點(diǎn)1為起點(diǎn)和終點(diǎn)的一條哈密頓回路。每一條這樣的路線(xiàn)都由一條邊<1,k>和一條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑組成，其中k∈V-{1},而這條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑通過(guò)V-{1，k}的每個(gè)結(jié)點(diǎn)各一次。如果這條周游路線(xiàn)是最優(yōu)的，則這條由結(jié)點(diǎn)k到結(jié)點(diǎn)1的路徑必定是通過(guò)V-{1，k}的每個(gè)結(jié)點(diǎn)各一次的由k到1的最短路徑。2024/7/525of158設(shè)T(i,S)是由結(jié)點(diǎn)i出發(fā)，經(jīng)過(guò)結(jié)點(diǎn)集S中每個(gè)結(jié)點(diǎn)各一次并回到初始結(jié)點(diǎn)1的一條最

短路徑長(zhǎng)度，則T(1,V-{1})就是一條最優(yōu)的周游路線(xiàn)長(zhǎng)度。動(dòng)態(tài)規(guī)劃模型：T(1,V-{1})=min{d1k+T(k,V-{1,k})}2≤k≤nT(i,s)=min{dij+T(j,S-{j})}j∈S,i?S2024/7/526of158∞1015205∞910613∞12889∞v1

v2v3v4v1v2v3v4T(1,{2,3,4})=min{d12+T(2,{3,4}),

d13+T(3,{2,4}),d14+T(4,{2,3})}T(2,{3,4})=min{d23+T(3,{4}),d24+T(4,{3})}T(3,{4})=d34+T(4,Φ)T(4,Φ)=d412024/7/527of158T(1,{2,3,4})T(2,{3,4})T(3,{2,4})T(4,{2,3})T(3,{4})T(4,{3})T(2,{4})T(4,{2})T(2,{3})T(3,{2})T(4,Φ)T(3,Φ)T(4,Φ)T(2,Φ)T(3,Φ)T(4,Φ)2024/7/528of158矩陣鏈乘法問(wèn)題描述加括號(hào)的方案數(shù)動(dòng)態(tài)規(guī)劃法2024/7/529of158矩陣鏈乘法:問(wèn)題描述給定n個(gè)矩陣A1,A2,…,An,Ai的維數(shù)為

pi-1×pi(1≤i≤n),要求計(jì)算鏈乘積A1A2…An由于矩陣乘法滿(mǎn)足結(jié)合率，所以可以有許多不同的計(jì)算次序，這種計(jì)算次序可以用加括號(hào)的方式來(lái)確定。比如：A1,A2,A3,A4

(A1(

A2(

A3(A4)))(A1((

A2A3)A4))(A1A2)(

A3A4)((A1(

A2A3))

A4)((A1A2)

A3)A4)2024/7/530of158不同的計(jì)算次序有不同的計(jì)算量注：1.設(shè)Ap×q,Aq×r兩矩陣相乘，普通乘法的次數(shù)為p×q×r2.加括號(hào)對(duì)乘法次數(shù)的影響如：A10×100×B100×5×C5×50((AB)C):10×100×5+10×5×50=7500次(A(BC)):100×5×50+10×100×50=75000次2024/7/531of158窮舉法：將n個(gè)矩陣從第k和第k+1處隔開(kāi)，對(duì)二個(gè)子序列再分別加括號(hào)，則可以得到下面遞歸式：因此，窮舉法不是一個(gè)有效算法2024/7/532of1581.矩陣鏈乘問(wèn)題滿(mǎn)足最優(yōu)性原理記A[i:j]為AiAi+1…Aj鏈乘的一個(gè)最優(yōu)括號(hào)方案，設(shè)A[i:j]的最優(yōu)次序中含有二個(gè)子鏈A[i:k]和A[k+1:n]，則A[i:k]和A[k+1:n]也是最優(yōu)的。（反證可得）2.矩陣鏈乘的子問(wèn)題空間：A[i:j],1≤i≤j≤nA[1:1],A[1:2],A[1,:3],…,A[1:n]A[2:2],A[2:3],…,A[2:n]………A[n-1:n-1],A[n-1,n]A[n,n]2024/7/533of158遞歸求解最優(yōu)解的值記m[i][j]為計(jì)算A[i:j]的最少乘法數(shù)，則原問(wèn)題的最優(yōu)值為

m[1][n](AiAi+1…Ak)pi-1×pk×(Ak+1Ak+2…Aj)pk×pj2024/7/534of158依據(jù)遞歸式自底向上計(jì)算。在計(jì)算過(guò)程中，保存已經(jīng)解決的子問(wèn)題答案。A1,A2,A3,A4,A5,A62024/7/535of158A1=(a

ij)35Х40A2=(a

ij)40Х20

A3=(a

ij)20Х10A4=(a

ij)10Х15m[1][3]=min{m[1][2]=m[2][3]=40Х20Х10＝8000

m[3][4]=20Х10Х15＝300035Х40Х20＝28000m[1][1]+m[2][3]+35Х40Х10,

m[1][2]+m[3][3]+35Х20Х10}m[2][4]m[1][4]m11m12m13m14m22m23m24m33m34m44

j=1234i=1

2

3

42024/7/536of158MATRIX-CHAIN-ORDER(p)1n←

length[p]-12fori←1ton3 dom[i,i]←04forl←2ton//listhechainlength.5 dofori←1ton-l+16 doj←

i+l-17 m[i,j]←

∞8 fork←

itoj-19 doq←

m[i,k]+m[k+1,j]+pi-1pkpj10 ifq<m[i,j]11 thenm[i,j]←

q12 s[i,j]←

k13returnmands

(n3)2024/7/537of158矩陣鏈乘法:s中存放m取得最優(yōu)時(shí)k的值

行x列A1 30x35A2 35x15A3 15x5A4 5x10A5 10x20A6 20x256555443333i33322333111654321sj6543i21654321mj0000001512550003500100053752500750105007125437526251187593757875157502024/7/538of158矩陣鏈乘法:s中存放m取得最優(yōu)時(shí)k的值6555443333i33322333111654321sjPRINT-OPTIMAL-PARENS(s,i,j)1ifi=j2 thenprint"A"i3 elseprint"("4 PRINT-OPTIMAL-PARENS(s,i,s[i,j])5 PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)6 print")"A1,A2,A3,A4,A5,A6

((A1(A2A3))((A4A5)A6))

2024/7/539of158課堂練習(xí)：貨物儲(chǔ)運(yùn)問(wèn)題在一個(gè)鐵路沿線(xiàn)順序存放著n堆裝滿(mǎn)貨物的集裝箱。貨物儲(chǔ)運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費(fèi)用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個(gè)運(yùn)輸方案，使總運(yùn)輸費(fèi)用最少。5,3,4,1,3,2,3,4為了簡(jiǎn)化，只算5,3,4,12024/7/540of158貨物儲(chǔ)運(yùn)問(wèn)題在一個(gè)鐵路沿線(xiàn)順序存放著n堆裝滿(mǎn)貨物的集裝箱。貨物儲(chǔ)運(yùn)公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運(yùn)輸費(fèi)用與新的一堆中集裝箱數(shù)成正比。給定各堆的集裝箱數(shù)，試制定一個(gè)運(yùn)輸方案，使總運(yùn)輸費(fèi)用最少。5,3,4,1,3,2,3,4設(shè)合并a[i:j]，1≤i≤j≤n，所需的最少費(fèi)用為m[i,j]，則原問(wèn)題的最優(yōu)值為m[1，n]。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知，2024/7/541of158貨物儲(chǔ)運(yùn)問(wèn)題5,3,4,1m11m12m13m14m22m23m24m33m34m44

j=1234i=1

2

3

4

j=1234i=1

2

3

4反例4,2,3,42024/7/542of158最優(yōu)子結(jié)構(gòu):無(wú)后效性無(wú)權(quán)最短路徑:邊數(shù)最少.具有最優(yōu)子結(jié)構(gòu)性質(zhì).無(wú)權(quán)最長(zhǎng)最短路徑:一定簡(jiǎn)單.ifwedecomposealongestsimplepathintosubpaths,

thenmustn'tp1bealongestsimplepathfromutow,

andmustn'tp2bealongestsimplepathfromwtov?

Theanswerisno!

uv除接合點(diǎn)外,不能共享資源.2024/7/543of158最優(yōu)子結(jié)構(gòu):無(wú)后效性動(dòng)態(tài)規(guī)劃要求其子問(wèn)題既獨(dú)立又重疊:

如果同一問(wèn)題的兩個(gè)子問(wèn)題不共享資源,則它們是獨(dú)立的;

對(duì)兩個(gè)子問(wèn)題來(lái)說(shuō),如果它們確實(shí)是相同的子問(wèn)題,只是作為不同問(wèn)題的子問(wèn)題出現(xiàn)的話(huà),是重疊的,則它們是重疊的.2024/7/544of158重疊子問(wèn)題對(duì)比分治法遞歸的每一步常常產(chǎn)生全新的子問(wèn)題.2024/7/545of158計(jì)算m[1][4]過(guò)程如下：自頂向下遞歸求解最優(yōu)解的值重疊子問(wèn)題2024/7/546of158備忘錄MEMOIZED-MATRIX-CHAIN(p)1n←

length[p]-12fori←1ton3 doforj←

iton4 dom[i,j]←

∞5returnLOOKUP-CHAIN(p,1,n)//表示該子問(wèn)題尚未解決2024/7/547of158備忘錄LOOKUP-CHAIN(p,i,j)1ifm[i,j]<∞2 thenreturnm[i,j]3ifi=j4 thenm[i,j]←05 elsefork←

itoj-16 doq←LOOKUP-CHAIN(p,i,k) +LOOKUP-CHAIN(p,k+1,j)+pi-1

pkpj7 ifq<m[i,j]8 thenm[i,j]←

q9returnm[i,j]2024/7/548of158自底向上的動(dòng)規(guī)與備忘錄區(qū)別自底向上的動(dòng)規(guī)每個(gè)子問(wèn)題至少求解一次.備忘錄某些子問(wèn)題根本沒(méi)有必要求解.2024/7/549of158Floyd算法A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}A(k)(i,j)表示從i到j(luò)的最短路徑,且允許的中間結(jié)點(diǎn)是1…k04116023∞0v1

v2v3v1v2v3123643112v1

v2v3v1v2v30411602370A(1)

=2024/7/550of158A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}A(k)(i,j)表示從i到j(luò)的最短路徑,且允許的中間結(jié)點(diǎn)是1…k04116023∞0v1

v2v3v1v2v3123643112v1

v2v3v1v2v30411602370A(1)

=v1

v2v3v1v2v3046

602370A(2)

=v1

v2v3v1v2v3046502370A(3)

=2024/7/551of158

Warshall算法Mk+1[i,j]=Mk[i,j]Floyd:

A(k+1)(i,j)=min{A(k)(i,j)

,

A(k)(i,k+1)+A(k)(k+1,j)}∨(Mk[i,k+1]∧

Mk[k+1,j])2024/7/552of158

Warshall算法Mk+1[i,j]=Mk[i,j]∨(Mk[i,k+1]∧

Mk[k+1,j])2024/7/553of158TRANSITIVE-CLOSURE(G)1n←|V[G]|2fori←1ton3 doforj←1ton4 doifi=jor(i,j)∈

E[G]11returnT(n)

Warshall算法2024/7/554of1580-1背包問(wèn)題:問(wèn)題描述及舉例問(wèn)題描述舉例：w=(w1,w2,w3)=(2,3,4),v=(v1,v2,v3)=(1,2,5),n=3,c=6,求Knap(1,3,6)

取x=(1,0,1)時(shí)，2024/7/555of1580-1背包問(wèn)題滿(mǎn)足最優(yōu)性原理證明：設(shè)(y1,y2,…,yn)是Knap(1,n,c)的一個(gè)最優(yōu)解，則(y2,…,yn)是Knap(2,n,c-w1y1)子問(wèn)題的一個(gè)最優(yōu)解。若不然，設(shè)(z2,…,zn)是Knap(2,n,c-w1y1)的最優(yōu)解，因此有說(shuō)明(y1,z2,…,zn)是Knap(1,n,c)的一個(gè)更優(yōu)解，矛盾。2024/7/556of1580-1背包問(wèn)題:遞歸關(guān)系考慮子問(wèn)題：

Knap(i,n,j)j≤c(假設(shè)c,wi取整數(shù))

設(shè)其最優(yōu)值為m(i,j),即m(i,j)是背包容量為j,可選物品為i,i+1,…,n的0-1背包問(wèn)題的最優(yōu)值。子問(wèn)題的背包容量在變化2024/7/557of1580-1背包問(wèn)題:遞歸關(guān)系遞歸式如下：不取物品i取物品i2024/7/558of1580-1背包問(wèn)題:算法voidKnapsack(intv[],intw[],intc,intn,intm[][]){//輸出m[1][c]intjMax=min(w[n]-1,c);//因?yàn)閖≤c,只要計(jì)算到m[1][c]即可

for(intj=0;j<=jMax;j++)m[n][j]=0;//0≤j<wn,(4)式

for(intj=w[n];j<=c;j++)m[n][j]=v[n];//j≥wn,(3)式

for(inti=n-1;i>1;i--){//i>1表示對(duì)i=1不處理，因?yàn)閕=1時(shí)只需求m[1][c]jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//0≤j<wi,(2)式

m[i][j]=m[i+1][j];for(intj=w[i];j<=c;j++)//j≥wi,(1)式

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}if(c>=w[1])m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);elsem[1][c]=m[2][c];}2024/7/559of1580-1背包問(wèn)題:算法（續(xù)）voidTraceback(intw[],intc,intn,intm[][],intx[]){//輸出解x[1..n]for(inti=0;i<n;i++)if(m[i][c]=m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}x[n]=(m[n][c])?1:0;}運(yùn)行時(shí)間：T(n)=O(cn)2024/7/560of1580-1背包問(wèn)題00000pi–1(j–wi)pi–1(j)0pi(j)0目標(biāo)

0i–1in0j–wi

jM2024/7/561of158例：有5個(gè)物體，其重量分別為2,2,6,5,4，價(jià)值分別為6,3,5,4,6，背包的載重量為10，求裝入背包的物體及其總價(jià)值2024/7/562of158找零錢(qián)問(wèn)題:問(wèn)題描述問(wèn)題描述一出納員支付一定數(shù)量的現(xiàn)金。假設(shè)他手中有幾種面值的硬幣，要求他用最少的硬幣數(shù)支付規(guī)定的現(xiàn)金。

例如，現(xiàn)有3種硬幣：它們的面值分別為1元、4元和6元。要支付8元。2024/7/563of1580-1背包問(wèn)題:遞歸關(guān)系不用第i種硬幣用第i種硬幣pi(j)：前i種硬幣支付金額j所需硬幣的最少個(gè)數(shù)。2024/7/564of1580∞

∞∞0pi–1(j)0pi(j–vi)pi(j)0目標(biāo)

0i–1in0j–vi

j82024/7/565of1581元、4元和6元。要支付8元。01234567800∞∞∞∞∞∞∞∞1012345678201231234230123121222024/7/566of158某公司準(zhǔn)備將新招聘的4名銷(xiāo)售員分配到下屬3個(gè)銷(xiāo)售點(diǎn)

甲、乙和丙。各銷(xiāo)售點(diǎn)增加若干名銷(xiāo)售員后可增加的

月銷(xiāo)售額如下表：增加銷(xiāo)售額（千元）增1人增2人增3人增4人甲12223038乙11202430丙13253036根據(jù)此表，只要人員分配適當(dāng)，公司每月最多

可以增加銷(xiāo)售額（）千元。動(dòng)規(guī)練習(xí)2024/7/567of158最長(zhǎng)公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對(duì)于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應(yīng)的遞增下標(biāo)序列為{2，3，5，7}。給定2個(gè)序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時(shí)，稱(chēng)Z是序列X和Y的公共子序列。給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長(zhǎng)公共子序列。

2024/7/568of158最長(zhǎng)公共子序列的結(jié)構(gòu)設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長(zhǎng)公共子序列為Z={z1,z2,…,zk}，則(1)若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長(zhǎng)公共子序列。(2)若xm≠yn且zk≠xm，則Z是xm-1和Y的最長(zhǎng)公共子序列。(3)若xm≠yn且zk≠yn，則Z是X和yn-1的最長(zhǎng)公共子序列。證明:P57由此可見(jiàn)，2個(gè)序列的最長(zhǎng)公共子序列包含了這2個(gè)序列的前綴的最長(zhǎng)公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2024/7/569of158子問(wèn)題的遞歸結(jié)構(gòu)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問(wèn)題最優(yōu)值的遞歸關(guān)系。用c[i][j]記錄序列和的最長(zhǎng)公共子序列的長(zhǎng)度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列。故此時(shí)C[i][j]=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：2024/7/5