動態(tài)規(guī)劃網(wǎng)絡

動態(tài)規(guī)劃網(wǎng)絡1第一頁，共五十一頁，編輯于2023年，星期日學習要點:理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）重疊子問題性質(zhì)掌握設計動態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計算出最優(yōu)值。(4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。2第二頁，共五十一頁，編輯于2023年，星期日通過應用范例學習動態(tài)規(guī)劃算法設計策略。（1）矩陣連乘問題；（2）最長公共子序列；（3）最大子段和（4）凸多邊形最優(yōu)三角剖分；（5）多邊形游戲；（6）圖像壓縮；（7）電路布線；（8）流水作業(yè)調(diào)度；（9）背包問題；（10）最優(yōu)二叉搜索樹。3第三頁，共五十一頁，編輯于2023年，星期日動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=4第四頁，共五十一頁，編輯于2023年，星期日但是經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)5第五頁，共五十一頁，編輯于2023年，星期日如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。算法總體思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)6第六頁，共五十一頁，編輯于2023年，星期日動態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。7第七頁，共五十一頁，編輯于2023年，星期日完全加括號的矩陣連乘積可遞歸地定義為：

（1）單個矩陣是完全加括號的；（2）矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)。設有四個矩陣A,B,C,D，它們的維數(shù)分別是：

A=50×10，B=10×40，C=40×30，D=30×5總共有五中完全加括號的方式：

(((AB)C)D)，(A((BC)D))，(A(B(CD)))，((AB)(CD))，((A(BC))D)計算量分別為87500,16000,10500,36000,34500完全加括號的矩陣連乘積8第八頁，共五十一頁，編輯于2023年，星期日矩陣連乘問題給定n個矩陣，其中與是可乘的，?？疾爝@n個矩陣的連乘積由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調(diào)用2個矩陣相乘的標準算法計算出矩陣連乘積9第九頁，共五十一頁，編輯于2023年，星期日矩陣連乘問題給定n個矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。窮舉法：列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。算法復雜度分析：對于n個矩陣的連乘積，設其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1...Ak)(Ak+1…An)可以得到關于P(n)的遞推式如下：10第十頁，共五十一頁，編輯于2023年，星期日矩陣連乘問題窮舉法動態(tài)規(guī)劃將矩陣連乘積簡記為A[i:j]，這里i≤j考察計算A[i:j]的最優(yōu)計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應完全加括號方式為計算量：A[i:k]的計算量加上A[k+1:j]的計算量，再加上A[i:k]和A[k+1:j]相乘的計算量11第十一頁，共五十一頁，編輯于2023年，星期日特征：計算A[i:j]的最優(yōu)次序所包含的計算矩陣子鏈A[i:k]和A[k+1:j]的次序也是最優(yōu)的。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。分析最優(yōu)解的結(jié)構(gòu)12第十二頁，共五十一頁，編輯于2023年，星期日建立遞歸關系設計算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]當i=j時，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當i<j時，可以遞歸地定義m[i,j]為：這里的維數(shù)為

的位置只有種可能13第十三頁，共五十一頁，編輯于2023年，星期日計算最優(yōu)值對于1≤i≤j≤n不同的有序?qū)?i,j)對應于不同的子問題。因此，不同子問題的個數(shù)最多只有由此可見，在遞歸計算時，許多子問題被重復計算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法14第十四頁，共五十一頁，編輯于2023年，星期日用動態(tài)規(guī)劃法求最優(yōu)解voidMatrixChain(int*p，intn，int**m，int**s){for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}}A1A2A3A4A5A63035351515551010202025算法復雜度分析：算法matrixChain的主要計算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。15第十五頁，共五十一頁，編輯于2023年，星期日動態(tài)規(guī)劃算法的基本要素一、最優(yōu)子結(jié)構(gòu)矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設由問題的最優(yōu)解導出的子問題的解不是最優(yōu)的，然后再設法說明在這個假設下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導致矛盾。利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。同一個問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低）16第十六頁，共五十一頁，編輯于2023年，星期日動態(tài)規(guī)劃算法的基本要素二、重疊子問題遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。17第十七頁，共五十一頁，編輯于2023年，星期日動態(tài)規(guī)劃算法的基本要素三、備忘錄方法備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復求解。intLookupChain(inti，intj){if(m[i][j]>0)returnm[i][j];if(i==j)return0;intu=LookupChain(i，i)+LookupChain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++){intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}18第十八頁，共五十一頁，編輯于2023年，星期日最長公共子序列若給定序列X={x1,x2,…,xm}，則另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k有：zj=xij。例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相應的遞增下標序列為{2，3，5，7}。給定2個序列X和Y，當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最長公共子序列。

19第十九頁，共五十一頁，編輯于2023年，星期日最長公共子序列的結(jié)構(gòu)設序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最長公共子序列為Z={z1,z2,…,zk}，則(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的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。20第二十頁，共五十一頁，編輯于2023年，星期日子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關系。用c[i][j]記錄序列和的最長公共子序列的長度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時C[i][j]=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關系如下：21第二十一頁，共五十一頁，編輯于2023年，星期日計算最優(yōu)值由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){inti，j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}構(gòu)造最長公共子序列voidLCS(inti，intj，char*x，int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-1，x，b);}22第二十二頁，共五十一頁，編輯于2023年，星期日算法的改進在算法lcsLength和lcs中，可進一步將數(shù)組b省去。事實上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]這3個數(shù)組元素的值所確定。對于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)組b而僅借助于c本身在時間內(nèi)確定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一個值所確定的。如果只需要計算最長公共子序列的長度，則算法的空間需求可大大減少。事實上，在計算c[i][j]時，只用到數(shù)組c的第i行和第i-1行。因此，用2行的數(shù)組空間就可以計算出最長公共子序列的長度。進一步的分析還可將空間需求減至O(min(m,n))。23第二十三頁，共五十一頁，編輯于2023年，星期日凸多邊形最優(yōu)三角剖分用多邊形頂點的逆時針序列表示凸多邊形，即P={v0,v1,…,vn-1}表示具有n條邊的凸多邊形。若vi與vj是多邊形上不相鄰的2個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成2個多邊形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。多邊形的三角剖分是將多邊形分割成互不相交的三角形的弦的集合T。給定凸多邊形P，以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)w。要求確定該凸多邊形的三角剖分，使得即該三角剖分中諸三角形上權(quán)之和為最小。24第二十四頁，共五十一頁，編輯于2023年，星期日三角剖分的結(jié)構(gòu)及其相關問題一個表達式的完全加括號方式相應于一棵完全二叉樹，稱為表達式的語法樹。例如，完全加括號的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應的語法樹如圖(a)所示。凸多邊形{v0,v1,…vn-1}的三角剖分也可以用語法樹表示。例如，圖(b)中凸多邊形的三角剖分可用圖(a)所示的語法樹表示。矩陣連乘積中的每個矩陣Ai對應于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，i<j，對應于矩陣連乘積A[i+1:j]。25第二十五頁，共五十一頁，編輯于2023年，星期日最優(yōu)子結(jié)構(gòu)性質(zhì)凸多邊形的最優(yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)。事實上，若凸(n+1)邊形P={v0,v1,…,vn-1}的最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個部分權(quán)的和：三角形v0vkvn的權(quán)，子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn}的權(quán)之和。可以斷言，由T所確定的這2個子多邊形的三角剖分也是最優(yōu)的。因為若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖分將導致T不是最優(yōu)三角剖分的矛盾。26第二十六頁，共五十一頁，編輯于2023年，星期日最優(yōu)三角剖分的遞歸結(jié)構(gòu)定義t[i][j]，1≤i<j≤n為凸子多邊形{vi-1,vi,…,vj}的最優(yōu)三角剖分所對應的權(quán)函數(shù)值，即其最優(yōu)值。為方便起見，設退化的多邊形{vi-1,vi}具有權(quán)值0。據(jù)此定義，要計算的凸(n+1)邊形P的最優(yōu)權(quán)值為t[1][n]。t[i][j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計算。當j-i≥1時，凸子多邊形至少有3個頂點。由最優(yōu)子結(jié)構(gòu)性質(zhì)，t[i][j]的值應為t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的權(quán)值，其中i≤k≤j-1。由于在計算時還不知道k的確切位置，而k的所有可能位置只有j-i個，因此可以在這j-i個位置中選出使t[i][j]值達到最小的位置。由此，t[i][j]可遞歸地定義為：27第二十七頁，共五十一頁，編輯于2023年，星期日多邊形游戲多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點構(gòu)成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“+”或“*”。所有邊依次用整數(shù)從1到n編號。游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：(1)選擇一條邊E以及由E連接著的2個頂點V1和V2；(2)用一個新的頂點取代邊E以及由E連接著的2個頂點V1和V2。將由頂點V1和V2的整數(shù)值通過邊E上的運算得到的結(jié)果賦予新頂點。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點上的整數(shù)值。問題:對于給定的多邊形，計算最高得分。28第二十八頁，共五十一頁，編輯于2023年，星期日最優(yōu)子結(jié)構(gòu)性質(zhì)在所給多邊形中，從頂點i(1≤i≤n)開始，長度為j(鏈中有j個頂點)的順時針鏈p(i，j)可表示為v[i]，op[i+1]，…，v[i+j-1]。如果這條鏈的最后一次合并運算在op[i+s]處發(fā)生(1≤s≤j-1)，則可在op[i+s]處將鏈分割為2個子鏈p(i，s)和p(i+s，j-s)。設m1是對子鏈p(i，s)的任意一種合并方式得到的值，而a和b分別是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一種合并方式得到的值，而c和d分別是在所有可能的合并中得到的最小值和最大值。依此定義有a≤m1≤b，c≤m2≤d(1)當op[i+s]='+'時，顯然有a+c≤m≤b+d(2)當op[i+s]='*'時，有min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd}換句話說，主鏈的最大值和最小值可由子鏈的最大值和最小值得到。

29第二十九頁，共五十一頁，編輯于2023年，星期日圖像壓縮圖象的變位壓縮存儲格式將所給的象素點序列{p1,p2,…,pn},0≤pi≤255分割成m個連續(xù)段S1,S2,…,Sm。第i個象素段Si中(1≤i≤m)，有l(wèi)[i]個象素,且該段中每個象素都只用b[i]位表示。設則第i個象素段Si為設，則hib[i]8。因此需要用3位表示b[i],如果限制1l[i]255，則需要用8位表示l[i]。因此，第i個象素段所需的存儲空間為l[i]*b[i]+11位。按此格式存儲象素序列{p1,p2,…,pn}，需要位的存儲空間。

圖象壓縮問題要求確定象素序列{p1,p2,…,pn}的最優(yōu)分段，使得依此分段所需的存儲空間最少。每個分段的長度不超過256位。30第三十頁，共五十一頁，編輯于2023年，星期日圖像壓縮設l[i]，b[i](1≤i≤m)，是{p1,p2,…,pn}的最優(yōu)分段。顯而易見，l[1]，b[1]是{p1,…,pl[1]}的最優(yōu)分段，且l[i]，b[i](2≤i≤m)

，是{pl[1]+1,…,pn}的最優(yōu)分段。即圖象壓縮問題滿足最優(yōu)子結(jié)構(gòu)性質(zhì)。設s[i]，1≤i≤n，是象素序列{p1,…,pn}的最優(yōu)分段所需的存儲位數(shù)。由最優(yōu)子結(jié)構(gòu)性質(zhì)易知：其中算法復雜度分析：由于算法compress中對k的循環(huán)次數(shù)不超這256，故對每一個確定的i，可在時間O(1)內(nèi)完成的計算。因此整個算法所需的計算時間為O(n)。31第三十一頁，共五十一頁，編輯于2023年，星期日電路布線在一塊電路板的上、下2端分別有n個接線柱。根據(jù)電路設計，要求用導線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i)是{1,2,…,n}的一個排列。導線(i,π(i))稱為該電路板上的第i條連線。對于任何1≤i<j≤n，第i條連線和第j條連線相交的充分且必要的條件是π(i)>π(j)。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。換句話說，該問題要求確定導線集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。

32第三十二頁，共五十一頁，編輯于2023年，星期日記。N(i,j)的最大不相交子集為MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)當i=1時，(2)當i>1時，2.1j<π(i)。此時，。故在這種情況下，N(i,j)=N(i-1,j)，從而Size(i,j)=Size(i-1,j)。2.2j≥π(i)，(i,π(i))∈MNS(i,j)。則對任意(t,π(t))∈MNS(i,j)有t<i且π(t)<π(i)。在這種情況下MNS(i,j)-{(i,π(i))}是N(i-1,π(i)-1)的最大不相交子集。2.3若，則對任意(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)。電路布線(1)當i=1時(2)當i>1時33第三十三頁，共五十一頁，編輯于2023年，星期日流水作業(yè)調(diào)度n個作業(yè){1，2，…，n}要在由2臺機器M1和M2組成的流水線上完成加工。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成所需的時間最少。分析：直觀上，一個最優(yōu)調(diào)度應使機器M1沒有空閑時間，且機器M2的空閑時間最少。在一般情況下，機器M2上會有機器空閑和作業(yè)積壓2種情況。設全部作業(yè)的集合為N={1，2，…，n}。SN是N的作業(yè)子集。在一般情況下，機器M1開始加工S中作業(yè)時，機器M2還在加工其它作業(yè)，要等時間t后才可利用。將這種情況下完成S中作業(yè)所需的最短時間記為T(S,t)。流水作業(yè)調(diào)度問題的最優(yōu)值為T(N,0)。34第三十四頁，共五十一頁，編輯于2023年，星期日流水作業(yè)調(diào)度設是所給n個流水作業(yè)的一個最優(yōu)調(diào)度，它所需的加工時間為a(1)+T’。其中T’是在機器M2的等待時間為b(1)時，安排作業(yè)(2)，…，(n)所需的時間。記S=N-{(1)}，則有T’=T(S,b(1))。證明：事實上，由T的定義知T’T(S,b(1))。若T’>T(S,b(1))，設’是作業(yè)集S在機器M2的等待時間為b(1)情況下的一個最優(yōu)調(diào)度。則(1)，’(2)，…，’(n)是N的一個調(diào)度，且該調(diào)度所需的時間為a(1)+T(S,b(1))<a(1)+T’。這與是N的最優(yōu)調(diào)度矛盾。故T’T(S,b(1))。從而T’=T(S,b(1))。這就證明了流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。由流水作業(yè)調(diào)度問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，35第三十五頁，共五十一頁，編輯于2023年，星期日Johnson不等式對遞歸式的深入分析表明，算法可進一步得到簡化。設是作業(yè)集S在機器M2的等待時間為t時的任一最優(yōu)調(diào)度。若(1)=i,(2)=j。則由動態(tài)規(guī)劃遞歸式可得:T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-{i,j},tij)其中，如果作業(yè)i和j滿足min{bi,aj}≥min{bj,ai}，則稱作業(yè)i和j滿足Johnson不等式。36第三十六頁，共五十一頁，編輯于2023年，星期日流水作業(yè)調(diào)度的Johnson法則交換作業(yè)i和作業(yè)j的加工順序，得到作業(yè)集S的另一調(diào)度，它所需的加工時間為T’(S,t)=ai+aj+T(S-{i,j},tji)其中，當作業(yè)i和j滿足Johnson不等式時，有由此可見當作業(yè)i和作業(yè)j不滿足Johnson不等式時，交換它們的加工順序后，不增加加工時間。對于流水作業(yè)調(diào)度問題，必存在最優(yōu)調(diào)度，使得作業(yè)(i)和(i+1)滿足Johnson不等式。進一步還可以證明，調(diào)度滿足Johnson法則當且僅當對任意i<j有由此可知，所有滿足Johnson法則的調(diào)度均為最優(yōu)調(diào)度。

37第三十七頁，共五十一頁，編輯于2023年，星期日算法描述流水作業(yè)調(diào)度問題的Johnson算法(1)令(2)將N1中作業(yè)依ai的非減序排序；將N2中作業(yè)依bi的非增序排序；(3)N1中作業(yè)接N2中作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)度。算法復雜度分析：算法的主要計算時間花在對作業(yè)集的排序。因此，在最壞情況下算法所需的計算時間為O(nlogn)。所需的空間為O(n)。38第三十八頁，共五十一頁，編輯于2023年，星期日0-1背包問題給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?0-1背包問題是一個特殊的整數(shù)規(guī)劃問題。39第三十九頁，共五十一頁，編輯于2023年，星期日0-1背包問題設所給0-1背包問題的子問題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i，j)的遞歸式如下。算法復雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當背包容量c很大時，算法需要的計算時間較多。例如，當c>2n時，算法需要Ω(n2n)計算時間。40第四十頁，共五十一頁，編輯于2023年，星期日算法改進由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1≤i≤n)，函數(shù)m(i,j)是關于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點唯一確定。如圖所示。對每一個確定的i(1≤i≤n)，用一個表p[i]存儲函數(shù)m(i，j)的全部跳躍點。表p[i]可依計算m(i，j)的遞歸式遞歸地由表p[i+1]計算，初始時p[n+1]={(0，0)}。41第四十一頁，共五十一頁，編輯于2023年，星期日一個例子n=3，c=6，w={4，3，2}，v={5，2，1}。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)42第四十二頁，共五十一頁，編輯于2023年，星期日函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運算得到的。因此，函數(shù)m(i,j)的全部跳躍點包含于函數(shù)m(i+1，j)的跳躍點集p[i+1]與函數(shù)m(i+1，j-wi)+vi的跳躍點集q[i+1]的并集中。易知，(s,t)q[i+1]當且僅當wisc且(s-wi,t-vi)p[i+1]。因此，容易由p[i+1]確定跳躍點集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]}

另一方面，設(a，b)和(c，d)是p[i+1]q[i+1]中的2個跳躍點，則當ca且d<b時，(c，d)受控于(a，b)，從而(c，d)不是p[i]中的跳躍點。除受控跳躍點外，p[i+1]q[i+1]中的其它跳躍點均為p[i]中的跳躍點。由此可見，在遞歸地由表p[i+1]計算表p[i]時，可先由p[i+1]計算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點得到表p[i]。算法改進43第四十三頁，共五十一頁，編輯于2023年，星期日一個例子n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始時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)}。從跳躍點集p[5