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

1、式修理了火孚算法設(shè)計與分析大作業(yè)班 級：電子154姓 名：吳志勇學(xué)號：1049731503279任課老師：李瑞芳日期：2015.12.25算法設(shè)計與分析課程論文0-1背包問題的算法設(shè)計策略對比與分析0引言對于計算機科學(xué)來說，算法的概念是至關(guān)重要的。在一個大型軟件系統(tǒng)的開發(fā)中，設(shè)計出有效的 算法將起到?jīng)Q定性的作用。通俗的講，算法是解決問題的一種方法。也因此，算法分析與設(shè)計成為計算科學(xué)的核心問題之一，也是計算機科學(xué)與技術(shù)專業(yè)本科及研究生的一門重要的專業(yè)基礎(chǔ)課。算法 分析與設(shè)計是計算機軟件開發(fā)人員必修課，軟件的效率和穩(wěn)定性取決于軟件中所采用的算法；對于一 般程序員和計算機專業(yè)學(xué)生，學(xué)習(xí)算法設(shè)計與分析

2、課程，可以開闊編程思路，編寫出優(yōu)質(zhì)程序。通過 老師的解析，培養(yǎng)我們怎樣分析算法的好“于 壞”，怎樣設(shè)計算法，并以廣泛用于計算機科學(xué)中的算法為例，對種類不同難度的算法設(shè)計進行系統(tǒng)的介紹與比較。本課程將培養(yǎng)學(xué)生嚴(yán)格的設(shè)計與分析算 法的思維方式，改變隨意拼湊算法的習(xí)慣。本課程要求具備離散數(shù)學(xué)、程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)等先 行課課程的知識。1算法復(fù)雜性分析的方法介紹算法復(fù)雜性的高低體現(xiàn)在運行該算法所需要的計算機資源的多少上，所需的資源越多，該算法的復(fù)雜性越高；反之，所需資源越少，該算法的復(fù)雜性越低。 對計算機資源，最重要的是時間與空間(即存儲器)資源。因此，算法的復(fù)雜性有時間復(fù)雜性T(n)與空間復(fù)雜性S

3、(n)之分。算法復(fù)雜性是算法運行所需要的計算機資源的量，這個量應(yīng)集中反映算法的效率，并從運行該算 法的實際計算機中抽象出來，換句話說，這個量應(yīng)該只依賴要解決的問題規(guī)模算法的輸入和算法本 身的函數(shù)。用C表示復(fù)雜性，N,I和A表示問題的規(guī)模、算法的輸入和算法本身規(guī)模，則有如下表達式：C=F(N,I,A) T=F(N , I,A) S=F(N , I,A)其中F(N,I,A)是一個三元函數(shù)。通常 A隱含在復(fù)雜性函數(shù)名當(dāng)中，因此表達式中一般不寫Ao即：C=F(N,I) T=F(N,I) S=F(N,I)算法復(fù)雜性中時間與空間復(fù)雜性算法相似，所以以下算法復(fù)雜性主要以時間復(fù)雜性為例：算法的時間復(fù)雜性一般分

4、為三種情況：最壞情況、最好情況和平均情況。下面描述算法復(fù)雜性時 都是用的簡化的復(fù)雜性算法分析，引入了漸近意義的記號O,Q,。，和o。O表示漸近上界Q表示漸近下界：。表示同階即：f(n)= Qg(n)且 f(n)= Q ( g(n)2常見的算法分析設(shè)計策略介紹2.1遞歸與分治策略分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以 便各個擊破，分而治之。直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)

5、模卻不斷縮小，最終使子問 題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對攣生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算法。遞歸算法舉例：Fibonacci 數(shù)歹U無窮數(shù)列1, 1, 2, 3, 5, 8, 13, 21, 34, 55,，稱為Fibonacci數(shù)列。它可以遞歸地定義為：1n = 0F(n) = 1n = 1F(n -1) F(n -2) n 1第n個Fibonacci數(shù)可遞歸地計算如下:int fibonacci (int n)if (n = 1) return 1;return fibonacci (n-1)+ fibonacci (n-2

6、);從上看出:遞歸算法的有點為：結(jié)構(gòu)清晰，可讀性強，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計算法、 調(diào)試程序帶來很大方便。缺點為：遞歸算法的運行效率較低，無論是耗費的計算時間還是占用的存儲空間都比非遞 歸算法要多。分治算法：一個分治法將規(guī)模為n的問題分成k個規(guī)模為n/m勺子問題去解。設(shè)分解閥值 n0=1 ,且adhoc解 規(guī)模為1的問題耗費1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合 并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計算時 間，則有：O(1)T(n)= kT(n/m) f (n)通過迭代法求得

7、方程的解: 算法舉例：logmn-1log 一 kjjT(n) = n m kj f(n/mj)二分搜索技術(shù)：給定已按升序排好序的n個元素a0:n-1j0 ,現(xiàn)要在這n個元素中找出一特定元素X。據(jù)此容易設(shè)計出 二。搜索算法:template int BinarySearch(Type a口，const Type& x, int l, int r)while (r = l)int m = (l+r)/2;if (x = am) return m;if (x am) r = m-1; else l = m+1;return -1;算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)，待搜索數(shù)組的大小減少

8、一半。因此，在最壞情況下， while循環(huán)被執(zhí)行了 O（logn）次。循環(huán)體內(nèi)運算需要 0（1）時間，因此整個算法在最壞情況下 的計算時間復(fù)雜性為O（logn）?？焖倥判蚍ǎ涸诳焖倥判蛑?，記錄的比較和交換是從兩端向中間進行的，關(guān)鍵字較大的記錄一次就 能交換到后面單元，關(guān)鍵字較小的記錄一次就能交換到前面單元，記錄每次移動的距離較大,因而總的比較和移動次數(shù)較少。void Quicksort (Type a, int p, int r) if (Pr) int q=Partition(a,p,r);對左半段排序?qū)τ野攵闻判騋uickSort (a,p,q-1); /QuickSort (a,q+1,

9、r); 復(fù)雜性分析：最壞時間復(fù)雜度： O(n2) 平均時間復(fù)雜度：O(nlogn) 輔助空間：O(n)或O(logn)2.2動態(tài)規(guī)劃動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題但是經(jīng)分解 得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時， 有些子問題被重復(fù)計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得 的答案，就可以避免大量重復(fù)計算，從而得到多項式時間算法。方法步驟：1 ）找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。2）遞歸地定義最優(yōu)值。3）以自底向上的方式計算出最優(yōu)值。4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。舉

10、例：矩陣連成問題基本要素：1）最優(yōu)子結(jié)構(gòu)2）重疊子問題3）備忘錄方法將矩陣連乘積簡記為Ai:j,這里i wj考察計算Ai:j的最優(yōu)計算次序。設(shè)這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i wkj ,則其相應(yīng)完全加括號方式為：（AA書.人）（入引八七.3）計算量：Ai:k的計算量加上Ak+1:j的計算量，再加上Ai:k和Ak+1: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 (i

11、nt i = 1; i = n - r+1; i+) int j=i+r-1;mij = mi+1j+ pi-1*pi*pj;sij = 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的主要計算量取決于算法中對r, i和k的3重循環(huán)。循環(huán)體內(nèi)的計算量為O(1),而3重循環(huán)的總次數(shù)為O(n3)。因此算法的計算時間上界為O(n3)。算法所占用的空間顯然為O(n2)。2.3 貪心算法顧名思義，貪心算法總是作出在當(dāng)前看來最好的選

12、擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是 整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。 如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其 最終結(jié)果卻是最優(yōu)解的很好近似?？捎秘澬乃惴ń鉀Q的問題的性質(zhì)：1)貪心選擇性質(zhì)2)最優(yōu)子結(jié)構(gòu)性質(zhì)舉例：最優(yōu)裝載問題有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wio最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 算法描述最優(yōu)裝載問題可用貪心算法求解。采用

13、重量最輕者先裝的貪心選擇策略，可產(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+) 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

14、+1=pj-1t-j+1Apj-1t-j+2；count+=pjt-j+1;Backtrack(t+1);for (int j=2;j=t;j+)count-=pjt-j+1;count-=i;復(fù)雜度分析計算可行性約束需要 O(n)時間，在最壞情況下有O(2n)個結(jié)點需要計算可行性約束，故解符號三角形問題的回溯算法所需的計算時間為O(n2n)。2.5分支限界法分支限界法常以廣度優(yōu)先或以最小耗費(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點。活結(jié)點一旦成為擴展結(jié)點，就一 次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點

15、被舍棄， 其余兒子結(jié)點被加入活結(jié)點表中。此后，從活結(jié)點表中取下一結(jié)點成為當(dāng)前擴展結(jié)點，并重復(fù)上述結(jié)點擴展過程。這個過程一 直持續(xù)到找到所需的解或活結(jié)點表為空時為止。常見的兩種分支限界法：(1)隊列式(FIFO)分支限界法按照隊列先進先出(FIFO)原則選取下一個節(jié)點為擴展節(jié)點。(2)優(yōu)先隊列式分支限界法按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當(dāng)前擴展節(jié)點。舉例:0-1背包問題算法思想：首先，要對輸入數(shù)據(jù)進行預(yù)處理，將各物品依其單位重量價值從大到小進行排列。在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。算法首先檢查

16、當(dāng)前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將 它加入到子集樹和活結(jié)點優(yōu)先隊列中。當(dāng)前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當(dāng)右兒子 結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。當(dāng)擴展到葉節(jié)點時為問題的最優(yōu)值。 部分算法如下：while (i != n+1) /非葉結(jié)點/檢查當(dāng)前擴展結(jié)點的左兒子結(jié)點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)前擴展結(jié)點的右兒子結(jié)點if (up = bestp) /

17、右子樹可能含最優(yōu)解AddLiveNode(up, cp, cw, false, i+1);/取下一個擴展節(jié)點(略)3結(jié)合0-1背包問題詳述動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法解決問題的過程0-1背包問題： 給定吊中物品和一背包。物品i的重量是wi,其價值為vi ,背包的容量為Co問應(yīng)如 何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？動態(tài)規(guī)劃算法：n設(shè)所給0-1背包問題的子問題max z 曠卜xkk =i, n WkXk & jk =iXk 0,1, i k 三 n的最優(yōu)值為m(i , j),即m(i , j)是背包容量為j ,可選擇物品為i , i+1 ,，n 時0-1背包問題的最優(yōu)

18、值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i, j)的遞歸式如下。m(i, j)=max m(im(i 1, j)0 - jwim(n, j);算法復(fù)雜度分析：vn0j - Wn0 M jWn1, j),m(i 1, j - Wi) Vij - Wi共11頁第9頁c很大時，算法需要從m(i, j)的遞歸式容易看出，算法需要 O(nc)計算時間。當(dāng)背包容量 的計算時間較多。例如，當(dāng)c2n時，算法需要Q(n2n)計算時間。改進算法：由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1 &i &n),函數(shù)m(i,j) 是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點是這一類函數(shù)的描

19、述特征。在一般情況下， 函數(shù)m(i,j)由其全部跳躍點唯一確定。對每一個確定的i(1 & i & n),用一個表pi存儲函數(shù)m(i, j)的全部跳躍點。表pi可依計算m(i , j)的遞歸式遞歸地由表pi+1計算，初始時 pn+1=(0 , 0)。函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作maX1算得到的。因此，函數(shù)m(i,j)的全部跳躍點包含于函數(shù)m(i+1 , j)的跳躍點集pi+1與函數(shù)m(i+1 ,j-wi)+vi 的跳躍點集qi+1的并集中。易知，(s,t) eqi+1當(dāng)且僅當(dāng)wiMsc且 (s-wi,t-vi) 即肝刀0因此，容易由pi+1 確定跳

20、躍點集qi+1 如下qi+1=pi+1二(wi,vi尸(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1另一方面,設(shè)(a, b)和(c, d)是pi+1 =qi+1中的2個跳躍點，則當(dāng) 6 a且db 時，(c , d)受控于(a, b),從而(c , d)不是pi中的跳躍點。除受控跳躍點外， pi+1 =qi+1中的其它跳躍點均為pi中的跳躍點。由此可見，在遞歸地由表pi+1計算表pi時，可先由pi+1計算出qi+1,然 后合并表pi+1和表qi+1,并清除其中的受控跳躍點得到表pi。改進后復(fù)雜性分析：上述算法的主要計算量在于計算跳躍點集pi(1 i n) o由于qi+1=pi+1畬

21、(wi ,vi),故計算 qi+1需要 O(|pi+1|) 計算時間。合并 pi+1和qi+1 并消除受控跳躍點也需要O(|pi+1|)計算時間。從跳躍點集pi的定義可以看出，pi中的跳躍點相應(yīng)于xi,xn的0/1賦值。因此，pi中跳躍點個數(shù)不超過2n-i+1。由此可 見，算法計算跳躍點集pi所花費的計算時間為從而，改進后算法的計算時間復(fù)雜性為 O(2n)。當(dāng)所給物品的重量wi(1 i &n)是整數(shù)時， |pi|c+1,(1 i n)0在這種情況下，改進后算法的計算時間復(fù)雜性為 O(minnc,2n)。貪心算法：在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不 能將物品i裝入背包多次，也不能只裝入部分的物品i。貪心算法的兩條性質(zhì)，可以放入物 品的部分，使它適合背包問題。不適合 0-1背包問題，所以不能用貪心算法計算。 回溯法： 回溯法的三個條件： 解空間：子集樹n可行性約束函數(shù)：、wi xi - c1i =1上界函數(shù)：templateTypep Knap二 BoundQnt i)/計算上界Typew cleft = c - cw; /乘 U 余容量Typep b