0-1背包問題的算法設(shè)計(jì)策略對比與分析報(bào)告

1、算法設(shè)計(jì)與分析大作業(yè)班級：電子名：學(xué)號：任課老師：李 瑞 芳 日期：算法設(shè)計(jì)與分析課程論文算法設(shè)計(jì)與分析課程論文0-1 背包問題的算法設(shè)計(jì)策略對比與分析0-1 背包問題的算法設(shè)計(jì)策略對比與分析0-1背包問題的算法設(shè)計(jì)策略對比與分析引言算法將起到?jīng)Q定性的作用。通俗的講，算法是解決問題的一種方法。也因此“好”于“壞”，怎樣設(shè)計(jì)算法，并以廣泛用于計(jì)算機(jī)科學(xué)中的算 法為例，對種類不同難度的算法設(shè)計(jì)進(jìn)行系統(tǒng)的介紹與比較。本課程將培養(yǎng)學(xué)生嚴(yán)格的設(shè)計(jì)與分析算 法的思維方式，改變隨意拼湊算法的習(xí)慣。本課程要求具備離散數(shù)學(xué)、程序設(shè)計(jì)語言、數(shù)據(jù)結(jié)構(gòu)等先 行課課程的知識。算法復(fù)雜性分析的方法介紹算法復(fù)雜性的高低體現(xiàn)

2、在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上，所需的資源越多，該算法的（存儲器）T(nS(n)之分。算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，這個量應(yīng)集中反映算法的效率，并從運(yùn)行該算 法的實(shí)際計(jì)算機(jī)中抽象出來，換句話說，這個量應(yīng)該只依賴要解決的問題規(guī)模算法的輸入和算法本 和AC=F(N,I,A)T=F(N，I,A)S=F(N，I,A)其中F(N,I,A)是一個三元函數(shù)。通A隱含在復(fù)雜性函數(shù)名當(dāng)中，因此表達(dá)式中一般不A即：C=F(N,I)T=F(N,I)S=F(N,I)算法復(fù)雜性中時(shí)間與空間復(fù)雜性算法相似，所以以下算法復(fù)雜性主要以時(shí)間復(fù)雜性為例：算法的時(shí)間復(fù)雜性一般分為三種情況：最壞情況、最好情況和

3、平均情況。下面描述算法復(fù)雜性時(shí)都是用的簡化的復(fù)雜性算法分析，引入了漸近意義的記號O,，和o。O表示漸近上界表示漸近下界： 表示同階 即 且 f(n)= 常見的算法分析設(shè)計(jì)策略介紹遞歸與分治策略分治法的設(shè)計(jì)思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。 情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。遞歸算法舉

4、例：共11頁 第1頁共共11頁 第6頁共共11頁 第7頁定義為：Fibonacci數(shù)列無窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地1n 0F (n)1n 1F(nF(n2)n 1第n個Fibonacci數(shù)可遞歸地計(jì)算如下： int fibonacci(int n)if (n = 1) return 1;return fibonacci(n-1)+fibonacci(n-2);從上看出：遞歸算法的有點(diǎn)為：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn)為：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)

5、的計(jì)算時(shí)間還是占用的存儲空間都比非遞歸算法要多。分治算法：kadhoc解1merge將k并為原問題的解需用f(n)個單位時(shí)間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間，則有：T (n) n 1kT (n / m) f(n)n logm n1通過迭代法求得方程的解： 算法舉例：T (n) nlogm kk f (n/ m j )a0:j 1n元素。據(jù)此容易設(shè)計(jì)出二。搜索算法： templateint BinarySearch(Type a, const Type& x, int l, int r)while (r = int m = if (x = am) return m;

6、if (x am) r = m-1; else l = m+1;return -1;算法設(shè)計(jì)與分析課程論文算法設(shè)計(jì)與分析課程論文0-1 背包問題的算法設(shè)計(jì)策略對比與分析0-1 背包問題的算法設(shè)計(jì)策略對比與分析算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下， while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn)?？焖倥判蚍ǎ涸诳焖倥判蛑校涗浀谋容^和交換是從兩端向中間進(jìn)行的，關(guān)鍵字較大的記錄一次就 因而總的比較和移動次數(shù)較少。void QuickSort (Type a,

7、 int p, int r)if (pr) int q=Partition(a,p,r);QuickSort (a,p,q-1); QuickSort (a,q+1,r); 復(fù)雜性分析：最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn) 輔助空間：O(n)或O(logn)動態(tài)規(guī)劃動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題但是經(jīng)分解 的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。方法步驟： 1）遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。舉例：矩陣連成問題基本要素： 1）重疊子問題備忘錄方法將矩陣連乘積簡記Ai:j，這ij考察計(jì)算Ai:j的最優(yōu)計(jì)

8、算次序。設(shè)這個計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號方式為：( A A.A)(A.A )ii1kk k2j計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上Ai:k和Ak+1:j相乘的計(jì)算量。算法如下：void MatrixChain(int *p，int n，int *m，int *s)for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+)for (int i = 1; i = n - r+1; i+) int j=i+r-1;mij = mi+1j+ pi-1*pi*pj; sij

9、 = i;for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj;if (t mij) mij = t; sij = k;算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對r，i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O(1)， O(n3O(n3O(n2貪心算法顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考 慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是 如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其 最終

10、結(jié)果卻是最優(yōu)解的很好近似?？捎秘澬乃惴ń鉀Q的問題的性質(zhì)： 1） 貪心選擇性質(zhì)2） 最優(yōu)子結(jié)構(gòu)性質(zhì)舉例：最優(yōu)裝載問題有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下。templatevoid Loading(int x, Type w, Type c, int n)int *t = new int n+1; Sort(w, t, n);for (int i = 1; i = n; i+)

11、xi = 0;for (int i = 1; i = n & wti half)|(t*(t-1)/2-counthalf) return; if (tn) sum+;elsefor (int i=0;i2;i+) p1t=i;count+=i;for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1;Backtrack(t+1);for (int j=2;j=t;j+) count-=pjt-j+1;count-=i;復(fù)雜度分析計(jì)算可行性約束需要O(n)時(shí)間，在最壞情況下有 O(2n)個結(jié)點(diǎn)需要計(jì)算可行性約束，故解符號三角

12、形問題的回溯算法所需的計(jì)算時(shí)間為 O(n2n)。分支限界法分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。常見的兩種分支限界法：(FIFO)分支限界法按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。舉例:0-1背包問題算法思想：首先，要對輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量價(jià)值從大到小進(jìn)行排列。位重量價(jià)值的物品裝滿剩余容

13、量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將 部分算法如下：while (i != n+1) / 非葉結(jié)點(diǎn)/ 檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)Typew wt = cw + wi;if (wt bestp) bestp = cp+pi; AddLiveNode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1);/ 檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)if (up = bestp) / /取下一個擴(kuò)展節(jié)點(diǎn)（略）0-10-1背包問題 ： 給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝

14、入背包的物品，使得裝入背包中物品的總價(jià)值最大?動態(tài)規(guī)劃算法：n設(shè)所給0-1背包問題的子問題maxv xkkk inw x jkkxki,i k nkm(i，j)，即m(i，j)j，可選擇物品為時(shí)0-10-1j)的遞歸式如下。 j),m(i j w )v j wm(i, j) m(i j)iii j wivm(n, j) j wn0 j 0wn算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí)，算法需要的計(jì)算時(shí)間較多。例如，當(dāng)c2n時(shí)，算法需要(n2n)計(jì)算時(shí)間。改進(jìn)算法：由m(i,j)i(1in)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是

15、這一類函數(shù)的描述特征。在一般情況下， 函數(shù)m(i,j)pi存儲函數(shù)pi可依計(jì)算的遞歸式遞歸地由表pi+1時(shí)pn+1=(0，0)。函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù) m(i+1jpi+1m(i+1， j-wi)+vi 的跳躍點(diǎn)集qi+1 的并集中。易知， (s,t)qi+1 當(dāng)且僅當(dāng)wiscpi+1qi+1另一方面，設(shè)(a，b)和(c，d)是pi+1qi+1中的2個跳躍點(diǎn)，則當(dāng)ca且db 時(shí)， (c，d)受控于(a，b)，從而(c，d)不是pi中的跳躍點(diǎn)。除受控跳躍點(diǎn)外， pi+1qi+1中的其它跳躍點(diǎn)均為pi

16、中的跳躍點(diǎn)。由此可見，在遞歸地由表pi+1計(jì)算表pi時(shí)，可先由pi+1計(jì)算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳躍點(diǎn)得到表pi。背包問題的算法設(shè)計(jì)策略對比與分析改進(jìn)后復(fù)雜性分析：pi(1in)qi+1需要O(|pi+1|)pi+1和并清除受控跳躍點(diǎn)也需要O(|pi+1|)計(jì)算時(shí)間。從跳躍點(diǎn)集pi的定義可以看出，pi 中的跳躍點(diǎn)相應(yīng)于xi,xn的0/1賦值。因此，pi中跳躍點(diǎn)個數(shù)不超過2n-i+1。由此可見，算法計(jì)算跳躍點(diǎn)集pi所花費(fèi)的計(jì)算時(shí)間為從而，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1in)是整數(shù)時(shí)，|pi|c+(1in)O(minnc,2n貪心算法：i只有2能將物品ii品的部分，使它適合背包問題。不適合0-1背包問題，所以不能用貪心算法計(jì)算?；厮莘ǎ夯厮莘ǖ娜齻€條件： 解空間：子集樹nw x cn可行性約束函數(shù)：ii1i1上界函數(shù)：template Typep Knap:Bound(int i)/ 計(jì)算上界Typew cleft = c - cw;/Typep b = cp;/ 以物品單位重量價(jià)值遞減序裝入物品while (i = n & wi = cleft) cleft -= wi;b += pi; i+;/ 裝滿背包if (i = n) b += pi/wi * c