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

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

(DynamicProgramming)1內(nèi)容動(dòng)態(tài)規(guī)劃概述基本思想基本原理基本要素動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)與實(shí)現(xiàn)矩陣連乘、凸多邊形最優(yōu)三角剖分最長公共子序列、最大子段和多邊形游戲、圖像壓縮電路布線、0-1背包問題2基本思想動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支。1950s，美國數(shù)學(xué)家RichardBellman在研究多階段決策過程的優(yōu)化問題時(shí)，提出了這一策略。使整個(gè)活動(dòng)的總體效果達(dá)到最優(yōu)的問題，稱為多階段決策問題。多階段決策過程是指可以按照時(shí)間順序?qū)⒃瓎栴}分解成若干相互聯(lián)系的階段，在每一階段都要作出決策。3多階段決策問題及多階段決策過程階段：將所給問題的過程，按時(shí)間或空間特征分解成若干相互聯(lián)系的階段，以便按次序去求每階段的解。狀態(tài)：各階段開始時(shí)的客觀條件叫做狀態(tài)。決策：當(dāng)各階段的狀態(tài)確定以后，就可以做出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。狀態(tài)轉(zhuǎn)移：根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。由第k-1段的狀態(tài)Sk-1和決策Uk-1確定第k段的狀態(tài)Sk。策略：各段決策確定后，整個(gè)問題的決策序列就構(gòu)成一個(gè)策略。使整個(gè)問題達(dá)到最優(yōu)效果的策略就是最優(yōu)策略。最優(yōu)策略的子策略也是最優(yōu)策略?；舅枷?基本思想動(dòng)態(tài)規(guī)劃策略通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個(gè)解都對應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個(gè)解。動(dòng)態(tài)Dynamic在一定條件下，當(dāng)前階段和下一階段的狀態(tài)的轉(zhuǎn)換。規(guī)劃Programming建立狀態(tài)轉(zhuǎn)移方程（或稱各階段間的遞推關(guān)系式）、將各個(gè)階段的狀態(tài)以表格式方法存儲。表格式方法(tabularmethod)：用一個(gè)表來記錄所有已解決的子問題的解。以空間換時(shí)間(space-for-timetradeoff)。5例如，找零錢問題當(dāng)硬幣系統(tǒng)為2角5分、1角、5分、1分時(shí)，要找給顧客6角3分錢，怎么做？一般思維：0.63=2個(gè)0.25+1個(gè)0.1+3個(gè)0.01所拿出的硬幣個(gè)數(shù)是最少的再如當(dāng)硬幣系統(tǒng)為4分、3分、1分時(shí)，要找給顧客6分錢，怎么做？一般思維：6=1個(gè)4分+2個(gè)1分2個(gè)3分才是最優(yōu)解！6Solveforallof1￠,2￠,3￠,...,6￠Tomake1￠(1coin)Tomake2￠,1￠+1￠(1coin+1coin=2coins)Tomake3￠,justusethe3￠coin(1coin)Tomake4￠,justusethe4￠coin(1coin)Tomake5￠,try1￠+4￠(1coin+1coin=2coins)2￠+3￠(2coins+1coin=3coins)Tomake6￠,try1￠+5￠(1coin+2coins=3coins)2￠+4￠(2coins+1coin=3coins)3￠+3￠(1coin+1coin=2coins)子問題原問題Example:CountingCoins.Findtheminimumnumberofcoins(1￠,3￠,and4￠)tomakeanyamount.For6￠:√bestsolution√bestsolution7最優(yōu)子結(jié)構(gòu)性質(zhì)(optimalsubstructure)原問題的最優(yōu)解包含了子問題的最優(yōu)解。該性質(zhì)使我們能夠以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出原問題的最優(yōu)解。重疊子問題(overlappingsubproblem)有些子問題被反復(fù)計(jì)算多次（前一階段的狀態(tài)帶到當(dāng)前階段，當(dāng)前階段的狀態(tài)帶到下一階段）。基本要素8最優(yōu)子結(jié)構(gòu)/最優(yōu)化原理最優(yōu)策略的子策略也是最優(yōu)策略原問題的最優(yōu)解包含了子問題的最優(yōu)解子問題的最優(yōu)解不一定組成原問題的最優(yōu)解FindtheminimumnumberofUScoins(1,2,5,10)tomakeanyamount.

For13￠Theoptimalsolutionto7￠is5￠+2￠,andTheoptimalsolutionto6￠is5￠+1￠,butTheoptimalsolutionto13￠isnot(5￠+2￠)+(5￠+1￠)Butthereissomewayofdividingup13￠intosubsetswithoptimalsolutions(say,11￠+2￠)thatwillgiveanoptimalsolutionfor13￠Hence,theprincipleofoptimalityholdsforthisproblem9重疊子問題與分治法類似，動(dòng)態(tài)規(guī)劃也是將待求解問題分解成若干子問題。但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。例，fibonacci(5)=fibonacci(4)+fibonacci(3);fibonacci(4)=fibonacci(3)+fibonacci(2)如果能夠記錄已解決的子問題的答案，而在需要時(shí)再找出，就可以避免大量重復(fù)計(jì)算。表格式方法10矩陣連乘

(matrix-chainmultiplication)給定n個(gè)矩陣{A1,A2,…,An}，其中，Ai和Ai+1是可乘的，現(xiàn)要計(jì)算出這n個(gè)矩陣的連乘積A1A2,…,An。矩陣A和矩陣B可乘的條件：A的列數(shù)等于B的行數(shù)。若A是一個(gè)p×q矩陣，B是一個(gè)q×r矩陣，則C=A×B是一個(gè)p×r矩陣，乘法次數(shù)為pqr。連乘：計(jì)算次序（完全加括號方式）對乘法次數(shù)有很大影響。該問題是最優(yōu)性質(zhì)問題：即求解矩陣連乘的最優(yōu)計(jì)算次序，使得依此次序計(jì)算矩陣連乘需要的乘法次數(shù)最少。11蠻力算法設(shè)n個(gè)矩陣連乘有P(n)個(gè)不同的計(jì)算次序。由于每種加括號方式都可以分解為兩個(gè)子矩陣的加括號問題：(A1...Ak)(Ak+1…An)，所以P(n)的遞歸關(guān)系式為：動(dòng)態(tài)規(guī)劃算法將矩陣連乘積AiAi+1...Aj簡記為A[i:j]，這里i≤j由于矩陣可乘，則設(shè)Ai的維數(shù)為Pi-1×Pi設(shè)A[i:j]的最優(yōu)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應(yīng)完全加括號方式為

(AiAi+1...Ak)(Ak+1Ak+2...Aj)總的計(jì)算量=A[i:k]的計(jì)算量+A[k+1:j]的計(jì)算量+A[i:k]和A[k+1:j]相乘的計(jì)算量(Pi-1PkPj)12分析最優(yōu)解的結(jié)構(gòu)：計(jì)算A[i:j]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的；遞歸定義最優(yōu)值：設(shè)計(jì)算A[i:j](1≤i≤j≤n)所需要的最少的乘法次數(shù)為m[i,j]，則原問題的最優(yōu)值為m[1,n]；計(jì)算最優(yōu)值：依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。記錄已解決的子問題答案。設(shè)的維數(shù)為

的位置只有種可能13例，5個(gè)矩陣連乘，行列數(shù)如下：A1A2A3A4A52*33*44*55*66*7024641242080601502760120288021001234234344記錄最優(yōu)值記錄斷開位置(((A1A2)A3)A4)A514計(jì)算最優(yōu)值：MatrixChain(p,m,s)//p={p0,p1,…,pn}，Ai的維數(shù)是p[i-1]*p[i]n=p.length-1//對角線為單一矩陣

fori=1tondom[i][i]=0//矩陣鏈長度

forr=2tondo

fori=1ton–r+1doj=i+r–1//相鄰矩陣m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]s[i][j]=i//矩陣鏈長度>2時(shí)找斷開位置

fork=i+1toj-1dot=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]

ift<m[i][j]m[i][j]=ts[i][j]=k構(gòu)造最優(yōu)解：Traceback(i,j,s)

ifi=jreturnTraceback(i,s[i][j],s)Traceback(s[i][j]+1,j,s)15算法分析MatrixChain的計(jì)算量取決于算法中對r,i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為θ(1)，而3重循環(huán)的總次數(shù)為θ(n3)。因此算法的計(jì)算時(shí)間為θ(n3)。T(n)=填表時(shí)間(計(jì)算最優(yōu)值)+查表時(shí)間(構(gòu)造最優(yōu)解)=填寫二維表×遍歷斷開位置+查表時(shí)間

=θ(n3)+θ(n)=θ(n3)空間復(fù)雜性：表格大小，θ(n2)16動(dòng)態(tài)規(guī)劃算法的基本步驟分析最優(yōu)解的結(jié)構(gòu)；遞歸定義最優(yōu)值（由最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系）；決策：選擇全部可能解中的最優(yōu)解（最大/?。ㄒ宰缘紫蛏系姆绞剑┯?jì)算最優(yōu)值；（根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息）構(gòu)造最優(yōu)解。17凸多邊形最優(yōu)三角剖分

(TriangulationofaConvexPolygon)凸多邊形就是把一個(gè)多邊形任意一邊向兩方無限延長成為一條直線，如果多邊形的其他各邊均在此直線的同旁，那么這個(gè)多邊形就叫做凸多邊形。用頂點(diǎn)的逆時(shí)針序列表示凸多邊形，即P={v0,v1,…,vn-1}，表示有n條邊v0v1,v1v2,…,vn-1v0若vi和vj是不相鄰的頂點(diǎn)，則線段vivj稱為弦；弦vivj將多邊形分割成兩個(gè)多邊形{vi,vi+1,…,vj}和{vj,vj+1,…,vi}凸多邊形的三角剖分是將凸多邊形分割成互不相交的三角形的弦的集合。18凸多邊形最優(yōu)三角剖分給定一個(gè)凸多邊形P={v0,v1,…,vn-1}，以及定義在由凸多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的一個(gè)三角剖分，使得該三角剖分中諸三角形上權(quán)之和為最小。19本質(zhì)上與矩陣連乘的最優(yōu)計(jì)算次序問題極為相似表達(dá)式的語法樹是一個(gè)完全二叉樹：葉結(jié)點(diǎn)、內(nèi)結(jié)點(diǎn)、根節(jié)點(diǎn)((A1(A2A3))(A4(A5A6)))所對應(yīng)的語法樹矩陣連乘中的每個(gè)矩陣Ai對應(yīng)于凸(n+1)邊形中的一條邊vi-1vj。三角剖分中的一條弦vivj，i<j，對應(yīng)于矩陣連乘A[i+1:j]20vkvkvk與矩陣連乘的算法相同時(shí)間復(fù)雜性：θ(n3)；空間復(fù)雜性：θ(n2)最優(yōu)子結(jié)構(gòu)性質(zhì)：若凸(n+1)邊形P={v0,v1,…,vn}的最優(yōu)三角剖分T包含三角形v0vkvn，則T的權(quán)為3個(gè)部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vK+1,…,vn}的權(quán)之和。定義t[i][j]，1≤i<j≤n為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對應(yīng)的權(quán)函數(shù)值。v0v1vn21最長公共子序列

(LongestCommonSubsequence)給定2個(gè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}是X的子序列是指存在一個(gè)嚴(yán)格遞增下標(biāo)序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xi序列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í)，稱Z是序列X和Y的公共子序列。22分析最優(yōu)解的結(jié)構(gòu)：設(shè)序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則若xm=yn

，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列。

//Xm-1={x1,x2,…,xm-1};Yn-1={y1,y2,…,yn-1};Zk-1={z1,z2,…,zk-1}若xm≠yn且zk≠xm，則Z是Xm-1和Y的最長公共子序列。若xm≠yn且zk≠yn，則Z是X和Yn-1的最長公共子序列。遞歸定義最優(yōu)值：用c[i][j]記錄Xi和Yj的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。建立遞歸關(guān)系如下：23計(jì)算最優(yōu)值：LcsLength(x,y,b)m=x.length-1n=y.length-1

fori=1tomdoc[i][0]=0

fori=1tondoc[0][i]=0

fori=1tomdo

forj=1tondo

ifx[i]=y[j]c[i][j]=c[i-1][j-1]+1b[i][j]=對角線值

elseifc[i-1][j]>=c[i][j-1]c[i][j]=c[i-1][j]b[i][j]=上值

elsec[i][j]=c[i][j-1]b[i][j]=左值構(gòu)造最優(yōu)解：Lcs(i,j,x,b)

ifi=0orj=0return

ifb[i][j]=對角線值

Lcs(i-1,j-1,x,b)System.out.print(x[i])

else

ifb[i][j]=上值

Lcs(i-1,j,x,b)

elseLcs(i,j-1,x,b)24算法的改進(jìn)在算法LcsLength和Lcs中，可進(jìn)一步將數(shù)組b省去。事實(shí)上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個(gè)數(shù)組元素的值所確定。對于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在O(1)時(shí)間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個(gè)值所確定的。25算法分析T(n)=計(jì)算最優(yōu)值（填表）的時(shí)間+構(gòu)造最優(yōu)解的時(shí)間=θ(mn)+θ(m+n)空間復(fù)雜性：表格大小θ(mn)26最大子段和

(Maximumsubarray)給定由n個(gè)整數(shù)組成的序列a1,a2,…,an，求該序列形如（即連續(xù)的）的子段和的最大值。當(dāng)所有整數(shù)均為負(fù)整數(shù)時(shí)定義其最大子段和為0。依此定義，所求的最優(yōu)值為(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)時(shí)，最大子段和為27蠻力算法：掃描任意個(gè)數(shù)的子段的和改進(jìn)算法一：表格式方法tabularmethod，利用已得到的結(jié)果，避免重復(fù)計(jì)算。θ(n2)表格中存放的并不是各階段的最優(yōu)值！能否進(jìn)一步改進(jìn)？該問題的最好情況輸入：全負(fù)或全正。θ(n)改進(jìn)算法二：分治法θ(nlogn)改進(jìn)算法三：動(dòng)態(tài)規(guī)劃θ(n)28設(shè)，即b[j]=max(a[i]+a[i+1]+..+a[j])，1≤i≤j≤n

則根據(jù)b[j]的定義，可以看出當(dāng)b[j-1]>0時(shí)，無論a[j]為何值，b[j]=b[j-1]+a[j]當(dāng)b[j-1]<0時(shí)，無論a[j]為何值，b[j]=a[j]故29多邊形游戲

(PolygonGame)有一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的多邊形。每個(gè)頂點(diǎn)被賦予一個(gè)整數(shù)值，每條邊被賦予一個(gè)運(yùn)算符“+”或“*”。所有邊依次用整數(shù)從1到n編號。游戲規(guī)則：第一步，將一條邊刪除；隨后n-1步按以下方式操作：選擇一條邊E以及由E連接著的2個(gè)頂點(diǎn)v1和v2；用一個(gè)新的頂點(diǎn)取代邊E以及由E連接著的2個(gè)頂點(diǎn)v1和v2。將由頂點(diǎn)v1和v2的整數(shù)值通過邊E上的運(yùn)算得到的結(jié)果賦予新頂點(diǎn)。最后，所有的邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點(diǎn)上的整數(shù)值。對于給定的多邊形，計(jì)算出最高得分，且列出所有得到這個(gè)最高得分首次被刪除的邊的編號。-7452+**+213430蠻力算法：窮舉法解決此問題的復(fù)雜性是n!-7452+**+2134-7452+*+214-242+*24-44+201號邊與2號邊之間的頂點(diǎn)的數(shù)值是1號頂點(diǎn)的數(shù)值…最后一個(gè)數(shù)值對應(yīng)于與n號邊和1號邊相關(guān)聯(lián)的頂點(diǎn)。31設(shè)p(i,j)是從頂點(diǎn)i開始，長度為j（即鏈中有j個(gè)頂點(diǎn)）的順時(shí)針鏈，表示為v[i],op[i+1],…,v[i+j-1]如果這條鏈的最后一次合并運(yùn)算在op[i+s]處發(fā)生(1≤s≤j-1)，則可在op[i+s]處將鏈分割為2個(gè)子鏈p(i,s)和p(i+s,j-s)設(shè)m1是對子鏈p(i,s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+s,j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有a≤m1≤b，c≤m2≤d在op[i+s]處合并后的值為m=(m1)op[i+s](m2)當(dāng)op[i+s]=‘+’時(shí)，a+c≤m≤b+d當(dāng)op[i+s]=‘*’時(shí)，min{ac,ad,bc,bd}≤m≤max{ac,ad,bc,bd}32為了求鏈合并的最大值，必須同時(shí)求子鏈合并的最大值和最小值。設(shè)m[i,j,0]是p(i,j)合并的最小值，m[i,j,1]是p(i,j)合并的最大值。設(shè)子鏈p(i,s)和p(i+s,j-s)的最大值和最小值分別為：a=m[i,s,0],b=m[i,s,1],c=m[i+s,j-s,0],d=m[i+s,j-s,1]時(shí)間復(fù)雜性（與矩陣連乘相同）為：θ(n3)33-7452+**+2134-7-3-6-304840-16210-405-22-112341234ijm[i,j,0]-7-3133484033210375-22612341234ijm[i,j,1]p(i,j)是從頂點(diǎn)i開始，長度為j（即鏈中有j個(gè)頂點(diǎn)）的順時(shí)針鏈。m[i,j,0]是p(i,j)合并的最小值，m[i,j,1]是p(i,j)合并的最大值。34圖像壓縮

(ImageCompression)計(jì)算機(jī)中常用像素點(diǎn)灰度值序列{p1,p2,…,pn}表示圖像。其中整數(shù)pi表示像素點(diǎn)i的灰度值。通常灰度值的范圍是0~255（需要用8位表示一個(gè)像素）圖像的變位壓縮格式是將所給的像素點(diǎn)序列{p1,p2,…,pn}分割成m個(gè)連續(xù)段S1,S2,…,Sm。第i個(gè)像素段Si中有l(wèi)[i]個(gè)像素，且該段中每個(gè)像素都只用b[i]位來表示。設(shè)表示前i-1個(gè)像素段所包含的像素

個(gè)數(shù)，則第i個(gè)像素段Si

：35設(shè)，則hi

b[i]

8，因此需要用3位表示b[i]。如果限制1

l[i]

255，則需要用8位表示l[i]。因此，第i個(gè)像素段所需的存儲空間為l[i]*b[i]+11位。按此格式存儲像素序列{p1,p2,…,pn}，需要位的存儲空間。圖像壓縮問題要求確定像素序列{p1,p2,…,pn}的最優(yōu)分段（確定l[i]和b[i]），使得依此分段所需的存儲空間最少。其中，每個(gè)分段的長度不超過256位。36最優(yōu)子結(jié)構(gòu)性質(zhì)原問題的最優(yōu)解：設(shè)l[i]和b[i]，1im是{p1,p2,…,pn}的一個(gè)最優(yōu)分段子問題的最優(yōu)解：l[1]和b[1]是{p1,…,pl[1]}的一個(gè)最優(yōu)分段，且l[i]和b[i]，2im是{pl[1]+1,…,pn}的一個(gè)最優(yōu)分段。設(shè)s[i]是{p1,…,pi}的最優(yōu)分段所需的存儲位數(shù)，則時(shí)間復(fù)雜性由于對k的循環(huán)次數(shù)不超過256，故對每一個(gè)確定的i，可在時(shí)間θ(1)內(nèi)完成s[i]的計(jì)算。因此整個(gè)算法所需的計(jì)算時(shí)間為θ(n)其中：{p1,p2,…,pi}{p1,…,pi-k,pi-k+1,…,pi}S[i]

當(dāng)前分段S[i-k]37電路布線在一塊電路板的上、下兩端分別有n個(gè)接線柱。根據(jù)電路設(shè)計(jì)，要求用導(dǎo)線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是{1,2,…,n}的一個(gè)排列。導(dǎo)線(i,π(i))稱為該電路板上的第i條連線。對于任何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。在制作電路時(shí)，要求將這n條連線分布到若干絕緣層上。在同一層上的連線不相交。電路布線問題就是要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導(dǎo)線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。38設(shè)的最大不相交子集為MNS(i,j)，且Size(i,j)=|MNS(i,j)|當(dāng)i=1時(shí)，當(dāng)i>1時(shí)(1)j<π(i)，。在這種情況下，N(i,j)=N(i-1,j)，故MNS(i,j)=MNS(i-1,j)，從而Size(i,j)=Size(i-1,j)。π(i)iN(i,j)j39(2)j≥π(i)若(i,π(i))∈MNS(i,j)，則對任意(t,π(t))∈MNS(i,j)，有t<i且π(t)<π(i)，否則(t,π(t))和(i,π(i))相交；

MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集，否則N(i-1,π(i)-1)的最大不相交子集MNS(i-1,π(i)-1)并上{(i,π(i))}（包含于）是N(i,j)中比MNS(i,j)更大的不相交子集。與MNS(i,j)的定義矛盾。所以，Size(i,j)=Size(i-1,π(i)-1)＋1iπ(i)jN(i,j)i-1π(i)-140若，則對任意(t,π(t))∈MNS(i,j)有t<i。從而。故Size(i,j)≤Size(i-1,j)另外，，故Size(i,j)≥Size(i-1,j)所以，Size(i,j)=Size(i-1,j)iπ(i)jN(i,j)tπ(t)41(1)當(dāng)i=1時(shí)(2)當(dāng)i>1時(shí)42實(shí)例練習(xí)對應(yīng)關(guān)系為：(1,8),(2,7),(3,4),(4,2),(5,5),(6,1),(7,9),(8,3),(9,10),(10,6)43計(jì)算最優(yōu)值123456789101000000011120000001111300011111114011111111150111222222611112222227111122223381122222233911222222341011222333341,82,73,44,25,56,17,98,39,1010,6i,π(i)ij44構(gòu)造最優(yōu)解123456789101000000011120000001111300011111114011111111150111222222611112222227111122223381122222233911222222341011222333341,82,73,44,25,56,17,98,39,1010,6iji,π(i)450-1背包問題給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為c。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?0-1：在選擇裝入背包的物品時(shí)，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。0-1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題。作個(gè)假設(shè)找出一個(gè)n元0-1向量(x1,x2,…,xn)，使得46Theexhaustivesearchapproachtothisproblemleadstoconsideringallthesubsetsofthesetofnitemsgiven,computingthetotalweightofeachsubsetinordertoidentifyfeasiblesubsets,andfindingasubsetofthelargestvalueamongthem.Theknapsackproblemisthebest-knownexamplesofso-calledNP-hardproblem.Nopolynomial-timealgorithmisknownforanyNP-hardproblem.Moreover,mostcomputerscientistsbelievethatsuchalgorithmsdonotexist,althoughthisveryimportantconjecturehasneverbeenproven.47分析最優(yōu)子結(jié)構(gòu)性質(zhì)原問題的最優(yōu)解：設(shè)(y1,y2,…,yn)是給定n種物品在背包載重為c時(shí)的一個(gè)最優(yōu)解子問題的最優(yōu)解：則(y2,…,yn)是除了第一個(gè)物品之外的n-1個(gè)物品在背包載重為c-w1y1時(shí)的一個(gè)最優(yōu)解。反證法：如若不然，設(shè)(z2,…,zn)是上述子問題的一個(gè)最優(yōu)解，而(y2,…,yn)不是。48Letusconsideraninstancedefinedbythefirstiitems,1in,withweightsw1,w2,…,wi,valuesv1,v2,…,vi,andknapsackcapacityj,1jc.LetV[i,j]bethevalueofanoptimalsolutiontothisinstance,i.e.,thevalueofthemostvaluablesubsetofthefirstiitemsthatfitintotheknapsackofcapacityj.Wecandivideallthesubsetsofthefirstiitemsthatfittheknapsackofcapacityjintotwocategories:thosethatdonotincludetheithitemandthosethatdo.49Amongthesubsetsthatdonotincludetheithitem,thevalueofanoptimalsubsetis,bydefinition,V(i-1,j)Amongthesubsetsthatdoincludetheithitem(j-wi0),anoptimalsubsetismadeupofthisitemandanoptimalsubsetofthefirsti-1itemsthatfitintotheknapsackofcapacityj-wi.Thevalueofsuchanoptimalsubsetisvi+V(i-1,j-wi)OutgoalistofindV(n,c),themaximalvalueofasubsetofthengivenitemsthatfitintotheknapsackofcapacityc,andanoptimalsubsetitself.50算法復(fù)雜性：θ(nc)。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c>2n時(shí)，算法需要Ω(n2n)計(jì)算時(shí)間。裝不下能裝但不裝裝設(shè)V(i,j)是背包容量為j，可選擇物品為前i個(gè)(x1,x2,…,xi)時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算V(i,j)的遞歸式5100000000goalni-1iwivij-wijcV[i-1,j-wi]V[i-1,j]V[i,j]itemweightvalue12122