算法設(shè)計方案與分析的基本方法及技巧.PPT

第二章 算法設(shè)計與分析的基本方法及技巧,2.1 程序運(yùn)行時間 2.2 一類遞歸方程的求解 2.3 分治 2.4 平衡 2.5 貪心法 2.6 動態(tài)規(guī)則 2.7 回溯,算法（Algorithm）：是對特定問題求解步驟的一種描述，它是 指令（規(guī)則）的有限序列，其中每一條指令表示一個或多個操作。,算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點說,就是計算機(jī)解題的過程。在這個過程中，無論是形成解題思路還是編寫程序,都是在實施某種算法。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。,Persian Textbook(波斯教科書)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm （約公元前825年） 從字面上看，這個名字的意思是“Jafar 的父親，Mohammed 和 Ms 的兒子，Khowrizm 的本地人”。Khowrizm 是前蘇聯(lián)XBA(基發(fā)) 的小城鎮(zhèn) 。Al-Khowrizm 寫了著名的書Kitab al jabr wal-muqabala (復(fù)原和化簡的規(guī)則)；,資料：Algorithm與Logarithm 這個詞一直到1957年之前在Websters New World Dictionary(韋氏新世界詞典)中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“Algorism”(算術(shù))，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程。在中世紀(jì)時，珠算家用算盤進(jìn)行計算，而算術(shù)家用算術(shù)進(jìn)行計算。中世紀(jì)之后，對這個詞的起源已經(jīng)拿不準(zhǔn)了，早期的語言學(xué)家試圖推斷它的來歷，認(rèn)為它是從把a(bǔ)lgiros(費(fèi)力的)+arithmos(數(shù)字)組合起來派生而成的，但另一些人則不同意這種說法，認(rèn)為這個詞是從“喀斯迪爾國王Algor”派生而來的。最后，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了algorism(算術(shù))一詞的真實起源：它來源于著名的Persian Textbook(波斯教科書)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm （約公元前825年）從字面上看，這個名字的意思是“Jafar 的父親，Mohammed 和 Ms 的兒子，Khowrizm 的本地人”。Khowrizm 是前蘇聯(lián)XBA(基發(fā)) 的小城鎮(zhèn) 。Al-Khowrizm 寫了著名的書Kitab al jabr wal-muqabala (復(fù)原和化簡的規(guī)則)；另一個詞，“algebra”(代數(shù))，是從他的書的標(biāo)題引出來的，盡管這本書實際上根本不是講代數(shù)的。 逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語字典所說明的，這個詞是由于同arithmetic(算術(shù))相混淆而形成的錯拼詞。由algorism又變成algorithm。一本早期的德文數(shù)學(xué)詞典 Vollstandiges Mathematisches Lexicon (數(shù)學(xué)大全辭典) ，給出了Algorithmus (算法)一詞的如下定義：“在這個名稱之下，組合了四種類型的算術(shù)計算的概念，即加法、乘法、減法、除法”。拉頂短語algorithmus infinitesimalis (無限小方法) ，在當(dāng)時就用來表示Leibnitz(萊布尼茲)所發(fā)明的以無限小量進(jìn)行計算的微積分方法。 1950年左右，algorithm一詞經(jīng)常地同歐幾里德算法(Euclids algorithm)聯(lián)系在一起。這個算法就是在歐幾里德的幾何原本(Euclids Elements ,第VII卷，命題i和ii)中所闡述的求兩個數(shù)的最大公約數(shù)的過程(即輾轉(zhuǎn)相除法)。,遞歸技術(shù) 最常用的算法設(shè)計思想，體現(xiàn)于許多優(yōu)秀算法之中 分治法 分而制之的算法思想，體現(xiàn)了一分為二的哲學(xué)思想 模擬法 用計算機(jī)模擬實際場景，經(jīng)常用于與概率有關(guān)的問題 貪心算法 采用貪心策略的算法設(shè)計 狀態(tài)空間搜索法 被稱為“萬能算法”的算法設(shè)計策略 隨機(jī)算法 利用隨機(jī)選擇自適應(yīng)地決定優(yōu)先搜索的方向 動態(tài)規(guī)劃 常用的最優(yōu)化問題解決方法,“好”的算法的標(biāo)準(zhǔn)： 正確性，算法能滿足具體問題的需求 可讀性，首先方便閱讀與交流，其次才是機(jī)器執(zhí)行 健壯性，輸入錯誤時，能作出反應(yīng)，避免異常出錯 效率與低存儲量要求,算法的特征： 有窮性、確定性、輸入、輸出、能行性,對算法“正確性”的要求： 不含語法錯誤； 對于幾組輸入數(shù)據(jù)能得到滿足要求的結(jié)果； 對精心選擇苛刻并帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果； 對于一切合法的輸入均得到滿足要求的結(jié)果；,算法描述： 自然語言；程序設(shè)計語言；類語言*；,關(guān)于本書采用的類語言描述： 結(jié)構(gòu)類型說明 輸入輸出約定( cin v , cout v ) new 和 delete 引入引用類型 其他,影響算法執(zhí)行的因素： 算法實現(xiàn)后所消耗的時間* 算法實現(xiàn)后所占存儲空間的大小* 算法是否易讀、易移植等等其它問題,影響時間特性的四個因素： 程序運(yùn)行時輸入數(shù)據(jù)的總量 對源程序編譯所需的時間 計算機(jī)執(zhí)行每條指令所需的時間 程序中指令重復(fù)執(zhí)行的次數(shù)*,定義 語句頻度：語句重復(fù)執(zhí)行的次數(shù),程序運(yùn)行時間,漸近時間復(fù)雜度（時間復(fù)雜度）T（n）,算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù) f（n），算法的時間度量記作： T（n）= O（ f（n） 它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和 f（n）的增長率相同。,漸近空間復(fù)雜度（空間復(fù)雜度）S（n）,S（n）= O（ g（n）,運(yùn)算法則： 設(shè)：T1(n)=O( f(n) )，T2(n)=O( g(n) ) 加法規(guī)則：T1(n)+T2(n) = O( max f(n), g(n) ) 乘法規(guī)則：T1(n) T2(n) = O( f(n) g(n) ),設(shè)：,T(x) ： 取變量或常量x之值所消耗時間 T(.V)： 取變量V之地址所消耗的時間 T(=) ： 賦值所消耗時間 T() ： 執(zhí)行基本運(yùn)算所耗時間 T(call/return)：執(zhí)行函數(shù)調(diào)用和返回所耗時間 T(par) ： 將參數(shù)par傳給函數(shù)所消耗時間,(1) 表達(dá)式和賦值語句 exp:=常數(shù) | 變量 | F-name(e1,e2,em) | (exp exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp exp)=T(exp)+T()+T(exp) T(F-name(e1,e2,em)=T(call/return)+mT(par)+T(F-body) 例： T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相應(yīng)的匯編程序為： load a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2,通常取O(1),(2) 語句序列 T(s1,s2,sk)=maxT(s1),T(s2),T(sk) (3) 條件語句 T( if (B) s1 else s2)=T(B)+T(else)+maxT(s1),T(s2) 通常取T(B)+T(else)=O(1) T(if(B) s )=O(1)+T(s) (4) Switch語句 設(shè)語句s switch(E) case E1: S1; case Ek: Sk; default : Sm T(s)=T(E)+T(Ei)+maxT(s1),T(sk),T(sm) O(1),k i=1,(5) for語句 T( for(i=1;i=n;i+) s ) =(T(s)+T(i=1)+T(i=n)+T(i+)+T(for),O(1),(6) while語句 while(B) s i=0;while(B) s ; i+ 設(shè)RT0表示某一次循環(huán)開始執(zhí)行時的絕對時間 關(guān)于循環(huán)的定時不變式RT為 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j) 其中：T(while)代表測試循環(huán)終止條件所耗時間 T(j)代表跳回循環(huán)頭所耗時間 可簡化成：T(j)=T(while) T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while),(7) 函數(shù)調(diào)用 遞歸調(diào)用：被調(diào)用子函數(shù)運(yùn)行時間 非遞歸調(diào)用：求解遞歸方程 (8) goto語句 goto語句破壞了程序結(jié)構(gòu) 一般對goto語句限制使用 對有條件的goto轉(zhuǎn)移可忽略不計,Void BUBBLE(A) int An; int I,j,temp; for(i=0;i=i+1;j-) O(n-i-1) if(Aj-1Aj) O(n-i-1) 1) O(n(n-1)/2) temp=Aj-1; O(1) O(1) =(n-i-1) =O(n2) Aj-1=Aj; O(1) O(1) Aj=temp; O(1) ,n-2 i=0,舉例： s = 0 ; f(n) = 1; T1(n) = O(f(n) = O(1) 常量階 for ( i=1 ; i = n ; +i ) +x; s += x; f(n) = 3n+1; T2(n) = O(f(n) = O(n) 線性階 for ( i=1; i=n ; +i ) for( j=1 ; j =n ; +j ) +x ; s += x; f(n) = 3n2+2n+1; T3(n) = O(f(n) = O(n2) 平方階 for ( i=1; i=n ; +i ) for ( j=1 ; j =n ; +j ) cij = 0; for ( k=1 ; k = n; +k ) cij += aik * bkj ; f(n) = 2n3+3n2+2n+1; T4(n) = O(f(n) = O(n3) 立方階,舉例： Long fact ( int n) if ( n=0 ) | ( n =1 ) return( 1 ); else return( n * fact( n 1 ) ); ,f( n ) = n G T( n ) = O( f( n ) ) = O( n ),int sort(i,j) int i,j; if(i=j) return(xi); else m=(i+j-1)/2; return(merge(sort(i,m),sort(m+1),j); ,這是一個快速排序算法 merge的運(yùn)行時間正比于n（n是2的冪） 設(shè)T(n)是sort最差情況下的運(yùn)行時間，則,一類遞歸方程的求解,猜解法： 首先猜出一個解f(n)的形式，令其帶有待定參數(shù)；在歸納 推理過程中確定待定參數(shù)，并利用方程證明T(n) f(n)。 若推理過程能夠完成且待定參數(shù)能夠確定，則求解完畢。 f(n)可以是 O(1) , O(n) , O(nlogn) , O(n2)等等。,猜測1：對參數(shù)a，T(n) anlogn，帶入n=1，由于anlogn=0 雖然滿足T(1) c1，但它與a無關(guān)，無法確定a與c1關(guān)系。 此猜測失敗。,猜測2：T(n)=anlogn+b，當(dāng)n=1時，只要bc1即可。 當(dāng)n2時，設(shè)對所有的 kn 有 T(k) aklogk+b 令k=n/2 得 T(n/2) a(n/2)log(n/2)+b 帶入原式： T(n) 2T(n/2)+c2n2(a(n/2)log(n/2)+b)+c2n =an(logn-1)+c2n+2b =anlogn+b-(an-c2n-b) 只要令an-c2n-b0就有 T(n) anlogn+b 選擇ac2+b，使an-c2n-b0得到滿足。 使T(n) anlogn+b成立的兩個約束是： bc1，ac2+b 取b=c1 , a=c1+c2 是合理的。,一類遞歸方程的展開式與通解,設(shè)T(n)是求解某個問題的時間開銷，n使問題的數(shù)據(jù)量。設(shè)計 對此問題列出的遞歸方程為： T(1)=1 T(n)=aT(n/c)+d(n) n2 其中c是大于等于1的正整數(shù)。全部數(shù)據(jù)被分割成c等分，每分的 數(shù)量為n/c。T(n/c)是求解一個子問題的時間開銷。aT(n/c)代表求 解a個問題的時間開銷。D(n)是任意的函數(shù)，方程是嚴(yán)格的等式。 用n/ci代替n得： T(n/ci)=aT(n/ci+1)+d(n/ci), i=1,2,3, T(n)=aT(n/c)+d(n) =a(aT(n/c2)+d(n/c)+d(n)=a2T(n/c2)+ad(n/c)+dn =a2(aT(n/c3)+d(n/c2)+ad(n/c)+d(n) =a3T(n/c3)+a2d(n/c2)+ad(n/c)+d(n) = =ai T(n/ci)+ajd(n/cj),i-1 j=0,倍積函數(shù)：若對所有的正整數(shù)x，y，有f(xy)=f(x)f(y)，則 f 是 正整數(shù)上的倍積函數(shù)。 若d(n)是倍積函數(shù)。則有： d(ck-1)=(d(c)k-1,定理：設(shè)a,c是非負(fù)常數(shù)，n是2的冪，d(n)是倍積函數(shù)，則,的齊次解是O(nlogc )，且對特解有如下結(jié)論： (1)若ad(c)，則特解是O(ak)，或O(nlogc ),即特解與齊次解同階 (2)若ad(c)，則特解是O(d(c)k)，或O(nlogcd(c)即特解與d同階 (3)若a=d(c)，則特解是齊次解的logcn。,a,a,基本思想：分而治之。將一個規(guī)模為n的問題分解為k個規(guī)模較小 的子問題，這些子問題互相獨(dú)立且與原問題相同。遞 歸地解這些子問題，然后將各子問題的解合并得到原 問題的解。,設(shè)問題輸入數(shù)據(jù)A0n-1，函數(shù)dac(p,q)求子問題Ap,q的解。 對函數(shù)dac的首次調(diào)用是dac(0,n-1)。,int dac(int p, int q) if(small(p,q) return(G(p,q); else (m1,mk)=divide(p,q); return(Combine(dac(p,m1),dac(m1+1,m2), ,dac(mk+1,q); ,分治方法與軟件設(shè)計的模塊化方法非常相似。為了解決一個大的問題，可以： 1) 把它分成兩個或多個更小的問題； 2) 分別解決每個小問題； 3) 把各小問題的解組合起來，即可得到原問題的解答。 小問題通常與原問題相似，可以遞歸使用分治策略來解決。,分治（Divide and Conquer ）,1、整數(shù)乘法,求兩個n位數(shù)之積，傳統(tǒng)方法需要O(n2)次比較運(yùn)算，運(yùn)用分治 法可以將運(yùn)算次數(shù)的階降到O(nlog3) O(n1.59)。,設(shè)x和y都是n位數(shù)，n是2的冪，將x和y各分成兩半，每一半都 是n/2位數(shù)，則xy的積可寫成：,xy=(a2n/2+b) (c2n/2+d) =ac2n+(ad+bc) 2n/2+bd 也可寫成： xy=ac2n+ac+ (a-b) (d-c) +bd) 2n/2+bd,a,b,c,d,x=,y=,int mult(int x, int y,int n) if(n=1) return(x*y); else s=sign(x)*sign(y); x=abs(x); y=abs(y); a=x的左n/2位； b=x的右n/2位； c=y的左n/2位； d=y的右n/2位； v=mult(a,c,n/2); u=mult(a-b,d-c,n/2); w=mult(b,d,n/2); return(s*(v*2n+(u+v+w)*2n/2+w) ,例：設(shè) x=3141, y=5327, 利用分治法求xy,31,41,53,27,x=,y=,x=3141 a=31 b=41 a-b=-10 y=5327 c=53 d=27 d-c=-26 ac=(1643)*, bd=(1107)*, (a-b) (d-c)=(260)* xy=ac104+(ac+(a-b) (d-c)+bd) 102+bd =(1643)*104+(1643)*+(260)*+(1107)* 102+(1107)* =(16732107)*,a=31 a1=3 b1=1 a1-b1=2 c=53 c1=5 d1=3 d1-c1=-2 a1c1=15, b1d1=3, (a1-b1) (d1-c1)=-4 ac=15102+(15+3-4)101+3=1632,b=41 a2=4 b2=1 a2-b2=3 d=27 c2=2 d2=7 d2-c2=5 a2c2=8, b2d2=7, (a2-b2) (d2-c2)=15 bd=8102+(8+7+15)101+7=1107,a-b=10 a3=1 b3=0 a3-b3=1 d-c=26 c3=2 d3=6 d3-c3=4 a3c3=2, b3d3=0, (a3-b3) (d3-c3)=4 (a-b) (d-c)=2102+(2+0+4) 101+0=260,2、求兩個矩陣的積,C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22,將A和B分別等分成4個小矩陣,每個元素就是一個(n/2) x(n/2)矩陣,假設(shè)用(n/2) (n/2)矩陣的m次相乘和a次相加（減）可以算出Cij， 則遞歸應(yīng)用這種算法，對nn矩陣之積的時間開銷滿足： T(n)2 其中第一項是計算m對(n/2) (n/2)矩陣之積的時間開銷,(n/2)2個數(shù) 第二項是a次矩陣相加的時間開銷。上是可變換成： 4/aT(n)=4m/aT(n/2)+n2 U(n)=4m/aU(n/2)+n2 其中d(n)=n2是倍積函數(shù)，只要ma就有4m/ad(c)，T(n)=O(nlogm) m=8,a=4，T(n)=O(n3),V.Strassen矩陣,引理2.1 兩個22矩陣(元素來自任意的環(huán))之積可以用7次相乘和 18次相加(減)完成。,M1=(A11A12)(B21+B22) M2=(A11+A22)(B11+B22) M3=(A11A21)(b11+B12) M4=(A11+A12)B22 M5=A11(B12-B22) M6=A22(B21B11) M7=(A21+A22)B11,C11=M1+M2-M4+M6 C12=M4+M5 C21=M6+M7 C22=M2M3+M5M7,定理2.2 兩個nn的矩陣(元素來自任意的環(huán))之積可用O(nlog7)次 運(yùn)算完成 證：設(shè)n=2k，T(n)是計算兩個nn矩陣之積，由引理2.1得 T(n)=7T(n/2)+18(n/2)2，n=2 故有：T(n)=O(nlog7),在對問題進(jìn)行分割時，應(yīng)使各子問題的數(shù)據(jù)量保持相等或盡可能 相等。保持平衡是算法設(shè)計的一條基本原則。,例如：常見的是“冒泡”分類算法就是一個不平衡的例子。 在分治時將輸入數(shù)據(jù)a1,a2,an分成很不平衡的數(shù)據(jù)段： 從左至右掃描a1,a2,an并求出minai,1=i=n；將它與 a1交換位置；對后面的n-1個元素遞歸地應(yīng)用此算法。,T(n)=n(n-1)/2=O(n2),考慮平衡：不妨設(shè)n是2的冪。將a1,a2,an分成兩個子序列： a1,a2,an/2和a(n/2)+1,an。先對每個子序列進(jìn)行分類，然后 對已分類的子序列進(jìn)行歸并（最多需要n-1次比較），合并成一 個有序序列。,T(n)=O(nlogn),平衡,運(yùn)用局部最佳策略以求達(dá)到全局最佳結(jié)果。 給定輸入數(shù)據(jù)為A1,A2,An，對解附有某些約束條件 和表示最佳結(jié)果的目標(biāo)函數(shù)，欲求滿足約束條件的子集Aik,使 目標(biāo)函數(shù)值達(dá)到最大（或最?。?。 滿足約束條件的任意子集叫做可用解，使給定的目標(biāo)值達(dá)到 最大（或最?。┑目捎媒饨凶鲎罴呀?。最終目的是求全局最佳解。,Dataset Gready(A, n) LIST A ; int n ; solution = ； for( i = 1; i = n; i+ ) x = select(A); if ( feasible( solution, x ) ) solution = union ( solution , x ) ; return solution ; ,select 對 A 確定一種取值辦法；每步對 一個x=Ai作出判斷：x是否可以包含在 最佳解中？若x加入局部最佳解時就產(chǎn)生 不可用解，放棄x，另作選擇。,union將x和solution結(jié)合成新的解向量,并 修改目標(biāo)函數(shù)的值。,貪心法,在貪心算法（greedy method）中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedy criterion）。,例找零錢 一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時所采用的貪婪準(zhǔn)則如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應(yīng)使零錢總數(shù)超過最終所需的數(shù)目。 假設(shè)需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過6 7美分），第三枚應(yīng)選擇1 0美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。,背包問題 設(shè)有n個對象和一個背包。對象的重量為wi。背包容量為M(重量)。 若將對象i的一部分xi(0xi1;xi表示重物wi的幾分之幾)放入背包， 則得增益pixi，其中pi叫做重物wi的增益率。目標(biāo):在n個對象中選 取若干對象，將背包裝滿(所選對象的總重量不超過M),使總增 益最大。,max(pixi) ,1in,約束條件：wixiM 0xi1, pi0, wi0, 1in 滿足的任意集合x1,x2,xn就是可用解 使最大的可用解即最佳解,1in,三種貪心策略： (1)局部最大增一策略：即在第i步選過之后第i+1步將當(dāng)前增益 最大的未選對象裝入背包；若該對象太大而溢出背包，則裝 入該對象的幾分之幾。 (2)貪心策略之二：背包容量局部消耗最小策略。即按先輕后重 的順序來選擇對象。 (3)貪心策略之三：消耗單位容量，獲取局部最大增益策略。即 按pi/wi非增加的順序來選擇對象。,例：設(shè)n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10),按策略1，對象1的增益率p1最大，取x1=1, 則背包容量尚余M-w1=2;對象2的增益率次 之,但w2=15,不能全部裝入,故令x2=2/15,得解2。 按策略2，首先取x3=1,次取x2=2/3,得解3。 按策略3，得解4，這才是最佳解。,Void KnapSack (LIST w ; int m ; LIST ,Pi/wi=(1.4,1.6,1.5),定理2.3 若 p1/w1p2/w2pn/wn 則算法Knapsack對給定的 背包問題生成全局最佳解。 證明見教材P42（略）。,實例： 設(shè)有一個背包可以放入的物品的重量為s，現(xiàn)有n件物品，重量分 別為w1, w2, , wn。問能否從這n件物品中選擇若干件放入 此背包中，使得放入的重量之和正好為S。 如果存在一種符合上 述要求的選擇，則稱此背包問題有解(或稱其解為真)；否則稱此 背包問題無解(或稱其解為假)。試用遞歸方法設(shè)計求解背包問題 的算法。,enum boolean False, True boolean Kanp( int s, int n ) if ( s = 0 ) return True; if ( s 0 ,當(dāng)一個問題的解可以看成是以序列判定的結(jié)果時，可以用動態(tài) 規(guī)劃方法設(shè)計出這類問題的求解算法。,起源于二十世紀(jì)五十年代（貝爾曼B.E.Bellman） 屬于現(xiàn)代控制理論的一部分 以長遠(yuǎn)利益為目標(biāo)的一系列決策 最優(yōu)化原理，可歸結(jié)為一個遞推公式 又稱為對階段規(guī)劃，特點體現(xiàn)在多階段性,動態(tài)規(guī)劃,背包問題的解可以看成是一序列判定的結(jié)果，這里必須決定xi(1in)的取值。我們可以用不盡的方式首先做關(guān)于x1的判定,然后關(guān)于x2,x3,等等.最后產(chǎn)生一個最佳的判定序列x1,x2,xn,使目標(biāo)函數(shù)pixi的值最大。,最佳原理 一個最佳判定序列有這樣一個性質(zhì)：無論該序列是從什么初始 狀態(tài)開始首次判斷的，其后續(xù)的判斷隊首次判斷所產(chǎn)生的狀態(tài) 而言，必構(gòu)成最佳判定序列。 貪心法與動態(tài)規(guī)劃方法之間的本質(zhì)區(qū)別： 貪心法只生成一個判定序列，而動態(tài)規(guī)劃方法則可能產(chǎn)生許多 判定序列。,maxpixi,1ij,例：（0/1）背包問題用Knap(1,I,y)表示下述0/1背包問題,約束條件：wixiy， xi=0 或 1 （ 1ij）,1ij,則0/1背包問題是knap(1,n,M),wiziM-w1 ，pizipixi,2in,2in,2in,設(shè)：y1,y2,yn是x1,x2,xn所取0/1值的最佳序列。,若y1=0, y2,y3,yn必構(gòu)成關(guān)于Knap(2,n,M)的最佳序列。不然，y1,y2,yn就不是Knap(1,n,M)的最佳序列。,若y1=1,則y2,y3,yn必是關(guān)于knap(2,n,M-w1)的最佳序列,如不然，就會有另一個0/1序列