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

/算法設(shè)計(jì)與分析大作業(yè)班級(jí)：電子154姓名：吳志勇學(xué)號(hào)：任課老師：李瑞芳日期：2015.12.250-1背包問題的算法設(shè)計(jì)策略對(duì)比與分析0引言對(duì)于計(jì)算機(jī)科學(xué)來說.算法的概念是至關(guān)重要的。在一個(gè)大型軟件系統(tǒng)的開發(fā)中.設(shè)計(jì)出有效的算法將起到?jīng)Q定性的作用。通俗的講.算法是解決問題的一種方法。也因此.《算法分析與設(shè)計(jì)》成為計(jì)算科學(xué)的核心問題之一.也是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科及研究生的一門重要的專業(yè)基礎(chǔ)課。算法分析與設(shè)計(jì)是計(jì)算機(jī)軟件開發(fā)人員必修課.軟件的效率和穩(wěn)定性取決于軟件中所采用的算法；對(duì)于一般程序員和計(jì)算機(jī)專業(yè)學(xué)生.學(xué)習(xí)算法設(shè)計(jì)與分析課程.可以開闊編程思路.編寫出優(yōu)質(zhì)程序。通過老師的解析.培養(yǎng)我們?cè)鯓臃治鏊惴ǖ?好"于"壞".怎樣設(shè)計(jì)算法.并以廣泛用于計(jì)算機(jī)科學(xué)中的算法為例.對(duì)種類不同難度的算法設(shè)計(jì)進(jìn)行系統(tǒng)的介紹與比較。本課程將培養(yǎng)學(xué)生嚴(yán)格的設(shè)計(jì)與分析算法的思維方式.改變隨意拼湊算法的習(xí)慣。本課程要求具備離散數(shù)學(xué)、程序設(shè)計(jì)語言、數(shù)據(jù)結(jié)構(gòu)等先行課課程的知識(shí)。1算法復(fù)雜性分析的方法介紹算法復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源的多少上.所需的資源越多.該算法的復(fù)雜性越高；反之.所需資源越少.該算法的復(fù)雜性越低。對(duì)計(jì)算機(jī)資源.最重要的是時(shí)間與空間〔即存儲(chǔ)器資源。因此.算法的復(fù)雜性有時(shí)間復(fù)雜性T<n>與空間復(fù)雜性S<n>之分。算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量.這個(gè)量應(yīng)集中反映算法的效率.并從運(yùn)行該算法的實(shí)際計(jì)算機(jī)中抽象出來.換句話說.這個(gè)量應(yīng)該只依賴要解決的問題規(guī)模‘算法的輸入和算法本身的函數(shù)。用C表示復(fù)雜性.N,I和A表示問題的規(guī)模、算法的輸入和算法本身規(guī)模.則有如下表達(dá)式：C=F<N,I,A>T=F<N.I,A>S=F<N.I,A>其中F<N,I,A>是一個(gè)三元函數(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ù)雜性一般分為三種情況：最壞情況、最好情況和平均情況。下面描述算法復(fù)雜性時(shí)都是用的簡化的復(fù)雜性算法分析.引入了漸近意義的記號(hào)O,Ω.θ.和o。O表示漸近上界Ω表示漸近下界：θ表示同階即：f<n>=O<g<n>>且f<n>=Ω〔g<n>2常見的算法分析設(shè)計(jì)策略介紹2.1遞歸與分治策略分治法的設(shè)計(jì)思想是.將一個(gè)難以直接解決的大問題.分割成一些規(guī)模較小的相同問題.以便各個(gè)擊破.分而治之。直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式.這就為使用遞歸技術(shù)提供了方便。在這種情況下.反復(fù)應(yīng)用分治手段.可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小.最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟.經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中.并由此產(chǎn)生許多高效算法。遞歸算法舉例：Fibonacci數(shù)列無窮數(shù)列.1.34.55.…….稱為Fibonacci數(shù)列。它可以遞歸地定義為：第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：intfibonacci<intn>{if<n<=1>return1;returnfibonacci<n-1>+fibonacci<n-2>;}從上看出：遞歸算法的有點(diǎn)為：結(jié)構(gòu)清晰.可讀性強(qiáng).而且容易用數(shù)學(xué)歸納法來證明算法的正確性.因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn)為：遞歸算法的運(yùn)行效率較低.無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。分治算法：一個(gè)分治法將規(guī)模為n的問題分成k個(gè)規(guī)模為n／m的子問題去解。設(shè)分解閥值n0=1.且adhoc解規(guī)模為1的問題耗費(fèi)1個(gè)單位時(shí)間。再設(shè)將原問題分解為k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f<n>個(gè)單位時(shí)間。用T<n>表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間.則有：通過迭代法求得方程的解：算法舉例：二分搜索技術(shù)：給定已按升序排好序的n個(gè)元素a[0:n-1].現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二。搜索算法：template<classType>intBinarySearch<Typea[],constType&x,intl,intr>{while<r>=l>{intm=<l+r>/2;if<x==a[m]>returnm;if<x<a[m]>r=m-1;elsel=m+1;}return-1;}算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán).待搜索數(shù)組的大小減少一半。因此.在最壞情況下.while循環(huán)被執(zhí)行了O<logn>次。循環(huán)體內(nèi)運(yùn)算需要O<1>時(shí)間.因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O<logn>?？焖倥判蚍ǎ涸诳焖倥判蛑?記錄的比較和交換是從兩端向中間進(jìn)行的.關(guān)鍵字較大的記錄一次就能交換到后面單元.關(guān)鍵字較小的記錄一次就能交換到前面單元.記錄每次移動(dòng)的距離較大.因而總的比較和移動(dòng)次數(shù)較少。voidQuickSort<Typea[],intp,intr>{if<p<r>{intq=Partition<a,p,r>;QuickSort<a,p,q-1>;//對(duì)左半段排序QuickSort<a,q+1,r>;//對(duì)右半段排序}}復(fù)雜性分析：最壞時(shí)間復(fù)雜度：O<n2>平均時(shí)間復(fù)雜度：O<nlogn>輔助空間：O<n>或O<logn>2.2動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃算法與分治法類似.其基本思想也是將待求解問題分解成若干個(gè)子問題但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí).有些子問題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問題的答案.而在需要時(shí)再找出已求得的答案.就可以避免大量重復(fù)計(jì)算.從而得到多項(xiàng)式時(shí)間算法。方法步驟：1找出最優(yōu)解的性質(zhì).并刻劃其結(jié)構(gòu)特征。2遞歸地定義最優(yōu)值。3以自底向上的方式計(jì)算出最優(yōu)值。4根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息.構(gòu)造最優(yōu)解。舉例：矩陣連成問題基本要素：最優(yōu)子結(jié)構(gòu)重疊子問題備忘錄方法將矩陣連乘積簡記為A[i:j].這里i≤j考察計(jì)算A[i:j]的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開.i≤k<j.則其相應(yīng)完全加括號(hào)方式為：計(jì)算量：A[i:k]的計(jì)算量加上A[k+1:j]的計(jì)算量.再加上A[i:k]和A[k+1:j]相乘的計(jì)算量。算法如下：voidMatrixChain<int*****s>{for<inti=1;i<=n;i++>m[i][i]=0;for<intr=2;r<=n;r++>for<inti=1;i<=n-r+1;i++>{intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for<intk=i+1;k<j;k++>{intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if<t<m[i][j]>{m[i][j]=t;s[i][j]=k;}}}}算法復(fù)雜度分析：算法matrixChain的主要計(jì)算量取決于算法中對(duì)r.i和k的3重循環(huán)。循環(huán)體內(nèi)的計(jì)算量為O<1>.而3重循環(huán)的總次數(shù)為O<n3>。因此算法的計(jì)算時(shí)間上界為O<n3>。算法所占用的空間顯然為O<n2>。2.3貪心算法顧名思義.貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮.它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然.希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解.但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題.最小生成樹問題等。在一些情況下.即使貪心算法不能得到整體最優(yōu)解.其最終結(jié)果卻是最優(yōu)解的很好近似?？捎秘澬乃惴ń鉀Q的問題的性質(zhì)：貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)舉例：最優(yōu)裝載問題有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下.將盡可能多的集裝箱裝上輪船。算法描述 最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略.可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下。template<classType>voidLoading<intx[],Typew[],Typec,intn>{int*t=newint[n+1];Sort<w,t,n>;for<inti=1;i<=n;i++>x[i]=0;for<inti=1;i<=n&&w[t[i]]<=c;i++>{x[t[i]]=1;c-=w[t[i]];}}最優(yōu)裝載問題滿足貪心算法的兩個(gè)基本性質(zhì).可以用貪心算法實(shí)現(xiàn)。2.4回溯法回溯法的基本做法是搜索.或是一種組織得井井有條的.能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中.按深度優(yōu)先策略.從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí).先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含.則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索.逐層向其祖先結(jié)點(diǎn)回溯；否則.進(jìn)入該子樹.繼續(xù)按深度優(yōu)先策略搜索。為了避免生成那些不可能產(chǎn)生最佳解的問題狀態(tài).要不斷地利用限界函數(shù)<boundingfunction>來處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn).以減少問題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法?；厮莘ǖ幕舅枷耄?lt;1>針對(duì)所給問題.定義問題的解空間；<2>確定易于搜索的解空間結(jié)構(gòu)；<3>以深度優(yōu)先方式搜索解空間.并在搜索過程中用剪枝函數(shù)避免無效搜索舉例分析：符號(hào)三角形問題：---+-+++--++--+---+下圖是由14個(gè)"+"和14個(gè)"-"組成的符號(hào)三角形。2個(gè)同號(hào)下面都是"+".---+-+++--++--+---+解法：解向量：用n元組x[1:n]表示符號(hào)三角形的第一行?？尚行约s束函數(shù)：當(dāng)前符號(hào)三角形所包含的"+"個(gè)數(shù)與"-"個(gè)數(shù)均不超過n*<n+1>/4無解的判斷：n*<n+1>/2為奇數(shù)voidTriangle::Backtrack<intt>{if<<count>half>||<t*<t-1>/2-count>half>>return;if<t>n>sum++;elsefor<inti=0;i<2;i++>{p[1][t]=i;count+=i;for<intj=2;j<=t;j++>{p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];count+=p[j][t-j+1];}Backtrack<t+1>;for<intj=2;j<=t;j++>count-=p[j][t-j+1];count-=i;}}復(fù)雜度分析計(jì)算可行性約束需要O<n>時(shí)間.在最壞情況下有O<2n>個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束.故解符號(hào)三角形問題的回溯算法所需的計(jì)算時(shí)間為O<n2n>。2.5分支限界法分支限界法常以廣度優(yōu)先或以最小耗費(fèi)〔最大效益優(yōu)先的方式搜索問題的解空間樹。在分支限界法中.每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn).就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中.導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄.其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后.從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn).并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。常見的兩種分支限界法：〔1隊(duì)列式<FIFO>分支限界法按照隊(duì)列先進(jìn)先出〔FIFO原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)?！?優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。舉例:0-1背包問題算法思想：首先.要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理.將各物品依其單位重量價(jià)值從大到小進(jìn)行排列。在下面描述的優(yōu)先隊(duì)列分支限界法中.節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量價(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn).則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn).僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問題的最優(yōu)值。部分算法如下：while<i!=n+1>{//非葉結(jié)點(diǎn)//檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)Typewwt=cw+w[i];if<wt<=c>{//左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn)if<cp+p[i]>bestp>bestp=cp+p[i];AddLiveNode<up,cp+p[i],cw+w[i],true,i+1>;}up=Bound<i+1>;//檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)if<up>=bestp>//右子樹可能含最優(yōu)解AddLiveNode<up,cp,cw,false,i+1>;//取下一個(gè)擴(kuò)展節(jié)點(diǎn)〔略}3結(jié)合0-1背包問題詳述動(dòng)態(tài)規(guī)劃、貪心算法、回溯法、分支限界法解決問題的過程0-1背包問題：給定n種物品和一背包。物品i的重量是wi.其價(jià)值為vi.背包的容量為C。問應(yīng)如何選擇裝入背包的物品.使得裝入背包中物品的總價(jià)值最大?動(dòng)態(tài)規(guī)劃算法：設(shè)所給0-1背包問題的子問題的最優(yōu)值為m<i.j>.即m<i.j>是背包容量為j.可選擇物品為i.i+1.….n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì).可以建立計(jì)算m<i.j>的遞歸式如下。算法復(fù)雜度分析：從m<i.j>的遞歸式容易看出.算法需要O<nc>計(jì)算時(shí)間。當(dāng)背包容量c很大時(shí).算法需要的計(jì)算時(shí)間較多。例如.當(dāng)c>2n時(shí).算法需要Ω<n2n>計(jì)算時(shí)間。改進(jìn)算法：由m<i,j>的遞歸式容易證明.在一般情況下.對(duì)每一個(gè)確定的i<1≤i≤n>.函數(shù)m<i,j>是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下.函數(shù)m<i,j>由其全部跳躍點(diǎn)唯一確定。對(duì)每一個(gè)確定的i<1≤i≤n>.用一個(gè)表p[i]存儲(chǔ)函數(shù)m<i.j>的全部跳躍點(diǎn)。表p[i]可依計(jì)算m<i.j>的遞歸式遞歸地由表p[i+1]計(jì)算.初始時(shí)p[n+1]={<0.0>}。函數(shù)m<i,j>是由函數(shù)m<i+1,j>與函數(shù)m<i+1,j-wi>+vi作max運(yùn)算得到的。因此.函數(shù)m<i,j>的全部跳躍點(diǎn)包含于函數(shù)m<i+1.j>的跳躍點(diǎn)集p[i+1]與函數(shù)m<i+1.j-wi>+vi的跳躍點(diǎn)集q[i+1]的并集中。易知.<s,t>?q[i+1]當(dāng)且僅當(dāng)wi￡s￡c且<s-wi,t-vi>?p[i+1]。因此.容易由p[i+1]確定跳躍點(diǎn)集q[i+1]如下q[i+1]=p[i+1]?<wi,vi>={<j+wi,m<i,j>+vi>|<j,m<i,j>>?p[i+1]}另一方面.設(shè)<a.b>和<c.d>是p[i+1]èq[i+1]中的2個(gè)跳躍點(diǎn).則當(dāng)c3a且d<b時(shí).<c.d>受控于<a.b>.從而<c.d>不是p[i]中的跳躍點(diǎn)。除受控跳躍點(diǎn)外.p[i+1]èq[i+1]中的其它跳躍點(diǎn)均為p[i]中的跳躍點(diǎn)。由此可見.在遞歸地由表p[i+1]計(jì)算表p[i]時(shí).可先由p[i+1]計(jì)算出q[i+1].然后合并表p[i+1]和表q[i+1].并清除其中的受控跳躍點(diǎn)得到表p[i]。改進(jìn)后復(fù)雜性分析：上述算法的主要計(jì)算量在于計(jì)算跳躍點(diǎn)集p[i]<1≤i≤n>。由于q[i+1]=p[i+1]?<wi.vi>.故計(jì)算q[i+1]需要O<|p[i+1]|>計(jì)算時(shí)間。合并p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要O<|p[i+1]|>計(jì)算時(shí)間。從跳躍點(diǎn)集p[i]的定義可以看出.p[i]中的跳躍點(diǎn)相應(yīng)于xi,…,xn的0/1賦值。因此.p[i]中跳躍點(diǎn)個(gè)數(shù)不超過2n-i+1。由此可見.算法計(jì)算跳躍點(diǎn)集p[i]所花費(fèi)的計(jì)算時(shí)間為從而.改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O<2n>。當(dāng)所給物品的重量wi<1≤i≤n>是整數(shù)時(shí).|p[i]|≤c+1.<1≤i≤n>。在這種情況下.改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為O<min{nc,2n}>。貪心算法：在選擇裝入背包的物品時(shí).對(duì)每種物品i只有2種選擇.即裝入背包或不裝入背包。不能將物品i裝入背包多次.也不能只裝入部分的物品i。貪心算法的兩條性質(zhì).可以放入物品的部分.使它適合背包問題。不適合0-1背包問題.所以不能用貪心算法計(jì)算?；厮莘ǎ夯厮莘ǖ娜齻€(gè)條件：解空間：子集樹可行性約束函數(shù)：上界函數(shù)：template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound<