1、期末復習期末復習題型題型 選擇題（選擇題（10分）分） 填空題（填空題（10分）分） 算法應用題（算法填空，簡單問題回答）算法應用題（算法填空，簡單問題回答）（3-4個題，個題，35-40分）分） 算法設計（按照已知條件設計算法或為算算法設計（按照已知條件設計算法或為算法補充完整）（法補充完整）（3個題，個題，45-50分）分）第第1章章 算法的性質及其與程序的區(qū)別算法的性質及其與程序的區(qū)別 算法復雜性分析算法復雜性分析 漸進意義下的四種記號漸進意義下的四種記號 簡單的程序段的復雜度分析簡單的程序段的復雜度分析算法的五個重要特征輸入輸入 有有零個或多個零個或多個由外部提供的量作為算法的輸入由外

2、部提供的量作為算法的輸入輸出輸出 算法產生算法產生至少一個量至少一個量作為輸出作為輸出.確定性確定性 組成算法的每條指令是清晰的組成算法的每條指令是清晰的,無歧義的無歧義的.有限性有限性 在執(zhí)行了有窮步驟后運算終止在執(zhí)行了有窮步驟后運算終止可行性可行性 運算都是基本運算，原理上能在有限時間內完成。運算都是基本運算，原理上能在有限時間內完成。漸進意義下的記號：O, f(N)和和g(N)是定義在正整數(shù)上的正函數(shù)是定義在正整數(shù)上的正函數(shù)定義定義1.1 1.1 如果存在兩個正常數(shù)如果存在兩個正常數(shù)c和和N0,對于所有的對于所有的NN0，有有f(N) Cg(N)，則記作：，則記作：f(N)= O(g(N

3、)。N0f(N)g(N)當說一個算法具有當說一個算法具有O(g(n)的計算時間時，指的的計算時間時，指的就是如果此算法用就是如果此算法用n值不變的同一類數(shù)據(jù)在某臺值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是小于機器上運行時，所用的時間總是小于g(n)的一個的一個常數(shù)倍。常數(shù)倍。g(n)是計算時間是計算時間f(n)的一個上界函數(shù)，的一個上界函數(shù)，f(n)的數(shù)的數(shù)量級就是量級就是g(n)符號符號的定義的定義 定義定義1.2 如果存在兩個正常數(shù)如果存在兩個正常數(shù)C和自然數(shù)和自然數(shù)N0，使得當使得當N N0時有時有f(N)Cg(N)，則稱函數(shù)，則稱函數(shù)f(N)當當N充分大時下有界；且充分大時下

4、有界；且g(N)是它的一個下界，是它的一個下界，記為記為f(N)=(g(N)。這時我們說。這時我們說f(N)的階不低的階不低于于g(N)的階。的階。 ，o 的定義 定義定義f(N)= (g(N)當且僅當當且僅當f(N)=O(g(N)且且f(N)=(g(N)。這時，我們說。這時，我們說f(N)與與g(N)同階同階 o 如果對于任意給定的如果對于任意給定的0，都存在正整數(shù)，都存在正整數(shù)N0，使得當使得當N N0時有時有f(N)/g(N)，則稱函數(shù)，則稱函數(shù)f(N)當當N充分大時的階比充分大時的階比g(N)低，記為低，記為f(N)=o(g(N) 例如：例如：4NlogN+7=o(3N2+4NlogN

5、+7)1.2 算法分析初步多項式時間算法多項式時間算法(polynomial time algorithm):可用多項式可用多項式來對其計算時間限界的來對其計算時間限界的算法算法O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時間算法指數(shù)時間算法(exponential time algorithm):計算時間用計算時間用指數(shù)函數(shù)限界的算法指數(shù)函數(shù)限界的算法O(2n)O(n!)O(nn) 作業(yè)作業(yè)1-7第第2章章 遞歸遞歸 分治法基本思想分治法基本思想 二分搜索算法二分搜索算法 Strassen矩陣乘法矩陣乘法 合并排序和快速排序合并排序和快速排序遞歸復雜度分析漢諾塔移動

6、次數(shù)M(1)=1M(n)=2M(n-1)+1 = 22M(n-2)+1+1 = 22M(n-2)+2+1 = 23M(n-3)+22+2+1 = =2iM(n-i)+2i-1+2i-2+2+1 =2iM(n-i)+2i - 1令令i= n -1 則則M(n)= 2n-1 + 2n-1-1=2n-12.1 遞歸遞歸分治法的基本思想分治法的基本思想分而治之方法與軟件設計的模塊化方法非常分而治之方法與軟件設計的模塊化方法非常相似。為了解決一個大的問題，可以：相似。為了解決一個大的問題，可以： l 把它分成兩個或多個更小的問題；把它分成兩個或多個更小的問題； l 分別解決每個小問題；分別解決每個小問題

7、； l 把各小問題的解答組合起來，即可得到原把各小問題的解答組合起來，即可得到原問題的解答。小問題通常與原問題相似，問題的解答。小問題通常與原問題相似，可以遞歸地使用分而治之策略來解決?？梢赃f歸地使用分而治之策略來解決。例例2-6 在在9,12,15,27,39中分別查找中分別查找27，12，149 12 15 27 390 1 2 3 4 left right midmid = (left+right)/2=(0+4)/2=2mid =(3+4)/2=39 12 15 27 39leftrightmid查找查找27成功返成功返回回3，leftrightmid9 12 15 27 39left

8、righttemplate BinarySearch( , ) /在在a0=a1=amiddle) left= ; else right= ; return 1; /未找到未找到x當當n1時，時，Tw(n)= Tw(n/2)+1, T(1) = 1Tw(n) = Tw(n/2) + 1 = Tw(n/4) +1 +1 =Tw(1)+1+.+1=1+k=1+logn二分搜索的時間復雜度 最壞情況下的成功檢索計算時間最壞情況下的成功檢索計算時間(logn) 最壞情況下的不成功檢索計算時間最壞情況下的不成功檢索計算時間(logn) 最好情況下的成功檢索計算時間最好情況下的成功檢索計算時間(1) 最好

9、情況下的不成功檢索計算時間最好情況下的不成功檢索計算時間(logn) 每種不成功的檢索時間都為每種不成功的檢索時間都為(logn)2.2二分搜索技術二分搜索技術作業(yè)： P34，2-2 中第二個和第中第二個和第五個算法的正確性，錯誤五個算法的正確性，錯誤的說明原因或者給出反例的說明原因或者給出反例 2. P35, 2-32-3：二分搜索中當程序停止時，左右指針或者指向同一個元素，此時該元素等于待查找元素或者left=right+1，此時right指向的為比待找元素小的元素，left為比待找元素大的元素 歸并排序主程序偽代碼歸并排序主程序偽代碼templatevoid MergeSort(Type

10、 a , int left, int right)/ Aleft:right是一個全程數(shù)組，含有是一個全程數(shù)組，含有 right-left+1個待排個待排序的元素。序的元素。 if ( ) /至少有至少有2個元素個元素 int mid = (left+right)/2; /求當前數(shù)組的分割點求當前數(shù)組的分割點 MergeSort(a，left, mid); MergeSort(a，mid+1, right); Merge(a，b，left, mid ,right); copy（a，b，left，right）；）； left right遞歸調用，分別對分遞歸調用，分別對分解出來的兩個子問題解出來

11、的兩個子問題排序排序合并兩個排好序的子合并兩個排好序的子問題，放入另一個數(shù)問題，放入另一個數(shù)組組b中中2.4合并排序合并排序考慮數(shù)組a的兩段為1, 7, 8, 9和2, 3, 4, 51,7,8,92,3,4,51,7,8,92,3,4,511,21,7,8,92,3,4,51,2,31,7,8,92,3,4,51,2,3,41,7,8,92,3,4,51,2,3,4,5數(shù)組數(shù)組a的兩部分的兩部分數(shù)組數(shù)組b1,2,3,4,5,71,2,3,4,5,7,81,2,3,4,5, 7,8,9在移動掃描指針的同時，在移動掃描指針的同時，要判斷其是否已經(jīng)到達數(shù)要判斷其是否已經(jīng)到達數(shù)組的尾部，如到達，則停

12、組的尾部，如到達，則停止掃描，把未參加排序的止掃描，把未參加排序的數(shù)全部放入備用數(shù)組中數(shù)全部放入備用數(shù)組中2.4合并排序合并排序合并函數(shù)templatevoid Merge( Type a , Type b , int l, int m, int r)/合并合并al:m和和am+1:r到到bl:r int i=l; j=m+1, k=l; while( ( )&( ) ) if( a i m ) for( int q=j; q=r; q+ ) b k+ =a q ; else for( int q=I; q=m; q+) b k+ =a q ;把把al:m和和am+1:r中的數(shù)中的數(shù)據(jù)進行比較

13、，按順據(jù)進行比較，按順序放入序放入b中中如果前一段數(shù)據(jù)如果前一段數(shù)據(jù)小于后一段的多，小于后一段的多，則先排完，把后則先排完，把后段剩余數(shù)賦給段剩余數(shù)賦給bn,否則將前段否則將前段數(shù)據(jù)賦給數(shù)據(jù)賦給bn前半段指針前半段指針后半段指針后半段指針數(shù)組數(shù)組b的下標指針的下標指針i=mj=r2.4合并排序合并排序作業(yè) 分析分析merge函數(shù)最好與最壞的鍵值比較次函數(shù)最好與最壞的鍵值比較次數(shù)。數(shù)。最好比較最好比較1次次最差比較最差比較m+n-1，m和和n分別為兩段數(shù)組的長度分別為兩段數(shù)組的長度快速排序Templatevoid QuickSort(Type a , int p,int r) if(pr) in

14、t q=Partition(a,p,r); QuickSort(a,p,q-1);/對左半段排序 QuickSort(a,q+1,r);/對右半段排序 a的起始位的起始位置置A的終止位置的終止位置Partition函數(shù)負責將函數(shù)負責將a進行一次分割，返進行一次分割，返回分割元素的位置回分割元素的位置快速排序問題快速排序問題劃分程序 templateint Partition(Type a ,int p,int r) int i = , j = ; Type x = ; while( true ) while( a +i x ); if( ) break; Swap( a i , a j );

15、a p = ; a j = ; return j;快速排序問題快速排序問題pr+1a p i = ja j x左側掃描指針起左側掃描指針起始始右側掃描指針起右側掃描指針起始始中軸元素中軸元素移動左側掃描指移動左側掃描指針針移動右側掃描指針移動右側掃描指針算法分析算法分析 最壞情況：劃分的兩個區(qū)域分別包含最壞情況：劃分的兩個區(qū)域分別包含n1個元素和個元素和1個元素，如果每一步都出現(xiàn)這種個元素，如果每一步都出現(xiàn)這種情況，其復雜性情況，其復雜性T(n) O(1) n1 T(n)= T(n-1)+O(n) n1解得：解得：T(n)=O(n2)快速排序問題快速排序問題 最好情況最好情況 每次劃分所取的基

16、準都恰好為中值，即每每次劃分所取的基準都恰好為中值，即每次劃分都產生兩個大小為次劃分都產生兩個大小為n/2的區(qū)域，的區(qū)域， O(1) n1 T(n)= 2T(n/2)+O(n) n1T(n)=O(nlogn)快速排序問題快速排序問題 2-19 將算法Partition中的不等號反向第第3章章 動態(tài)規(guī)劃思想，基本要素動態(tài)規(guī)劃思想，基本要素 矩陣連乘算法及最優(yōu)解構造矩陣連乘算法及最優(yōu)解構造 0-1背包問題最優(yōu)值及最優(yōu)解背包問題最優(yōu)值及最優(yōu)解 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹（通過具體實例弄清每個算法的流程及算法（通過具體實例弄清每個算法的流程及算法的具體實現(xiàn)）的具體實現(xiàn)）動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法 將待

17、求解的問題分解成若干個子問題，將待求解的問題分解成若干個子問題，先求解子問題，并存儲子問題的解先求解子問題，并存儲子問題的解而而避免計算重復的子問題避免計算重復的子問題，再由子，再由子問題的解得到原問題的解。問題的解得到原問題的解。算法思想算法思想動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素1 最優(yōu)子結構性質最優(yōu)子結構性質2 重疊子問題性質重疊子問題性質1. 最優(yōu)子結構最優(yōu)子結構 當問題的最優(yōu)解包含了其子問題的最優(yōu)解當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有時，稱該問題具有最優(yōu)子結構性質最優(yōu)子結構性質。 分析最優(yōu)子結構性質時，一般假設由問題分析最優(yōu)子結構性質時，一般假設由問題的最優(yōu)解

18、導出的子問題不是最優(yōu)的，然后的最優(yōu)解導出的子問題不是最優(yōu)的，然后再設法說明在這個假設下可以構造出一個再設法說明在這個假設下可以構造出一個比原問題更優(yōu)解更好的解，從而導出矛盾。比原問題更優(yōu)解更好的解，從而導出矛盾。動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素2.重疊子問題重疊子問題 在用遞歸算法自頂向下解此問題時，每次在用遞歸算法自頂向下解此問題時，每次產生的子問題并不總是新問題，有些子問產生的子問題并不總是新問題，有些子問題被反復計算多次。動態(tài)規(guī)劃算法對每個題被反復計算多次。動態(tài)規(guī)劃算法對每個問題只解一次，而后將其解保存在一個表問題只解一次，而后將其解保存在一個表格中，當再次需要解此問題時，用

19、常數(shù)時格中，當再次需要解此問題時，用常數(shù)時間查看一下結果。因此，用動態(tài)規(guī)劃算法間查看一下結果。因此，用動態(tài)規(guī)劃算法通常只需要多項式時間。通常只需要多項式時間。動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素 都是分解成子問題，由子問題的解得到原都是分解成子問題，由子問題的解得到原問題的解。問題的解。 分治中子問題相互獨立，而動態(tài)規(guī)劃中子分治中子問題相互獨立，而動態(tài)規(guī)劃中子問題互相有聯(lián)系，且存在重復計算，即存問題互相有聯(lián)系，且存在重復計算，即存在在。動態(tài)規(guī)劃算法設計步驟動態(tài)規(guī)劃算法設計步驟（1）找出最優(yōu)解的性質，刻畫其結構特征）找出最優(yōu)解的性質，刻畫其結構特征（2）遞歸地定義最優(yōu)值）遞歸地定義最優(yōu)值

20、（3）以自底向上的方式計算出最優(yōu)值）以自底向上的方式計算出最優(yōu)值（4）根據(jù)計算最優(yōu)值時得到的信息，構造一）根據(jù)計算最優(yōu)值時得到的信息，構造一個最優(yōu)解個最優(yōu)解矩陣連乘問題矩陣連乘問題給定給定n個矩陣個矩陣A1, A2, , An，其中，其中Ai 是是一個一個ri-1ri 矩陣矩陣( 1in)，即，即AiAi+1是是可乘的，求出可乘的，求出n個矩陣相乘的最優(yōu)計算個矩陣相乘的最優(yōu)計算次序，使得計算量最小。次序，使得計算量最小。問題提出問題提出設三個矩陣設三個矩陣A1, A2, A3大小分別為大小分別為10100，1005，550，考慮，考慮(A1( A2 A3), (A1A2) A3的的結果與相乘的

21、次數(shù)。結果與相乘的次數(shù)。最優(yōu)子結構特征最優(yōu)子結構特征 計算計算A1:n的一個最優(yōu)次序所包含的計算的一個最優(yōu)次序所包含的計算矩陣子鏈矩陣子鏈A1:k和和Ak+1:n的次序也是最優(yōu)的次序也是最優(yōu)的的 矩陣連乘積計算次序問題的最優(yōu)解包含著矩陣連乘積計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解，也就是最優(yōu)子結構性其子問題的最優(yōu)解，也就是最優(yōu)子結構性質。質。矩陣連乘問題矩陣連乘問題考慮考慮A1:k 和和Ak+1:n相乘所需的相乘所需的計算量，計算量，A i: k 和和A k+1:j 相乘呢相乘呢A1:k 的結果為的結果為r0*rk的的矩陣，矩陣，Ak+1:n的結果的結果為為rk*rn的矩陣，則它們的矩陣，

22、則它們相乘的計算量為相乘的計算量為p0*pk*pn2.建立遞歸關系建立遞歸關系 設計算設計算A i: j 所需的最少次數(shù)為所需的最少次數(shù)為mij,原問題的最優(yōu)原問題的最優(yōu)解為解為m1n。 當當 i = j 時，時，A i : j = Ai ,m i i = 0,i=1,2,n。 當當 i j 時時m i j =m i k + m k+1 j + pi-1pkpj k i, i+1, , j-1 jipppjkmkimjijimjkijki1min01矩陣連乘問題矩陣連乘問題采用遞歸方法計算采用遞歸方法計算int RecurMatrixChain( int i, int, j, int p) i

23、f ( ) return 0; int u=RecurMatrixChain(i, i)+RecurMatrixChain(i+1,j,p) +pi-1*pi*pj; sij=i; for(int k=i+1; kj; k+) int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j,p) +pi-1*pi*pj; if (tu) u=t; sij=k; return u;參加運算矩陣鏈起始位置參加運算矩陣鏈起始位置矩陣鏈終止位置矩陣鏈終止位置i=j取第一個斷開位取第一個斷開位置時計算量置時計算量記記錄錄當當前前斷斷開開位位置置循環(huán)取循環(huán)取k的可取的

24、可取斷開位置斷開位置矩陣連乘問題矩陣連乘問題遞歸樹遞歸樹1411241234134422 342344 11 22 33 441123 12333344223322 33 11 22矩陣連乘問題矩陣連乘問題24223412334411141323矩陣連乘問題矩陣連乘問題3.計算最優(yōu)值計算最優(yōu)值3.計算最優(yōu)值計算最優(yōu)值 置所有只有一個矩陣的矩陣鏈計算量為置所有只有一個矩陣的矩陣鏈計算量為0，即，即mii=0， i=1,2,n。 通過上一步的結果可以得到所有矩陣鏈長度為通過上一步的結果可以得到所有矩陣鏈長度為2的的子問題的最優(yōu)計算量。子問題的最優(yōu)計算量。 通過上兩步的結果可以得到所有矩陣鏈長度為通

25、過上兩步的結果可以得到所有矩陣鏈長度為3的的子問題的最優(yōu)計算量子問題的最優(yōu)計算量 矩陣連乘問題矩陣連乘問題計算計算m i j 時，只用到已計算出的時，只用到已計算出的m i k 和和m k+1 j A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025例例32設要計算矩陣連乘積設要計算矩陣連乘積A1A2A3A4A5A6 ,其中各矩陣的維數(shù)分別為其中各矩陣的維數(shù)分別為 1 2 3 4 5 6 00000015750262575010005000 m11 + m23+p0p1p3=7875m13=min m12 + m33 + p0p2p3=1575093751

26、18751512543757125105002500537535007875ij3.計算最優(yōu)值計算最優(yōu)值void MatrixChain(int p, int n, int * *m, int * *s) for (int i=1; i=n; i+) mii= ;/單個矩陣的計算量單個矩陣的計算量 for (int r=2; r=n; r+)/r為每次循環(huán)矩陣鏈的長度為每次循環(huán)矩陣鏈的長度 for (int i=1; i= ; i+) int j=i+r-1; mij= mi+1j+pi-1*pi*pj; sij=i; for (int k=i+1; kj; k+) int t= mik+ m

27、k+1j+ ; if (t mij) mij=t; sij=k; 矩陣連乘問題矩陣連乘問題0n r + 1取第一個可取第一個可取位置，即取位置，即斷開位置為斷開位置為i循環(huán)取循環(huán)取k的可取的可取位置位置pi-1*pk*pj算法復雜度算法復雜度 算法算法MatrixChain 的主要計算量取決于程的主要計算量取決于程序中對序中對r, i 和和k 的三重循環(huán)，的三重循環(huán)， 循環(huán)體內的計算量為循環(huán)體內的計算量為O(1)，三重循環(huán)的總，三重循環(huán)的總次數(shù)是次數(shù)是O(n3)，所以，算法的計算時間上界，所以，算法的計算時間上界為為O(n3)。4. 構造最優(yōu)解構造最優(yōu)解 上述算法只是明確給出了矩陣最優(yōu)連乘次上

28、述算法只是明確給出了矩陣最優(yōu)連乘次序所用的數(shù)乘次數(shù)序所用的數(shù)乘次數(shù)m1n，并未明確給出，并未明確給出最優(yōu)連乘次序，即完全加括號方法。但是最優(yōu)連乘次序，即完全加括號方法。但是以以sij為元素的為元素的2 維數(shù)組卻給出了足夠的維數(shù)組卻給出了足夠的信息。事實上，信息。事實上，sij=k說明，計算連乘積說明，計算連乘積Ai:j的最佳方式應該在矩陣的最佳方式應該在矩陣Ak 和和Ak+1 之之間斷開，即最優(yōu)加括號方式為間斷開，即最優(yōu)加括號方式為(Ai:k)(Ak+1:j)。 1 2 3 4 5 60 1 1 3 3 3 0 2 3 3 3 0 3 3 3 0 4 5 0 51 0考慮計算考慮計算A16時的

29、順序時的順序S16 (A1A3) (A4A6)S13 A1(A2A3)S46 (A4A5) A6S11=0 S23=0 A1(A2)(A3)S22= S33= 0 S66=0 S45=0 (A4)(A5) A6S44= S55= 0 根據(jù)最優(yōu)值算法構造最優(yōu)解根據(jù)最優(yōu)值算法構造最優(yōu)解Void Traceback(int i, int j, int * * s) if (i=j) return; Traceback(i, sij, s); Traceback(sij+1, j, s); cout “Multiply A” i “,” sij; cout “and A” (sij +1) “,” j

30、; endl; 調用調用Traceback(1, n, s)即可得到即可得到A1:n 作業(yè)作業(yè) 1 當當A1 A2 A3 A4 A5 分別為分別為2025， 2510，105，515，1520的矩陣時，填寫相的矩陣時，填寫相應的應的mij和和sij，并給出最優(yōu)計算次序。，并給出最優(yōu)計算次序。備忘錄方法備忘錄方法 用一個表格來保存已解決的子問題的答案，用的用一個表格來保存已解決的子問題的答案，用的時候查表即可。時候查表即可。 采用的遞歸方式是采用的遞歸方式是自頂向下自頂向下，動態(tài)規(guī)劃是，動態(tài)規(guī)劃是自低向自低向上上 控制結構與直接遞歸相同，區(qū)別在于備忘錄方式控制結構與直接遞歸相同，區(qū)別在于備忘錄方

31、式為每個解過的子問題建立備忘錄。為每個解過的子問題建立備忘錄。 初始化為每個子問題的記錄存入一個特殊的值，初始化為每個子問題的記錄存入一個特殊的值，表示并未求解。在求解過程中，查看相應記錄如表示并未求解。在求解過程中，查看相應記錄如果是特殊值，表示未求解，否則只要取出該子問果是特殊值，表示未求解，否則只要取出該子問題的解答即可。題的解答即可。動態(tài)規(guī)劃算法的基本要素動態(tài)規(guī)劃算法的基本要素備忘錄方法解矩陣乘備忘錄方法解矩陣乘int MemoizedMatrixChain(int n,int *m,int *s) for(int i=1;i=n;i+) for(int j=i;j0) return

32、mij; if(i=j) return 0; int u=LookupChain(i,i)+LookupChain(i+1,j) +pi-1*pk*pj; sij=i; for(int k=i+1;kj;k+) int t=LookupChain(i,k) +LookupChain(k+1,j) +pi-1*pk*pj; if(t0，其價值為，其價值為vi0，背包的容量為，背包的容量為c。問。問應如何選擇裝入背包中的物品，使得裝入應如何選擇裝入背包中的物品，使得裝入背 包 中 物 品 的 總 價 值 最 大 ？背 包 中 物 品 的 總 價 值 最 大 ？要求一組數(shù)要求一組數(shù)i (i = 0

33、= 0 或或，i = 0= 0表示表示物體物體不放入背包，不放入背包，i 1表示把表示把物體物體放入背包），放入背包），使得使得 vixi 最大，即將盡量多的價值裝入背包。最大，即將盡量多的價值裝入背包。1 i n1. 最優(yōu)子結構性質最優(yōu)子結構性質證明證明0/1 背包問題具有最優(yōu)子結構性質背包問題具有最優(yōu)子結構性質即若背包容量為即若背包容量為c時，時，(y1, y2, yn )為待選物品為為待選物品為1到到n時時knap(1, n, c)的最優(yōu)解，則的最優(yōu)解，則(y2, yn )將是物品將是物品1作出作出選 擇 后 的 子 問 題選 擇 后 的 子 問 題 的 最 優(yōu) 解的 最 優(yōu) 解當?shù)谝粋€

34、物品做出決策后，有兩種狀態(tài)當?shù)谝粋€物品做出決策后，有兩種狀態(tài) y1=0，則背包容量沒有影響，則背包容量沒有影響，(y2, yn )是是 的最優(yōu)解的最優(yōu)解 y1=1，則背包減少，則背包減少w1，價值增長，價值增長v1，(y2, yn )是是 的最優(yōu)解的最優(yōu)解x1vixiknap(2, n, c- w1*y1)knap(2, n,c)knap(2, n,c w1)2.遞歸關系 設背包問題的子問題的最優(yōu)值為設背包問題的子問題的最優(yōu)值為m( i, j ),即即m( i, j)是背是背包容量為包容量為j，可選擇物品為，可選擇物品為i，i1，, n時的最優(yōu)值。時的最優(yōu)值。 當選擇第當選擇第i個物品時，個物

35、品時， 。 如果不選擇第如果不選擇第i個物品，則個物品，則 。由問題的最優(yōu)子結構性質，我們可以建立計算由問題的最優(yōu)子結構性質，我們可以建立計算m( i, j)的遞歸式如的遞歸式如下：下： iiiiwjjimwjvwjimjimjim0), 1(), 1(), 1(max),( nnnwjwjvjnm00),(m( i, j) = m(i + 1, j - wi) + vim( i, j) = m(i + 1, j)例例: 四個物品，背包容積為四個物品，背包容積為5，w4=2, 1, 3, 2，v4=12, 10, 20, 15，求最大價值，求最大價值m1c及選取的物品編號及選取的物品編號432

36、14321050000010 1515 15 151515 2020 3535302537ijnnnwjwjvjnm00),( iiiiwjjimwjvwjimjimjim0), 1(), 1(), 1(max),(x4 X3 X2 X11m15m25所以物品所以物品1被選被選c w1= 3,查看查看m23m331j w2= 2,查看查看m32=m420查看查看m42013.算法描述templatevoid Knapsack(Type v, int w, int c, int n, Type *m) int jMax = min( wn - 1, c ); for( int j = 0; j

37、= jMax; j + )/出口出口 m n j = ; for( int j = wn; j 1; i - ) jMax = min( w i - 1, c ); for(int j = 0; j = jMax; j +) m i j = ; for(int j = w i ; j = w1 ) m1c=max(m1c,m2c-w1+v1);0vnm i+1 j m 2 c 初始化初始化mnj只剩下第一個物品只剩下第一個物品時，如果剩余背包時，如果剩余背包容積大于容積大于w1時，時，要進行選擇要進行選擇m15 m2543214321050000010 1015 15 151515 2020

38、3535302537ij構造最優(yōu)解x1=1 c= 5- w1=3m23 m33x2=1 c= 3- w2=2m32 = m42x3=0 c= 2m42 0 x4=1構造最優(yōu)解TemplateVoid Traceback(Type *m,int w,int c,int n,int x) for(int i=1;i2n時，算法需要時，算法需要(n2n)n=3, (w1, w2, w3)=(2, 3, 4), v1, v2, v3=(1, 2, 5), c=5 3-4 錢幣問題3.5 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹Optimal Binary Search Trees最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹利用動

39、態(tài)規(guī)劃構造對標識符集合利用動態(tài)規(guī)劃構造對標識符集合a1, a2, , an的的最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹算法算法包包括括成功檢索成功檢索和和不成功檢索不成功檢索）。）。最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹3、最優(yōu)二叉搜索樹問題、最優(yōu)二叉搜索樹問題 對于有序集對于有序集S及其存取概率分布及其存取概率分布 （a0, b1, a1, , bn, an），在所有表示有序集），在所有表示有序集S的二叉搜索樹中找出一棵具有最小平均路的二叉搜索樹中找出一棵具有最小平均路長的二叉搜索樹。長的二叉搜索樹。 結點在二叉搜索樹中的層次越深，需要比結點在二叉搜索樹中的層次越深，需要比較的次數(shù)就越多，因此要構造一棵最小二較的

40、次數(shù)就越多，因此要構造一棵最小二叉樹，一般盡量把搜索概率較高的結點放叉樹，一般盡量把搜索概率較高的結點放在較高的層次。在較高的層次。最優(yōu)二叉搜索樹問題最優(yōu)二叉搜索樹問題4、最優(yōu)子結構性質、最優(yōu)子結構性質 假設選擇假設選擇 k為樹根，則為樹根，則 1, 2, , k-1 和和a0, a1, , ak-1 都將位于左子樹都將位于左子樹 L 上，其余上，其余結點結點 (k+1, , n 和和 ak, ak+1, , an)位于位于右子樹右子樹 R 上。上。k L R 1, 2, , k-1 a0, a1, , ak-1k+1, , n ak, ak+1, , an最優(yōu)子結構性質最優(yōu)子結構性質4、最優(yōu)

41、子結構性質、最優(yōu)子結構性質 二叉搜索樹二叉搜索樹T 的一棵含有頂點的一棵含有頂點xi , , xj和葉頂點和葉頂點 (xi-1 , xi ) , , ( xj , xj+1)的子樹可以看作是有序集的子樹可以看作是有序集 xi , , xj 關于全集為關于全集為 xi-1 , xj1 的一棵二叉搜索樹（的一棵二叉搜索樹（T 自身可自身可以看作是有序集以看作是有序集) 。根據(jù)。根據(jù)S 的存取分布概率，在子樹的頂?shù)拇嫒》植几怕剩谧訕涞捻旤c處被搜索到的概率是點處被搜索到的概率是最優(yōu)子結構性質最優(yōu)子結構性質jipwpww)(pww)(pwpwr,jmli,mijr,jmm,mli,mijij 1111

42、11左子樹左子樹的搜索的搜索概率概率右子樹右子樹的搜索的搜索概率概率設設Tij是有序集是有序集xi , , xj關于存儲概率分布為關于存儲概率分布為ai-1, bi, , bj, aj 的一棵最優(yōu)二叉搜索樹的一棵最優(yōu)二叉搜索樹Pij ：平均路長平均路長xm ：Tij的根頂點存儲的元素的根頂點存儲的元素pl和和pr: 左子樹左子樹Tl和右子樹和右子樹Tr的平均路長的平均路長xi , , xj的存儲概率分布為的存儲概率分布為ai-1, bi, , bj, aj ，其，其中，中，ah，bk分別是下面的條件概率：分別是下面的條件概率：構造最優(yōu)二叉搜索樹時，可以選構造最優(yōu)二叉搜索樹時，可以選擇先構造其左

43、右子樹，使其左右擇先構造其左右子樹，使其左右子樹最優(yōu)，然后構造整棵樹子樹最優(yōu)，然后構造整棵樹最優(yōu)子結構性質最優(yōu)子結構性質5、遞歸計算最優(yōu)值 最優(yōu)二叉搜索樹最優(yōu)二叉搜索樹Tij的平均路長為的平均路長為pij，則所求的，則所求的最優(yōu)值為最優(yōu)值為p1,n。由二叉樹的花費公式。由二叉樹的花費公式 根據(jù)最優(yōu)二叉搜索樹問題的最優(yōu)子結構性質可根據(jù)最優(yōu)二叉搜索樹問題的最優(yōu)子結構性質可建立計算建立計算pij的遞歸式如下的遞歸式如下初始時初始時jipwpww)(pww)(pwpw,jk,jki,ki,kij,jk,jkk,ki,ki,kijij 1111111111遞歸計算最優(yōu)值遞歸計算最優(yōu)值記記wi,j pi,

44、j為為m( i, j ) 遞歸計算最優(yōu)值遞歸計算最優(yōu)值例 給出標識符集給出標識符集1, 2, 3do, if, stop存取存取概率概率 若若P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05構造一棵最優(yōu)二叉搜索樹構造一棵最優(yōu)二叉搜索樹遞歸計算最優(yōu)值遞歸計算最優(yōu)值P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.051q0q1T11w11=0.75m11=0.752q1q2T22w22=0.25m22=0.253q2q3T33w33=0.15m33=0.1512q0q

45、1q212q0q1q2T12w12=0.9m12=0.9+ m11+m32 =1.65w12=0.9m12=0.9+ m10+m22 =1.15q0T10w10=0.15m10=0q1T21w21=0.1m21=0q2T32w32=0.05m32=0q3T43w43=0.05m43=0P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.051q0q1T11w11=0.75m11=0.752q1q2T22w22=0.25m22=0.253q2q3T33w33=0.15m33=0.1512q0q1q212q0q1q2T12w12=0.9m

46、12=0.9+ m11+m32 =1.65w12=0.9m12=0.9+ m10+m22 =1.1523q1q2q323q1q2q3T23w23=0. 5m23=0.5m23=0.6P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.051q0q1T11w11=0.75m11=0.752q1q2T22w22=0.25m22=0.253q2q3T33w33=0.15m33=0.1512q0q1q212q0q1q2T12w12=0.9m12=0.9+ m11+m32 =1.65w12=0.9m12=0.9+ m10+m22 =1.1523

47、q1q2q323q1q2q3T23w23=0. 5m23=0.5m23=0.6P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05T12m12=1.1512q0q1q223q1q2q3T23m23=0.523q2q31q0q1T13W13=1m13=1.523q2q31q0q1m13=1.923q2q31q0q1m13=2.15P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05T12m12=1.1512q0q1q223q1q2q3T23m23=0.523q2q31q

48、0q1T13W13=1m13=1.523q2q31q0q1m13=1.923q2q31q0q1m13=2.15P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.050123123000040 1 2 31234W(i, j)0 1 2 31234000050.050.750.7550.15230.91.1510.3510. 521.51m(i, j)s(i, j)void OptimalBinarySearchTree( int a, int b,int n, int *m, int *s

49、, int *w) for( int i=0; i=n; i+) wi+1i=ai; mi+1i=0; for(int r=0; rn; r+) for(int i =1; i= n - r; i+) int j= j + r; wij=wij-1+aj+bj; mij=mi+1j; sij = i; for(int k = i+1; k=j; k+) int t=mik-1+mk+1j; if (tmij) mij=t; sij=k; mij+=wij; 初始化初始化對角線賦值對角線賦值i為起始元素下標為起始元素下標j為終止元素下標為終止元素下標加第加第j個結點后，個結點后，權值權值w改變改

50、變如第如第i個結點作根的個結點作根的值值取第取第k個結點作根個結點作根練習練習設設n=4，且，且 (1, 2, 3, 4) = (do, if, read, while)。又設又設b(1 : 4)=(3, 3, 1, 1)和和a(0 : 4)=(2,3,1,1,1)(這些這些b,a都乘了都乘了16。) 寫出數(shù)組寫出數(shù)組wij,mij,sij及最后的最優(yōu)及最后的最優(yōu)二叉搜索樹二叉搜索樹作業(yè)P84 3-15第第4章章 貪心算法的基本要素，思想，與動態(tài)規(guī)劃貪心算法的基本要素，思想，與動態(tài)規(guī)劃的區(qū)別聯(lián)系的區(qū)別聯(lián)系 活動安排問題活動安排問題 最優(yōu)裝載最優(yōu)裝載 單源最短路徑單源最短路徑 多機調度問題多機調

51、度問題什么是貪心方法什么是貪心方法 如果硬幣面值為如果硬幣面值為1角角1分分、7分分、5分分、和、和1分分。 要找給顧客要找給顧客2角角6分分錢，錢， 按貪心方法找出的硬幣個數(shù)是：按貪心方法找出的硬幣個數(shù)是：2個個1角角1分分和四個和四個1分，共分，共6枚，枚， 這比這比1個個1角角1分和分和3個個5分多了分多了2枚；因此，枚；因此，從從局部的最優(yōu)選擇局部的最優(yōu)選擇得到的解得到的解并不總是問題并不總是問題的最優(yōu)解的最優(yōu)解。 貪心算法貪心算法總是作出在當前看來最好的選擇。總是作出在當前看來最好的選擇。 也就是說貪心算法也就是說貪心算法并不從整體最優(yōu)并不從整體最優(yōu)考慮，它所考慮，它所作出的選擇只是

52、在某種意義上的作出的選擇只是在某種意義上的局部最優(yōu)選擇局部最優(yōu)選擇。當然，當然，希望希望貪心算法得到的最終結果也是整體貪心算法得到的最終結果也是整體最優(yōu)的。最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。如單解，但對許多問題它能產生整體最優(yōu)解。如單源最短路徑問題，最小生成樹問題等。源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。 貪心算法通過一系列的選擇來得到一個問貪心算法通過一

53、系列的選擇來得到一個問題的解。它所做的每一個選擇都是當前狀題的解。它所做的每一個選擇都是當前狀態(tài)下某種意義的最好選擇，即貪心選擇。態(tài)下某種意義的最好選擇，即貪心選擇。 希望通過每次所做的選擇導致最終結果是希望通過每次所做的選擇導致最終結果是問題的一個最優(yōu)解。問題的一個最優(yōu)解。 希望從希望從局部的最優(yōu)選擇局部的最優(yōu)選擇得到得到整體最優(yōu)解整體最優(yōu)解。貪心算法的基本要素貪心算法的基本要素貪心算法的基本要素貪心算法的基本要素貪心算法的基本要素貪心算法的基本要素 可用貪心算法求解的問題的基本要素可用貪心算法求解的問題的基本要素 用貪心算法求解的問題，具有兩個重要的性質：用貪心算法求解的問題，具有兩個重要

54、的性質：最優(yōu)子結構性質最優(yōu)子結構性質貪心選擇性質貪心選擇性質。 貪心算法的基本要素貪心算法的基本要素1. 最優(yōu)子結構性質最優(yōu)子結構性質 最優(yōu)子結構性質最優(yōu)子結構性質 整體最優(yōu)解整體最優(yōu)解包含它的包含它的子問題的最優(yōu)解子問題的最優(yōu)解。 具有具有最優(yōu)子結構性質最優(yōu)子結構性質是一個問題可用動態(tài)規(guī)劃是一個問題可用動態(tài)規(guī)劃算法或貪心算法求解的一個關鍵特征。算法或貪心算法求解的一個關鍵特征。貪心算法的基本要素貪心算法的基本要素最優(yōu)子結構性質最優(yōu)子結構性質例：例： 活動安排問題中最優(yōu)子結構性質表現(xiàn)為：活動安排問題中最優(yōu)子結構性質表現(xiàn)為：若若A是對于是對于E的活動安排問題包含活動的活動安排問題包含活動1的的一

55、個最優(yōu)解，則相容活動集合一個最優(yōu)解，則相容活動集合A= A 1是對于是對于E =iE: sif1的活動安排問題的的活動安排問題的一個最優(yōu)解一個最優(yōu)解2.貪心選擇性質貪心選擇性質 貪心選擇性質貪心選擇性質: 所求問題的整體最優(yōu)解可以通過一系列局所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇來完成即貪心選擇來達到。部最優(yōu)的選擇來完成即貪心選擇來達到。 這是貪心算法可行的要素。也是貪心算法這是貪心算法可行的要素。也是貪心算法與與動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法的主要區(qū)別。的主要區(qū)別。 如找顧客錢幣問題和圖的染色問題不具有如找顧客錢幣問題和圖的染色問題不具有貪心選擇性質貪心選擇性質。 貪心算法的基本要素貪心

56、算法的基本要素3.貪心算法與動態(tài)規(guī)劃算法的差異貪心算法與動態(tài)規(guī)劃算法的差異 相同點：都具有最優(yōu)子結構性質相同點：都具有最優(yōu)子結構性質 區(qū)別：動態(tài)規(guī)劃算法每步所作的選擇往往區(qū)別：動態(tài)規(guī)劃算法每步所作的選擇往往依賴于相關子問題的解。只有解出相關子依賴于相關子問題的解。只有解出相關子問題才能作出選擇。問題才能作出選擇。 貪心算法僅在當前狀態(tài)下作出最好選擇，貪心算法僅在當前狀態(tài)下作出最好選擇，即局部最優(yōu)選擇，但不依賴于子問題的解即局部最優(yōu)選擇，但不依賴于子問題的解 貪心：自頂向下貪心：自頂向下 動態(tài)規(guī)劃：自低向上動態(tài)規(guī)劃：自低向上貪心算法的基本要素貪心算法的基本要素貪心算法與動態(tài)規(guī)劃算法的差異貪心算法

57、與動態(tài)規(guī)劃算法的差異 對于一個具有最優(yōu)子結構的問題應該選用對于一個具有最優(yōu)子結構的問題應該選用貪心算法還是動態(tài)規(guī)劃算法？貪心算法還是動態(tài)規(guī)劃算法？ 是不是能用動態(tài)規(guī)劃算法求解的問題也能是不是能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法來求解？用貪心算法來求解？活動安排問題活動安排問題 已知已知n個活動個活動 E = 1, 2, , n 要求使用同要求使用同一資源，第一資源，第k個活動要求的開始和結束時間個活動要求的開始和結束時間為為sk , fk , 其中其中sk fk , k = 1, 2, , n ?；顒印；顒觡與活動與活動j稱為相容的如果稱為相容的如果sk fj 或者或者sj fk?；顒影才?/p>

58、問題就是要在所給的活動集合中活動安排問題就是要在所給的活動集合中選出最大的相容活動子集。選出最大的相容活動子集。問題提出：問題提出：基本思路基本思路 在安排時應該將結束時間早的活動盡量往前安排，在安排時應該將結束時間早的活動盡量往前安排，好給后面的活動安排留出更多的空間，從而達到好給后面的活動安排留出更多的空間，從而達到安排最多活動的目標。安排最多活動的目標。 貪心準則應當是：貪心準則應當是：在未安排的活動中挑選結束時在未安排的活動中挑選結束時間最早的活動安排。間最早的活動安排。活動安排問題活動安排問題活動安排貪心算法偽代碼活動安排貪心算法偽代碼 templatevoid GreedySele

59、ctor(int n, Type starttime , Type fintime ,bool A ) A1 = true; /用集合用集合A來存儲所選擇的活動，活動來存儲所選擇的活動，活動i在集合在集合A中，中， /當且僅當當且僅當Ai的值為的值為true int join=1; /變量變量join用以記錄最近一次加入到用以記錄最近一次加入到A中的活動中的活動 for(int i =2; i=finishtimejoin) /如果第如果第i個任務和個任務和第第j個相容個相容 Ai = true; join = i ; else Ai = false; 活動安排問題活動安排問題4.3 最優(yōu)裝載

60、最優(yōu)裝載 有一艘大船用來裝載貨物。假設有有一艘大船用來裝載貨物。假設有n個貨箱，個貨箱，它們的體積相同，重量分別是它們的體積相同，重量分別是 貨船的最大載重量貨船的最大載重量是是c。目標是在船上裝最多貨。目標是在船上裝最多貨箱該怎樣裝？如果用箱該怎樣裝？如果用 表示裝第表示裝第i個貨箱，個貨箱，而而 表示不裝第表示不裝第i個貨箱，則上述問題是解個貨箱，則上述問題是解優(yōu)化問題：求優(yōu)化問題：求x1, x2,， xn，問題提出0 ix1 ixcxinii 1w niix1max滿足滿足使得使得nwww,211.算法描述算法描述 采用重量最輕者先裝的貪心選擇策略采用重量最輕者先裝的貪心選擇策略. te