算法設計與分析第四章動態(tài)規(guī)劃目錄概述（基本思想、解題步驟、基本要素）矩陣連乘問題凸多邊形最優(yōu)三角剖分最長公共子序列問題加工順序問題0-1背包問題最優(yōu)二叉查找樹教學目標理解動態(tài)規(guī)劃的思想掌握動態(tài)規(guī)劃、分治法及貪心法的異同掌握動態(tài)規(guī)劃的基本要素掌握動態(tài)規(guī)劃的設計步驟通過實例學習，掌握動態(tài)規(guī)劃設計的策略動態(tài)規(guī)劃應用應用領域：經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題。動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。

動態(tài)規(guī)劃動態(tài)規(guī)劃的基本思想。動態(tài)規(guī)劃解題步驟。動態(tài)規(guī)劃基本要素。矩陣連乘問題問題：給定n個矩陣{A1,A2,A3,…,An}，其中Ai與Ai+1(i=1,2,3,…,n-1)是可乘的。用加括號的方法表示矩陣連乘的次序，不同加括號的方法所對應的計算次序是不同的。找出一種最優(yōu)的計算次序，使得n個矩陣元素相乘的次數(shù)最小。實例：A1（10×100）、A2（100×5）、A3（5×50）窮舉算法A1(A2A3)乘法次數(shù)：100×50×5+10×50×100=75000(A1A2)A3乘法次數(shù)：10×5×100+10×50×5=7500窮舉算法是否可行？n個矩陣連乘，計算次序有多少種？（少則可行，太多則不可行）n=1，不用運算，1種計算次序n=2，有1種計算次序n=3，有2種計算次序n=4，A1|A2A3A4A1A2|A3A4

A1A2A3|A4

121121共5中計算次序窮舉算法是否可行？n=5，A1|A2A3A4A5

A1A2|A3A4A5

1512

A1A2A3|A4A5

A1A2A3A4|A52151共5+2+2+5=14種由此，我們可以得到計算次序數(shù)，用p(n)表示，則p(n)的表達式為：著名的Catalan數(shù)卡特蘭數(shù)是組合數(shù)學中一個常出現(xiàn)在各種計數(shù)問題中的數(shù)列。以比利時的數(shù)學家歐仁·查理·卡塔蘭(1814–1894)的名字來命名。Catalan數(shù)的定義令h(1)=1，Catalan數(shù)滿足遞歸式：h(n)=h(1)*h(n-1)+h(2)*h(n-2)+...+h(n-1)h(1)n>=2該遞推關(guān)系的解為：h(n)=C(2n-2,n-1)/n，n=1,2,3,...（其中C(2n-2,n-1)表示2n-2個中取n-1個的組合數(shù)）動態(tài)規(guī)劃算法n個矩陣連乘問題是最優(yōu)性質(zhì)的問題。把它劃分為與時間相關(guān)的多個階段規(guī)模為1時，不用運算，初始狀態(tài)，乘法次數(shù)為0第一個階段：依據(jù)初始狀態(tài)，計算2個矩陣相乘的最少乘法次數(shù)，做出決策。第二個階段：依據(jù)第一階段計算的結(jié)果計算3個矩陣相乘的最少乘法次數(shù)，做決策。以此類推，直到最后一個階段得到n個矩陣連乘最少計算次數(shù)，做決策。實例：求A1（3×2）、A2（2×5）、A3（5×10）、A4（10×2）和A5（2×3）最佳計算次序m[i][j]A1A2A3A4A5s[i][j]A1A2A3A4A5A1030160132150A101111A20100120132A20224A30100130A3034A4060A404A50A50A1|A2A3100+2×10×3=160A1A2|A330+3×5×10=180A2|A3A4100+5×2×2=120

A2A3|A4100+2×10×2=140A3|A4A560+10×3×5=210

A3A4|A5100+5×2×3=130A1|A2A3A4120+3×2×2=132A1A2|A3A430+100+5×2×3=160A1A2A3|A4160+3×10×2=220A2|A3A4A5130+2×5×3=160A2A3|A4A5100+60+2×10×3=220A2A3A4|A5120+2×2×3=132A1|A2A3A4A5132+3×2×3=150A1A2|A3A4A530+130+3×5×3=205A1A2A3|A4A5160++60+3×10×3=310A1A2A3A4|A5132+3×2×3=150A1（（A2（A3A4））A5）動態(tài)規(guī)劃的基本思想（1）經(jīng)分解得到的各個子問題往往不是相互獨立的。比如:A1A2A3與A2A3A4有共同的子問題A2A3（2）在求解過程中，將已解決的子問題的最優(yōu)值進行保存，在需要時可以輕松找出。（3）通常采用表的形式記錄子問題的最優(yōu)值，即在實際求解過程中，一旦某個子問題被計算過，不管該問題以后是否用得到，都將其計算結(jié)果填入該表，需要的時候就從表中找出該子問題的最優(yōu)值。（4）根據(jù)最優(yōu)值，記錄最優(yōu)決策，構(gòu)造最優(yōu)解。動態(tài)規(guī)劃的解題步驟（1）分析最優(yōu)解的性質(zhì)，刻畫最優(yōu)解的結(jié)構(gòu)特征——考察是否適合采用動態(tài)規(guī)劃法。（2）遞歸定義最優(yōu)值（即建立遞歸式或動態(tài)規(guī)劃方程）。（3）以自底向上的方式計算出最優(yōu)值，并記錄相關(guān)信息。（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造出最優(yōu)解。動態(tài)規(guī)劃的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)子問題重疊性質(zhì)自底向上的求解方式小結(jié)動態(tài)規(guī)劃的基本思想。動態(tài)規(guī)劃解題步驟。動態(tài)規(guī)劃基本要素。矩陣連乘最優(yōu)子結(jié)構(gòu)性質(zhì)分析設：Ai(pi×qi）設n個矩陣連乘的最佳計算次序為（A1A2…Ak）(Ak+1Ak+2…An)，則（A1A2…Ak）連乘的計算次序一定是最優(yōu)的，(Ak+1Ak+2…An)連乘的計算次序也一定是最優(yōu)的。反證法：假設（A1A2…Ak）連乘的計算次序不是最優(yōu)的，或(Ak+1Ak+2…An)連乘的計算次序不是最優(yōu)的。令a：（A1A2…Ak）連乘的乘法次數(shù)

b：（Ak+1Ak+2…An)連乘的乘法次數(shù)

c：（A1A2…Ak)(Ak+1Ak+2…An)連乘的乘法次數(shù)則c=a+b+p1qnqk由于a不是最小的或b不是最小的，則c肯定不是最小的，（A1A2…Ak)(Ak+1Ak+2…An)不是最優(yōu)決策，矛盾，故假設不真，兩個子問題的計算次序都是最優(yōu)的。建立最優(yōu)值的遞歸關(guān)系式描述子問題：AiAi+1…Aj，其中矩陣Am的行數(shù)為pm，列數(shù)為qm(m=i,i+1,…,j)描述子問題的最少乘法次數(shù)（最優(yōu)值）用i和j兩個參數(shù)描述問題規(guī)模設從k處分開為最優(yōu)決策m[i][j]：（AiAi+1…Ak)(Ak+1…Aj）連乘的乘法次數(shù)m[i][k]：AiAi+1…Ak的最佳計算次序?qū)某朔ù螖?shù)m[k+1][j]：Ak+1Ak+2…Aj的最佳計算次序?qū)某朔ù螖?shù)當i=j時，只有一個矩陣,故m[i][i]=0；當i<j時，m[i][j]=m[i][k]+m[k+1][j]+piqjqk把n個矩陣的行列存儲到數(shù)組P中：0123...n-2n-1np1q1q2q3......qn-2qn-1qn建立最優(yōu)值的遞歸關(guān)系式自底向上求解m[i][j]j=1j=2j=3j=...j=ns[i][j]j=1j=2j=3j=...j=ni=10i=10i=20i=20i=30i=30i=...0i=...0i=n0i=n0遞歸構(gòu)造最優(yōu)解算法分析計算最優(yōu)值：填寫二維表格n2，取最小n，故：O(n3)構(gòu)造最優(yōu)解：

解此遞歸式得T(n)=O(n)。小結(jié)矩陣連乘問題的動態(tài)規(guī)劃算法分析最優(yōu)子結(jié)構(gòu)性質(zhì)建立最優(yōu)值的遞歸關(guān)系式自底向上求解構(gòu)造最優(yōu)解時間復雜度分析凸多邊形最優(yōu)三角剖分基本概念凸多邊形：一個簡單多邊形及其內(nèi)部構(gòu)成一個閉凸集。凸多邊形三角剖分：將一個凸多邊形分割成互不相交的三角形的弦的集合，如{弦1，弦2，弦3}弦1弦2弦3凸多邊形三角剖分凸多邊形三角剖分唯一嗎？給定凸多邊形及定義在邊、弦構(gòu)成的三角形的權(quán)函數(shù)w(i,j,k)。最優(yōu)三角剖分：不同剖分方法所劃分的各三角形上權(quán)函數(shù)之和最小的三角剖分。三角形剖分的結(jié)構(gòu)（A1A2)(A3(A4A5))A1A2A3A4A5最優(yōu)子結(jié)構(gòu)性質(zhì)分析設v0vkvn是將n+1邊形P={v0,v1,…,vn}分成三部分{v0,v1,…,vk}、{vk,vk+1,…,vn}和{v0,vk,vn}的最佳剖分方法，那么凸多邊形{v0,v1,…,vk}的剖分一定是最優(yōu)的，{vk,vk+1,…,vn}的剖分也一定是最優(yōu)的。最優(yōu)子結(jié)構(gòu)性質(zhì)分析反證法：設凸多邊形{v0,v1,…,vk}的剖分不是最優(yōu)的或{vk,vk+1,…,vn}的剖分不是最優(yōu)的。令c：{v0,v1,…,vn}三角剖分的權(quán)函數(shù)之和a：{v0,v1,…,vk}三角剖分的權(quán)函數(shù)之和b：{vk,vk+1,…,vn}三角剖分的權(quán)函數(shù)之和w(v0vkvn)：三角形v0vkvn的權(quán)函數(shù)則c=a+b+w(v0vkvn)。w(v0vkvn)固定不變，根據(jù)假設知：a不是最小的或不是最小的，則c一定不是最小的，這說明c對應的{v0,v1,…,vn}的三角剖分不是最優(yōu)的，矛盾。建立最優(yōu)值的遞歸關(guān)系式描述子問題：vi-1vi…vj描述子問題的最優(yōu)值：m[i][j]表示vi-1vi…vj最優(yōu)三角剖分權(quán)函數(shù)之和m[i][k]表示vi-1vi…vk最優(yōu)三角剖分權(quán)函數(shù)之和m[k+1][j]表示vkvi…vj最優(yōu)三角剖分權(quán)函數(shù)之和當i=j時表示一條直線段，將其看作退化多邊形，其權(quán)函數(shù)為0。則自底向上求解定義三角形的權(quán)函數(shù)：defget_weight(i,j,k):ifk<n:returnweights[i][j]+weights[j][k]+weights[k][i]#計算最優(yōu)值并記錄最優(yōu)決策defMinest_weight_val(n):#n邊形的三角剖分問題相當于n-1個矩陣連乘問題。m=np.zeros((n,n))#存放最優(yōu)值s=np.zeros((n,n))#存放最優(yōu)決策foriinrange(1,n):m[i][i]=0s[i][i]=0forrinrange(2,n):foriinrange(1,n-r+1):j=i+r-1m[i][j]=m[i+1][j]+get_weight(i-1,i,j)s[i][j]=iforkinrange(i+1,j):t=m[i][k]+m[k+1][j]+get_weight(i-1,k,j)ift<m[i][j]:m[i][j]=ts[i][j]=kreturnm,s構(gòu)造最優(yōu)解res=[]defTraceback(i,j,s,res):ifi==j:returnelse:Traceback(i,int(s[i][j]),s,res)Traceback(int(s[i][j]+1),j,s,res)

res.append('v'+str(i-1)+',v'+str(j)+',v'+str(int(s[i][j])))小結(jié)基本概念分析了與矩陣連乘問題的聯(lián)系動態(tài)規(guī)劃解題步驟最優(yōu)子結(jié)構(gòu)性質(zhì)分析建立最優(yōu)值遞歸關(guān)系式自底向上求解最優(yōu)值，記錄相關(guān)信息根據(jù)相關(guān)信息構(gòu)造最優(yōu)解最長公共子序列問題基本概念（1）子序列給定序列X={x1,x2,…,xn}、Z={z1,z2,…,zk}，若Z是X的子序列，當且僅當存在一個嚴格遞增的下標序列{i1,i2,…,ik}，對j∈{1,2,…,k}有zj=xik如：X={A,B,C,B,D,A,B}{A,B}{B,C,A}{A,B,C,D,A}{B,B,C}（2）公共子序列給定序列X和Y，序列Z是X的子序列，也是Y的子序列，則稱Z是X和Y的公共子序列。X={A,B,C,B,D,A,B}Y={A,C,B,E,D,B}的公共子序列有：{A,B}{C,B,D}{A,C,B,D,B}（3）最長公共子序列包含元素最多的公共子序列即為最長公共子序列。

最長公共子序列問題最優(yōu)子結(jié)構(gòu)性質(zhì)分析設Zk={z1,z2,…,zk}是序列Xm={x1,x2,…,xm}和序列Yn={y1,y2,…,yn}的最長公共子序列。a)若zk=xm=yn，則Zk-1={z1,z2,…,zk-1}是Xm-1和Yn-1的最長公共子序列。證明：設Zk-1不是Xm-1和Yn-1的最長公共子序列，則對序列Xm-1和Yn-1來說，應該有它們的最長公共子序列，設其最長公共子序列為M。因此有：|Zk-1|<|M|。在Xm-1和Yn-1的最后均添加一個相同的字符zk=xm=yn，則Zk-1+{zk}和M+{zk}均是Xm和Yn的公共子序列。又由于|Zk-1+{zk}=Zk|<|M+{zk}|，故Zk不是Xm和Yn的最長公共子序列，與前提矛盾，假設不真。最優(yōu)子結(jié)構(gòu)性質(zhì)分析b)若xm≠yn,xm≠zk，則Zk是Xm-1和Yn的最長公共子序列。證明：設Zk不是Xm-1和Yn的最長公共子序列，則對序列Xm-1和Yn來說，應該有它們的最長公共子序列，設其最長公共子序列為M。由此有：|Zk|<|M|。在Xm-1的最后添加一個字符xm，則M也是Xm和Yn的公共子序列。又由于|Zk|<|M|，故Zk不是Xm和Yn的最長公共子序列，與前提矛盾，得證。最優(yōu)子結(jié)構(gòu)性質(zhì)分析c)若xm≠yn,yn≠zk，則Zk是Xm和Yn-1的最長公共子序列。證明：設Zk不是Xm和Yn-1的最長公共子序列，則對序列Xm和Yn-1來說，應該有它們的最長公共子序列，設其最長公共子序列為M。由此有：|Zk|<|M|。在Yn-1的最后添加一個字符yn，則M也是Xm和Yn的公共子序列。又由于|Zk|<|M|，故Zk不是Xm和Yn的最長公共子序列，與前提矛盾，得證。建立最優(yōu)值的遞歸關(guān)系式描述子問題：Xi、Yj描述最長公共子序列長度：c[i][j]自底向上填表求解，記錄相關(guān)信息根據(jù)相關(guān)信息構(gòu)造最優(yōu)解res=[]defprintLCS(s,A,i,j):if(i==0orj==0):return0ifs[i][j]==0:printLCS(s,A,i-1,j-1)res.append(A[i])elifs[i][j]==1:printLCS(s,A,i-1,j)else:printLCS(s,A,i,j-1)實例給定序列X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}，求它們的最長公共子序列。小結(jié)最長公共子序列問題最優(yōu)子結(jié)構(gòu)性質(zhì)分析建立最優(yōu)值遞歸關(guān)系式自底向上求解最優(yōu)值，記錄相關(guān)信息根據(jù)相關(guān)信息構(gòu)造最優(yōu)解實例加工順序問題問題：設有n個工件需要在機器M1和M2上加工，每個工件的加工順序都是先在M1上加工，然后在M2上加工。t1j、t2j分別表示工件j在M1、M2上所需的加工時間(j=1,2,…,n)。問應如何在兩機器上安排生產(chǎn)，使得第一個工件從在M1上加工開始到最后一個工件在M2上加工完所需的總加工時間最短？處理過程：最優(yōu)子結(jié)構(gòu)性質(zhì)分析整體最優(yōu)：將n個工件的集合看作N={1,2,…,n}，設(p1,p2,...,pn)是M1開始處理集合N時，機器M2經(jīng)過t時間才能夠停下來的最優(yōu)調(diào)度方案。子問題最優(yōu)：(p2,...,pn)是M1開始處理集合N-{p1}時，機器M2經(jīng)過max{t-t1p1,0}+t2p1時間才能夠停下來的最優(yōu)調(diào)度方案。證明：(p2,...,pn)不是M1開始處理集合N-{p1}時，機器M2經(jīng)過max{t-t1p1,0}+t2p1時間才能夠停下來的最優(yōu)調(diào)度方案。令T(S，t)：表示集合S中的工件開始在M1上加工時，機器M2需要t時間才能停下來到情況下所消耗的總加工時間。則：T(N，t)：調(diào)度方案(p1,p2,...,pn)總加工時間。T(N-{p1},max{t-t1p1,0}+t2p1)是(p2,...,pn)總加工時間。T(N,t)=t1p1+T(N-{p1},max{t-t1p1,0}+t2p1)由于T(N-{p1},max{t-t1p1,0}+t2p1)不是最小的所以T(N,t)肯定不是最小的，矛盾。建立最優(yōu)值的遞歸關(guān)系式子問題：M1開始處理集合S中的工件時，M2需要t時間停下來。整體最優(yōu)值T(S,t)子問題的最優(yōu)值T(S-{i},max{t-t1i,0}+t2i)遞歸關(guān)系式：自底向上求解最優(yōu)值方案1：先加工S中的i號工件，再加工j號工件，其它工件的加工順序為最優(yōu)調(diào)度順序。方案2：先加工S中的j號工件，再加工i號工件，其它工件的加工順序為最優(yōu)調(diào)度順序。自底向上求解若tij≤tji，則T(S,t)≤T'(S,t)，方案1優(yōu)于方案2若方案1優(yōu)于方案2，則T(S,t)≤T'(S,t)，tij≤tji方案1優(yōu)于方案2tij≤tji不等式兩邊同乘以-1方案2優(yōu)于方案1tji≤tij不等式兩邊同乘以-1Johnson-Bellman'sRule最優(yōu)加工順序的第i個和第j個要加工的工件，如果i<j，則必有如果加工工件i和j滿足min{t1j，t2i}大于等于min{t1i，t2j}不等式，稱加工工件i和j滿足JohnsonBellman‘sRule。滿足JohnsonBellman'sRule的加工順序方案為最優(yōu)方案。構(gòu)造最優(yōu)解算法步驟1：令N1={i|t1i<t2i},N2={i|t1it2i}；步驟2：將N1中工件按t1i非減序排序；將N2中工件按t2i非增序排序；步驟3：N1中工件接N2中工件，即N1N2就是所求的滿足JohnsonBellman'sRule的最優(yōu)加工順序

算法分析顯然，F(xiàn)lowShop算法的時間復雜性取決于Sort函數(shù)的執(zhí)行時間由于Sort函數(shù)的執(zhí)行時間為O(nlogn)，因此FlowShop算法的時間復雜性為O(nlogn)。小結(jié)最優(yōu)加工順序問題最優(yōu)子結(jié)構(gòu)性質(zhì)分析建立最優(yōu)值的遞歸關(guān)系分析貝爾曼法則根據(jù)貝爾曼法則設計2個算法分析算法時間復雜度0-1背包問題問題：n個物品和1個背包。對物品i，其價值為vi，重量為wi，背包的容量為W。如何選取物品裝入背包，使背包中所裝入的物品的總價值最大？物品不可分割。問題建模目標函數(shù)：約束條件：最優(yōu)子結(jié)構(gòu)性質(zhì)分析假設(x1,x2,…,xn)是0-1背包問題的一個最優(yōu)解，則(x1,x2,…,xn-1)是下面相應子問題的一個最優(yōu)解：目標函數(shù)：

約束條件：反證法證明：設(x1,…,xn-1)不是上述子問題的一個最優(yōu)解，而(y1,…,yn-1)是上述子問題的一個最優(yōu)解，則又最優(yōu)解向量(y1,…,yn-1)滿足：所以這說明(y1,y2,…,yn-1,xn)是原問題的一個解反證法證明：又這說明(x1,x2,…,xn)不是所給0-1背包問題的最優(yōu)解，與前提矛盾。故（x1,…,xn-1）是上述相應子問題的一個最優(yōu)解建立最優(yōu)值的遞歸關(guān)系式子問題：物品集為{1,2,...,i}，背包剩余容量為j子問題的最優(yōu)值：

則遞歸關(guān)系式：自底向上求解，記錄相關(guān)信息defknapsack(weight,value,capacity):#returnmaxvalueweight.insert(0,0)#前0件要用value.insert(0,0)#前0件要用num=len(weight)bag_value=np.zeros((num,capacity+1),dtype=32)#下標從零開始foriinrange(1,num):forjinrange(1,capacity+1):ifweight[i]<=j:bag_value[i][j]=max(bag_value[i-1][j-weight[i]]+value[i],bag_value[i-1][j])else:bag_value[i][j]=bag_value[i-1][j]returnbag_value構(gòu)造最優(yōu)解defshow(n,capacity,weight,bag_value):print('最大價值為:',bag_value[n][capacity])x=[0foriinrange(n)]j=capacityforiinrange(n,0,-1):ifbag_value[i][j]>bag_value[i-1][j]:x[i-1]=1j-=weight[i-1]實例有5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10，物品不可分割，求裝入背包的物品和獲得的最大價值。012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515算法時間復雜度分析填寫二維表格：耗時O(nW)循環(huán)二維表中的每個元素，要么由c[i-1][j]得到，要么由c[i-1][j-wi]+vi計算得到，耗時O(1)。所以：算法的時間復雜度為O(nW)。缺點：（1）算法要求所給物品的重量wi是整數(shù)；（2）當背包容量W很大時，算法需要的計算時間較多，例如，當W>2n時，算法需要O(n2n)的計算時間。小結(jié)：0-1背包問題最優(yōu)子結(jié)構(gòu)性質(zhì)分析建立最優(yōu)值的遞歸關(guān)系自底向上求解構(gòu)造最優(yōu)解分析算法時間復雜度及缺點改進算法——跳躍點算法函數(shù)c[i][j]是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)遞歸關(guān)系式p[0]={(0,0)}q[i-1]=p[i-1]+(wi,vi)i=1,2,...,np[i]=q[i-1]∪p[i-1]改進步驟（a）對每一個確定的i，用一個表p[i]來存儲函數(shù)C[i][j]的全部跳躍點并按照j升序排列。（b）p[i]可通過計算p[i-1]得到。（c）清除受控點：j大，但價值小的點。（d）由此可得，在遞歸地由p[i-1]計算p[i]時，可先由p[i-1]計算出q[i-1]，然后合并p[i-1]和q[i-1]，并清除其中的受控跳躍點得到p[i]。改進后算法的計算時間復雜性為O(min{nW，2n})

實例：5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10p[0]={(0，0)}。q[0]={(2，6)}p[1]={(0，0)，(2，6)}q[1]={(2，3)，(4，9)}p[2]={(0，0)，(2，6)，(2，3)，(4，9)}q[2]={(6，5)，(8，11)，(10，14)}p[3]={(0，0)，(2，6)，(4，9)，(6，5)，(8，11)，(10，14)}實例：5個物品，其重量分別為2,2,6,5,4，價值分別為6,3,5,4,6。背包容量為10q[3]={(5，4)，(7，10)，(9，13)，(13，15)，(15，18)}p[4]={(0，0)，(2，6)，(4，9)，(5，4)，(7，10)，(8，11)，(9，13)，(10，14)}q[4]={(4，6)，(6，12)，(8，15)，(11，16)，(12，17)，(13，19)，(14，20)}p[5]={(0，0)，(2，6)，(4，9)，(4，6)，(6，12)，(7，10)，(8，11)，(8，15)，(9，13)，(10，14)}代碼：計算P[]defknapsack_improve(weight,value,capacity):iflen(weight)!=len(value):print("parametererr!")returnobj_num=len(weight)jump_points_p=[[]forxinrange(obj_num+1)]jump_points_q=[[]forxinrange(obj_num+1)]jump_points_p[0].append((0,0))foriinrange(1,obj_num+1):jump_points_q[i-1]=[(point[0]+weight[i-1],point[1]+value[i-1])forpointinjump_points_p[i-1]ifpoint[0]+weight[i-1]<=capacity]jump_points_p[i]=merge_points(jump_points_p[i-1],jump_points_q[i-1])returnjump_points_p構(gòu)造最優(yōu)解defshow(obj_num,weight,value,jump_points_p):vector=[0forxinrange(obj_num)]point=jump_points_p[5][len(jump_points_p[5])-1]foriinrange(obj_num,0,-1):temp_point=(point[0]-weight[i-1],point[1]-value[i-1])iftemp_pointinjump_points_p[i-1]:vector[i-1]=1point=temp_pointreturnvector小結(jié)0-1背包問題的跳躍點算法p[0]={(0,0)}q[i-1]=p[i-1]+(wi,vi)i=1,2,...,np[i]=q[i-1]∪p[i-1]算法的復雜度為min(nW,2n)最優(yōu)二叉搜索樹基本概念：二叉搜索樹給定n個關(guān)鍵字組成的有序序列S={s1,s2,…,sn},構(gòu)造一棵左子樹比根節(jié)點小，右子樹比根節(jié)點大的二叉樹，該二叉樹成為二叉搜索樹。如{s1,s2,s3}的二叉搜索樹：最優(yōu)二叉查找樹在二叉搜索樹中查找指定關(guān)鍵字k時，有可能查找成功，有可能查找不成功。查找不成功時均是到達樹節(jié)點的空指針，將空指針看作樹的虛節(jié)點ei，e0表示小于s1的所有值，en表示大于sn所有值，其他ei表示(si,si+1)思考：n個關(guān)鍵字的有序序列，二叉搜索樹共有幾個虛節(jié)點？n+1最優(yōu)二叉查找樹給定S={s1,s2,...,sn}的查找概率(p1,p2,...,pn)和虛節(jié)點{e0,e1,...,en}的概率(q1,q2,...,qn)，且滿足：平均查找次數(shù)：思考：n個關(guān)鍵字的有序序列，二叉搜索樹共有幾棵？最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹是在所有表示有序序列S的二叉搜索樹中，具有最小平均比較次數(shù)的二叉搜索樹。在查找概率相等時：深度最小的二叉查找樹為最優(yōu)二叉搜索樹。查找概率不等時：最優(yōu)二叉樹并不一定是深度最小的二叉搜索樹。最優(yōu)子結(jié)構(gòu)性質(zhì)分析T(1,n)：實結(jié)點{s1,s2,…,sn}和虛結(jié)點{e0,e1,…,en}構(gòu)成的二叉搜索樹。設定元素sk作為該樹的根結(jié)點，1≤k≤n。左子樹T(1,k-1)：實結(jié)點{s1,…,sk-1}和虛結(jié)點e0,…,ek-1組成。右子樹T(k+1,n)：實結(jié)點{sk+1,…,sn}和虛結(jié)點ek,…,en組成。整體最優(yōu)：如果T(1,n)是最優(yōu)二叉查找樹，則子問題最優(yōu)：左子樹T(1,k-1)和右子樹T(k+1,n)也是最優(yōu)二叉查找樹。證明：（反證法）假設左子樹T(1,k-1)不是最優(yōu)二叉搜索樹。最優(yōu)子結(jié)構(gòu)性質(zhì)分析<建立最優(yōu)值的遞歸關(guān)系式子問題：有序序列{si,si+1,...,sj},虛節(jié)點{ei-1,ei,...,ej}假設sk為樹根是最優(yōu)決策，則左子樹：有序序列{si,si+1,...,sk-1},虛節(jié)點{ei-1,ei