【導(dǎo)讀】指令（規(guī)則）的有限序列，其中每一條指令表示一個或多個操作。算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。在這個過程中，無論是形成解題思路還是編寫程序,都是在實施某種算法。和Mûsâ的兒子，Khowârizm的本地人”。聯(lián)XИBA(基發(fā))的小城鎮(zhèn)。Al-Khowârizm寫了著名的書Kitab. 在中世紀(jì)時，珠算家用算盤進行計算，而算術(shù)家用算術(shù)進行計算。斯迪爾國王Algor”派生而來的。最后，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了algorism(算術(shù))一詞的真實起源：它。來源于著名的PersianTextbook的作者的名字AbuJa'farMohammedibnMûsâal-Khowârizm——從字面上看，這個名字的意思是“Ja'far的父親，逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語字典所說明的，這個詞是由。于同arithmetic(算術(shù))相混淆而形成的錯拼詞。1950年左右，algorithm一詞經(jīng)常地同歐幾里德算法聯(lián)系在一起。法就是在歐幾里德的《幾何原本》中所闡述的求兩。③對精心選擇苛刻并帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果；④對于一切合法的輸入均得到滿足要求的結(jié)果；f的增長率相同。

　　

【正文】 x[i] = 1 。 cu = cu – w[i] 。 } L : if ( i = n ) x[i] = cu / w[i] 。 } Pi/wi=(,) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 36 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 定理 若 p1/w1≥p2/w2≥…≥p n/wn 則算法 Knapsack對給定的 背包問題生成全局最佳解。 證明見教材 P42（略）。 實例： 設(shè)有一個背包可以放入的物品的重量為 s，現(xiàn)有 n件物品，重量分 別為 w[1], w[2], …, w[n] 。問能否從這 n件物品中選擇若干件放入 此背包中，使得放入的重量之和正好為 S。 如果存在一種符合上 述要求的選擇，則稱此背包問題有解 (或稱其解為真 )；否則稱此 背包問題無解 (或稱其解為假 )。試用遞歸方法設(shè)計求解背包問題 的算法。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 37 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 ??????????????????? ][)1],[(][10 )1,( 10Fa l s e 0Fa l s e 0T r u e),(時所選物品中包括時所選物品中不包括且或物品件數(shù)不能為負(fù)數(shù)且總重量不能為負(fù)數(shù)此時背包問題一定有解nwnnwsK N A PnwnsnsK N A PnsssnsK N A Penum boolean { False, True } boolean Kanp( int s, int n ) { if ( s == 0 ) return True。 if ( s 0 || s 0 amp。amp。 n 1 ) return False。 if ( Kanp ( s – W[n], n1 ) == True ) { cout W[n] ‘ , ’。 return True。 } return Kanp( s, n1 )。 } . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 38 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 當(dāng)一個問題的解可以看成是以序列判定的結(jié)果時，可以用動態(tài) 規(guī)劃方法設(shè)計出這類問題的求解算法。 ?起源于二十世紀(jì)五十年代（貝爾曼 ） ?屬于現(xiàn)代控制理論的一部分 ?以長遠(yuǎn)利益為目標(biāo)的一系列決策 ?最優(yōu)化原理，可歸結(jié)為一個遞推公式 ?又稱為對階段規(guī)劃，特點體現(xiàn)在多階段性 ?動態(tài)規(guī)劃 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 39 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 背包問題的解可以看成是一序列判定的結(jié)果，這里必須決定xi(1≤i≤n)的取值。我們可以用不盡的方式首先做關(guān)于 x1的判定 ,然后關(guān)于 x2,x3,等等 .最后產(chǎn)生一個最佳的判定序列 x1,x2,…,x n,使目標(biāo)函數(shù) ∑pixi的值最大。 最佳原理 一個最佳判定序列有這樣一個性質(zhì)：無論該序列是從什么初始 狀態(tài)開始首次判斷的，其后續(xù)的判斷隊首次判斷所產(chǎn)生的狀態(tài) 而言，必構(gòu)成最佳判定序列。 貪心法與動態(tài)規(guī)劃方法之間的本質(zhì)區(qū)別： 貪心法只生成一個判定序列，而動態(tài)規(guī)劃方法則可能產(chǎn)生許多 判定序列。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 40 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 max∑pixi 1≤i≤j 例：（ 0/1）背包問題用 Knap(1,I,y)表示下述 0/1背包問題 約束條件： ∑wixi≤y， xi=0 或 1 （ 1≤i≤j） 1≤i≤j 則 0/1背包問題是 knap(1,n,M) ∑wizi≤Mw1 ， ∑pizi＞ ∑pixi 2≤i≤n 2≤i≤n 2≤i≤n 設(shè)： y1,y2,…,y n是 x1,x2,…,x n所取 0/1值的最佳序列。 ? 若 y1=0, y2,y3,…,y n必構(gòu)成關(guān)于 Knap(2,n,M)的最佳序列。不然，y1,y2,…,y n就不是 Knap(1,n,M)的最佳序列。 ? 若 y1=1,則 y2,y3,…,y n必是關(guān)于 knap(2,n,Mw1)的最佳序列 ,如不然，就會有另一個 0/1序列 z2,z3,…,z n使： 于是， y1,z2,…,z n是一個符合目標(biāo)函數(shù)且具有最大增益的序列。這與 y1,y2,…,y n是最佳序列相矛盾 ,說明最佳原理適用于 0/1背包問題。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 41 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 gj(y)=∑pixi ， ∑wixi≤ y ， xi=0/1 (j+1≤i≤n) j+1≤i≤n j+1≤i≤n ?若選 x1=0： g0(M)=∑pixi=∑pixi=g1(M)，約束條件： ∑wixi=∑wixi≤M ?若選 x1=1： g0(M)=∑pixi=p1+∑pixi=p1+g1(Mw1) 關(guān)于目標(biāo)函數(shù)的遞推式： 設(shè) gj(y)是 0/1背包 (子 )問題 Knap(j+1,n,y)的最佳解的目標(biāo)函數(shù)，即： 則 g0(M)是 knap(1,n,M)的最佳解。 對 x1的可能判定是 0/1： 其中 ∑wixi≤M是對 Knap(2,n,M)的約束條件。因此，如果決定不取 w1，則 求解 Knap(1,n,M)的問題即歸結(jié)為求解子問題 Knap(2,n,M)。 約束條件 ∑wixi可以換成： ∑wixi≤Mw1，就是說，如果決定將 w1裝入背包， 則 g0(M)=p1+g1(Mw1)且對 0/1背包問題的約束變成 ∑wixi≤Mw1， 故求解 Knap(1,n,M)的問題可歸結(jié)為求解 Knap(2,n,Mw1)的問題。 1≤i≤n 1≤i≤n 1≤i≤j 1≤i≤j 2≤i≤n 2≤i≤n 2≤i≤n 2≤i≤n 2≤i≤n 2≤i≤n . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 42 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 由最佳原理得： g0(M)=max { g1(M) , g1(Mw1)+p1 } 一般向前遞推式為： gi(n)=max { gi+1(y) , gi+1(ywi+1)+pi+1 } 由于 gn(y)=0對所有的 y成立，在上式 代入 i=n1即可由 gn(y)求出 gn1(y)…… 一般向后遞推式為： gn(M)=max { gn1(M) , gn1(Mwn)+pn } gj(y)=max{gj1(y),gj1(ywj)+pj g0(y)=0 (y≥0) 0/1背包問題難于非 0/1背包問題，因為 0/1背包問題將產(chǎn)生 2n 個判定序列，其中 n是解向量 (x1,x2,…,x n)的長度。所以不能 用貪心法解 0/1背包問題。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 43 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 mij = 0 i=j min(mik+mk+1,j+ri1rkrj ij i≤k≤j M = M1 M2 M3 M4 [10 20] [20 50] [50 1] [1 100] M = M1 M2 … Mn M1 (M2 M3 M4) 23000次乘法 (M1 (M2 M3)) M4) 2200次乘法 設(shè) mij是計算 Mi Mi+1 … Mj的最小代價 求 n個矩陣的乘積 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 44 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 m11=0 m22=0 m33=0 m44=0 m12=10000 m23=1000 m34=5000 m13=1200 m24=3000 m14=2200 { for ( i=1 。 i= n 。 i++ ) mi,i=0 。 for ( l=1 。 l = n 。 l++ ) for( i=1 。i = n1 。 i++ ) { j = i+1 。 mi,j=min(Mi,k+Mk+1,j+ri1*rk*rj ) 。 } write(mln) 。 } { mij=∞； for(k=i。k=j1。k++) if(mijmik+mk+1,j+ri1*rk*rj) { mij=mk+mk+1,j+ri1*rk*rj； Kij=k 。 } } . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 45 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 ?回溯