背包問題的算法研究與實現(xiàn)本科畢業(yè)論文

1、華中師范大學(xué)漢口分校華中師范大學(xué)漢口分校 本本 科科 畢畢 業(yè)業(yè) 論論 文文 0-10-1 背包問題的算法研究與實現(xiàn)背包問題的算法研究與實現(xiàn) 院院 系：系：信息科學(xué)技術(shù)學(xué)院信息科學(xué)技術(shù)學(xué)院 專專 業(yè)：業(yè)：計算機科學(xué)與技術(shù)計算機科學(xué)與技術(shù) 年年 級：級： 20052005 級級 學(xué)學(xué) 生：生： 劉念劉念 學(xué)學(xué) 號：號： 20059110322005911032 指導(dǎo)老師：指導(dǎo)老師： 賓云峰、楊健賓云峰、楊健 華中師范大學(xué)漢口分校 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下獨立進(jìn)行研究工作 所取得的研究成果。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何 其他個人或集

2、體已經(jīng)發(fā)表或撰寫的成果作品。本人完全意識到本聲明的法律后 果由本人承擔(dān)。 學(xué)位論文作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保障、使用學(xué)位論文的規(guī)定，同意學(xué)校 保留并向有關(guān)學(xué)位論文管理部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文 被查閱和借閱。本人授權(quán)省級優(yōu)秀學(xué)士學(xué)位論文評選機構(gòu)將本學(xué)位論文的全部 或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段 保存和匯編本學(xué)位論文。 本學(xué)位論文屬于 1、保密 ，在_年解密后適用本授權(quán)書。 2、不保密 。 （請在以上相應(yīng)方框內(nèi)打“” ） 學(xué)位論文作者簽名： 日期： 年 月

3、日 導(dǎo)師簽名： 日期： 年 月 日 目目 錄錄 內(nèi)容摘要.1 關(guān) 鍵 詞.1 abstract.2 key words.2 1 緒論.3 1.1 問題的提出及研究意義 .3 1.2 0-1 背包問題的算法研究的分析.3 1.3 課題的主要研究內(nèi)容 .4 2 0-1 背包問題的實現(xiàn) .5 2.1 0-1 背包問題在動態(tài)規(guī)劃中的實現(xiàn).5 2.2 0-1 背包問題在回溯法中的實現(xiàn).8 2.3 0-1 背包問題在分枝-限界法中的實現(xiàn).12 2.4 0-1 背包問題在遺傳算法中的實現(xiàn).16 3 解 0-1 背包問題的算法比較與分析.20 4 總結(jié)與展望 .22 參考文獻(xiàn).23 致 謝.25 內(nèi)容摘要內(nèi)容

4、摘要：背包問題是一個在運籌學(xué)領(lǐng)域里常見的典型 np-c 難題，也是算 法設(shè)計分析中的經(jīng)典問題，對該問題的求解方法的研究無論是在理論上,還是在 實踐中都具有重要意義。對這個問題的求解已經(jīng)研究出了不少的經(jīng)典方法，對 該問題的探索和應(yīng)用研究一直在進(jìn)行。在先進(jìn)理論指導(dǎo)下，求解 0-1 背包問題 具有科學(xué)、高效、經(jīng)濟、靈活、方便等顯著特點。 那么要解決背包問題，首要的前提就是設(shè)計出好的算法，想求得背包問題 的解，就要先設(shè)計出算法,本文采用動態(tài)規(guī)劃法，回溯法，分枝-限界法，遺傳 算法四種方法分別對背包問題、0-1 背包問題及簡單 0-1 背包問題進(jìn)行算法設(shè) 計和時間復(fù)雜度分析，給出具體算法設(shè)計和實現(xiàn)過程。

5、并以具體實例詳細(xì)描述 不同方法求解問題解時算法基本思想，然后就解決 0-1 背包問題對這四種算法 進(jìn)行詳細(xì)的比較，總結(jié)四種方法實現(xiàn)的優(yōu)缺點并得出結(jié)論。如何將背包問題應(yīng) 用于實際問題中，有針對性地設(shè)計適合求解實際 0-1 背包問題的算法，并很好 地解決實際問題，是計算機工作者不斷思索、研究的一個領(lǐng)域。 關(guān)關(guān) 鍵鍵 詞詞：0-1 背包 動態(tài)規(guī)劃 回溯法 分枝-限界法 遺傳算法 abstractabstract： knapsack problem is a typical np-c problem as well as algorithm design and analysis of the cla

6、ssical problems in the common field of operations research. it is very important to study the solution of the problem, whether in theory or in practice. after some research, a lot of classical methods solving this problem have been come up with ,and the exploration of this issue and applied research

7、 has been ongoing. under the guidance of advanced theory, there are distinctive features such as scientific, efficient, economic, flexible and convenient features in solving the 0-1 knapsack problem . so to solve the knapsack problem, the first premise is to design a good algorithm.to seek the solut

8、ion of knapsack problem, it is necessary to design algorithms using dynamic programming at first. in this paper, four methods such as dynamic programming, backtracking, branch - bound method and genetic algorithm respectively aiming at knapsack problem ,0-1 knapsack problem and a simple 0-1 knapsack

9、 problem carry out the algorithm design and analysis of time complexity, and give the specific algorithm design and implementation of the process.and descript detailedly the basic idea of algorithm by using specific examples in solving the issue with different ways .and then aiming at solving the 0-

10、1 knapsack problem , compare four algorithms in detail and summarize the advantages and disadvantages of realization of four methods and reach a conclusion.how to apply the knapsack problem into the practical, and to design targeted for the practical algorithms of solving 0-1 knapsack problem and to

11、 solve the practical problems very well, is an area of computer workers constantly thinking and study. keykey wordswords：0-1 knapsack problem dynamic programmi backtracking branch - bound method genetic algorithm 1 1 緒論緒論 1.11.1 問題的提出及研究意義問題的提出及研究意義 0-1 背包問題是計算機科學(xué)中的一個非常經(jīng)典的優(yōu)化問題。也是被證明了 的 np 難度問題。它是在 1

12、978 年由 merkel 和 hellman 提出的。它的主要思路 是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并將 它們放到背包中來加密消息。背包中的物品中重量是公開的，所有可能選擇的 物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量， 而要列出可能的物品，在計算上是不可實現(xiàn)的。背包問題是熟知的不可計算問 題，背包體制以其加密，解密速度快而其人注目。但是，大多數(shù)一次背包體制 均被破譯了，因此現(xiàn)在很少有人使用它。圍繞這個問題的求解方法很多，比如 貪婪算法、動態(tài)規(guī)劃、分枝限界、回溯法、遺傳算法等等。其中回溯法是常見 的一種求解方法。 多年來，背包問題吸引

13、了許多理論和實際工作者對此問題作深入的研究， 在理論上，盡管背包問題的結(jié)構(gòu)簡單，但它卻具有組合爆炸的性質(zhì)，在實際應(yīng) 用中，許多工業(yè)問題都可以用背包問題來描述求解，如資金運算、貨艙裝載、 存儲分配等都是其典型的應(yīng)用例子。如何將背包問題應(yīng)用于實際問題中，并很 好地解決實際問題，是計算機工作者不斷思索、研究的一個領(lǐng)域。 1.21.2 0-10-1 背包問題的算法研究的分析背包問題的算法研究的分析 0-1 背包問題的算法研究主要是通過算法設(shè)計與分析知識，設(shè)計解決相關(guān) 問題的盡可能高效的算法并程序?qū)崿F(xiàn)，而且能夠分析算法的復(fù)雜性，通過實驗 進(jìn)一步領(lǐng)會各種算法設(shè)計技術(shù)的基本原理，掌握算法設(shè)計和分析方法，提高

14、算 法設(shè)計與分析的應(yīng)用能力。 0-1 背包是一類很典型的優(yōu)化問題,研究它有很重要的實際意義，這不僅是 由于它結(jié)構(gòu)簡潔，可以作為子問題為研究更復(fù)雜的問題奠定理論基礎(chǔ)，有很高 的理論研究價值，而且由于它是許多實際工程應(yīng)用問題的種通用化描述，在很 多實際問題當(dāng)中有著非常廣泛的應(yīng)用背景，例如項目決策等。他是最基本的背 包問題，即對一個物體要么選用，要么就拋棄，不能將一個物體再繼續(xù)細(xì)分的 情況。它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，在經(jīng)濟管理、資源 分配、投資決策、裝載設(shè)計等領(lǐng)域有著重要的應(yīng)用價值。在計算理論中屬于 np-c 完全問題，其計算復(fù)雜度，傳統(tǒng)上采用動態(tài)規(guī)劃來求解。背包問題就是在 資源

15、有限的條件下，追求總的最大收益的資源有效分配問題。 1.31.3 課題的主要研究內(nèi)容課題的主要研究內(nèi)容 .1 背包問題的描述背包問題的描述 背包問題是整數(shù)規(guī)劃中的一類特殊問題，在現(xiàn)實生活中具有廣泛應(yīng)用。如 果能提出求解此問題的有效算法，則具有很好的經(jīng)濟價值和決策價值。 問題的一般描述是：旅行者背包登山，背包的最大承重為 m，現(xiàn)有 n 個物 品可供選擇裝入背包，第 i 個物品鶯量為 wi，價值為 pi，假定物品 i 的一部分 xi(0 xi1)放人背包，獲得價值為 xipi，由于背包最大承重為 m，要求裝入物 品總質(zhì)量不過超過 m，問旅行者應(yīng)該如何選擇物品裝入背包，使得裝入物品的

16、 價值總和達(dá)到最大值。 背包問題的數(shù)學(xué)描述如下：要求找到一個 n 元向量(x1，x2xn)，在滿足 約束條件：情況下，使得目標(biāo)函數(shù)，其中， 10 i ii x mwx p x i i max 1in；m0；wi0；pi0。滿足約束條件的任何向量都是一個可行解，而使 得目標(biāo)函數(shù)達(dá)到最大的那個可行解則為最優(yōu)解1。 .2 0-10-1 背包問題背包問題 0-1 背包問題的提出 給定 n 種物品和 1 個背包。物品 i 的重量是 wi，其價值為 pi，背包的容 量為 m。問應(yīng)如何裝入背包中的物品，使得裝人背包中物品的總價值最大？在 選擇裝人背包的物品時，對每種物品 i 只有兩種選擇，即

17、裝入背包、不裝入背 包。不能將物品 i 裝人背包多次，也不能只裝入部分的物品 i。該問題稱為 0- 1 背包問題。 問題符號化 0-1 背包問題的符號化表示是，給定 m0， w i 0， pi 0，1in ， 要求找到一個 n 元 0-1 向量向量(x1，x2xn)， x i =0 或 1 , 1in, 使得 ，而且達(dá)到最大2。mwx ii px i i 2 2 0-10-1 背包問題的實現(xiàn)背包問題的實現(xiàn) 2.12.1 0-10-1 背包問題在動態(tài)規(guī)劃中的實現(xiàn)背包問題在動態(tài)規(guī)劃中的實現(xiàn) .1 動態(tài)規(guī)劃的基本原理與分析動態(tài)規(guī)劃的基本原理與分析 動態(tài)規(guī)劃算法的基本思想是將待求解問題

18、分解成若干個子問題，先求解子 問題，然后從這些子問題的解得到原問題的解。但是經(jīng)分解得到的子問題往往 不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。如果能夠保存已解 決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復(fù)計 算，從而得到多項式時間算法。它把已知問題分為很多子問題，按順序求解子 問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可 能產(chǎn)生最佳的結(jié)果舍棄其余。前一子問題為后面子問題提供信息，而減少計算 量，最后一個子問題的解即為問題解。采用此方法求解 0-1 背包問題的主要步 驟如下： 分析最優(yōu)解的結(jié)構(gòu)：最有子結(jié)構(gòu)性質(zhì)； 建立遞歸方程； 計算最優(yōu)值；

19、 構(gòu)造最優(yōu)解4。 動態(tài)規(guī)劃算法的每一步?jīng)Q策都是根據(jù)前一步的狀態(tài)參量來決定這一步狀態(tài) 參量的設(shè)置，也就是說，從初始狀態(tài)到最終狀態(tài)要經(jīng)過多個過程，經(jīng)歷不同的 狀態(tài)，不斷地根據(jù)上一步狀態(tài)決定下一狀態(tài)，從而形成了一個決策序列，最終 將整個問題解決，這就是典型的多段決策的特性。 由上面的動態(tài)規(guī)劃法的介紹，可以看出 0-1 背包問題，是符合多段決策的 特點和具有重疊子問題。因此，在設(shè)計 0-1 背包問題解決方案時，可以將整個 物品放到背包的過程，看成一個取物品的過程。 .2 0-10-1 背包問題的實現(xiàn)背包問題的實現(xiàn) 最優(yōu)子結(jié)構(gòu)性質(zhì) 0-1 背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)(y1，y2yn)

20、是所給 0-1 背包問題 的一個最優(yōu)解，則(y2，y3yn)是下面相應(yīng)子問題的一個最優(yōu)解： n ik kkx vmax nkix jxw k n ik kk ,1 , 0 因若不然，設(shè)(z2，z3zn)是上述問題的一個最優(yōu)解，而(y2，y3yn)不 是它的最優(yōu)解，由此可見,且c。因此 n i 2 n i iiy v 2 n i iiz w 2 w1y1 n i iiz v 2 v1y1 n i iiy v 1 c n i iiz w 2 w1y1 這說明(y1，z2zn)是所給 0-1 背包問題的一個更優(yōu)解，從而(y1，y2yn)不 是所給 0-1 背包問題的最優(yōu)解。此為矛盾1。 遞歸關(guān)系 設(shè)

21、所給 0-1 背包問題的子問題 n ik kkx vmax nkix jxw k n ik kk ,1 , 0 的最優(yōu)值為 m(i,j)，即 m(i,j)是背包容量為 j，可選擇物品為 i，i+1，n 時 0-1 背包問題的最優(yōu)值。由 0-1 背包問題的最優(yōu)子結(jié)構(gòu)性 質(zhì)，可以建立計算 m(i,j)的遞歸式如下： wjjjim wijviwijimjim 0), 1( ,), 1(),),1(max j)m(i, wnj wnvnj 0 j)m(n, 算法描述 基于以上討論，當(dāng) wi(1 i n)為正整數(shù)時，用二維數(shù)組 m來存儲 m(i,j)的相應(yīng)值，可設(shè)計解 0-1 背包問題的動態(tài)規(guī)劃算法 k

22、napsack 入下： template void knapsack(type v,int w,int c,int n,type* * m) int jmax=min(wn-1,c); for (int j=0;j=jmax;j+)mnj=0; for (int j=wn;j1;i-) jmax=min(wi-1,c); for (int j=0;j=jmax;j+)mij=mi+1j; for(intj=wi;j=w1) m1c=max(m1c,m2c-w1+v1); template void traceback(type* * m,int w,int c,int n,int x) for

23、 (int i=1;i=n;i+) if(mic=mi+1c) xi=0; else xi =1;c-= wi; xn=(mnc)?1:0; 1 計算復(fù)雜性分析 利用動態(tài)規(guī)劃求解 0-1 背包問題的復(fù)雜度為 0(minnc,2n。動態(tài)規(guī)劃主要 是求解最優(yōu)決策序列，當(dāng)最優(yōu)決策序列中包含最優(yōu)決策子序列時，可建立動態(tài) 規(guī)劃遞歸方程，它可以幫助高效地解決問題8。 2.22.2 0-10-1 背包問題在回溯法中的實現(xiàn)背包問題在回溯法中的實現(xiàn) .1 回溯法的基本原理與分析回溯法的基本原理與分析 回溯是一種系統(tǒng)地搜索問題解答的方法。為了實現(xiàn)回溯，首先需要為問題 定義一個解空間，這個解空間必須

24、至少包含問題的一個解(可能是最優(yōu)的)?；?溯法需要為問題定義一個解空間，這個解空間必須至少包含問題的一個解(可能 是最優(yōu)的)。 使用遞歸回溯法解決背包問題的優(yōu)點在于它算法思想簡單，而且它能完全 遍歷搜索空間，肯定能找到問題的最優(yōu)解奉但是由于此問題解的總組合數(shù)有 個，因此隨著物件數(shù) n 的增大，其解的空間將以 n級增長，當(dāng) n 大到一定 n 2 n 2 程度上，用此算法解決背包問題將是不現(xiàn)實的。 下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹。 一旦定義了解空間的組織方法，這個空間即可按照深度優(yōu)先的方法從開始結(jié)點 進(jìn)行搜索，利用限界函數(shù)避免移動到不可能產(chǎn)生解的子空間。 2.2.2

25、2.2.2 0-10-1 背包問題的實現(xiàn)背包問題的實現(xiàn) 回溯法的算法描述 回溯法是一種系統(tǒng)地搜索問題解答的方法。為了實現(xiàn)回溯，首先需要為問 題定義一個解空間，這個解空間必須至少包含問題的一個解(可能是最優(yōu)的)。 一旦定義了解空間的組織方要選擇一個對象的子集，將它們裝人背包，以便獲 得的收益最大，則解空間應(yīng)組織成子集樹的形狀。首先形成一個遞歸算法，去 找到可獲得的最大收益。然后，對該算法加以改進(jìn)，形成代碼。改進(jìn)后的代碼 可找到獲得最大收益時包含在背包中的對象的集合。 左子樹表示一個可行的結(jié)點，無論何時都要移動到它，當(dāng)右子樹可能含有 比當(dāng)前最優(yōu)解還優(yōu)的解時，移動到它。一種決定是否要移動到右子樹的簡

26、單方 法是 r 為還未遍歷的對象的收益之和，將 r 加到 cp (當(dāng)前節(jié)點所獲收益)之上， 若( r+cp) bestp(目前最優(yōu)解的收益)，則不需搜索右子樹。一種更有效的方 法是按收益密度 vi/wi 對剩余對象排序，將對象按密度遞減的順序去填充背包 的剩余容量， 當(dāng)遇到第一個不能全部放人背包的對象時， 就使用它的一部分。 解 0-1 背包問題的回溯算法描述如下： template class knap friend typep knapsack(typep*,typew*,typew,int); private： typep bound(int i); void backtrack(int

27、 i); typew c; /背包容量 int n; /物品數(shù) typew*w; /物品重量數(shù)組 typep*p; /物品價值數(shù)組 typew cw; /當(dāng)前重量 typep cp; /當(dāng)前價值 typep bestp; /當(dāng)前最優(yōu)價值 ; template void knap:backtrack(int i) if(in)/到達(dá)葉結(jié)點 bestp=cp; return; if(cw+wibestp) /進(jìn)入右子數(shù) backtrack(i+1); template typep knap:bound(int i) /計算上界 typew cleft=c-cw; /剩余容量 typep b=cp;

28、 /以物品單位重量價值遞減序裝入物品 while (i=n b+=pi; i+; /裝滿背包 if(i=n)b+=pi* cleft/wi; return b; class object friend int knapsack(int*,int *,int,int); public; int operator=a.d); private: int id; float d; ; template typep knapsack(typep p, typep w,typew c,int n) /為 knap:backtrack 初始化 typew w=0; typep p=0; object*q=n

29、ew objectn; for(int i=1;i=n;i+) qi-1.id=i; qi-1.d=1.0*pi/wi; p+=pi; w+=wi; if(w=c)return p;/裝入所有物品 /依物品單位重量價值排序 sort(q,n); knapk; k.p=new typepn+1; k.w=new typewn+1; for (int i=1;i=n;i+) k.pi=pqi-1.id; k.wi=wqi-1.id; k.cp=0; k.cw=0; k.c=c; k.n=n; k.bestp=0; /回搠搜索 k.backtrack(1); deleteq; deletek.w;

30、deletek.p; reture k,bestp; 1 算法效率 由于計算上界函數(shù)需要 o(n)時間，在最壞情況下有 o()個右孩子結(jié)點需 n 2 要上界函數(shù)，故計算 0-1 背包問題的回溯算法所需的計算時間復(fù)雜度為 o(n)。 n 2 對回溯法的改進(jìn)主要是對判斷是否移動右子樹上，一種更有效的方法是按效益 密度 vi/wi 對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量， 當(dāng)遇到第一個不能全部放人背包的對象時，就使用它的一部分。 回溯算法的運行時間取決于它在搜索過程中所生成的結(jié)點數(shù),而限界函數(shù) 可以大量減少所生成的結(jié)點個數(shù),省去許多無謂的搜索, 使得搜索速度更快 , 其調(diào)用限界函

31、數(shù)計算上界需花費 o(n)時間 ,最壞情況下有 o()個結(jié)點需調(diào)用 n 2 限界函數(shù) ,需花費 o(n)時間,所以該算法的時間復(fù)雜度為 o(n)12。 n 2 回溯法的另一個重要特性就是在搜索執(zhí)行的同時產(chǎn)生解空間 在搜索期間 的任何時刻 僅保留從開始結(jié)點到當(dāng)前可擴展結(jié)點的路徑其空間需求為 o(從開 始結(jié)點起最長路徑的長度),所以 ,此處該算法的空間復(fù)雜度為 o(n),回溯法是 算法設(shè)計的基本方法之一 ,它適用于解一些涉及到尋找一組解的問題或者求滿 足某些約束條件的最優(yōu)解的問題,且適用于求解組合數(shù)量較大的問題。 2.32.3 0-10-1 背包問題在分枝背包問題在分枝- -限界法中的實現(xiàn)限界法中

32、的實現(xiàn) .1 分枝分枝- -限界法的基本原理與分析限界法的基本原理與分析 分枝限界發(fā)是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于 對 e-結(jié)點(expansion node)的擴充方式。每個活結(jié)點有且僅有一次會變成 e-結(jié) 點。當(dāng)一個結(jié)點變?yōu)?e-結(jié)點時，則生成從該結(jié)點移動一步即可到達(dá)的所有新結(jié) 點。在生成的結(jié)點中，拋棄那些不可能導(dǎo)出(最優(yōu))可行解的結(jié)點，其余結(jié)點加 人活結(jié)點表，然后從表中選擇一個結(jié)點作為下一個 e 結(jié)點。從活結(jié)點表中取出 所選擇的結(jié)點并進(jìn)行擴充，直到找到解或活動表為空，擴充才結(jié)束。 有兩種常用的方法可用來選擇下一個 e-結(jié)點: 先進(jìn)先出(fifo)

33、即從活結(jié)點表中取出結(jié)點的順序與加人結(jié)點的順序相 同，因此活結(jié)點表的性質(zhì)與隊列相同。 最小耗費或最大收益法在這種模式中，每個結(jié)點都有一個對應(yīng)的耗費 或收益。如果查找一個具有最小耗費的解，則活結(jié)點表可以最小堆來建立，下 一個 e-結(jié)點就是具有最小耗費的活結(jié)點，如果希望搜索一個具有最大收益的解， 則可用最大堆來構(gòu)造活結(jié)點表，下一個 e-結(jié)點是具有最大收益的活結(jié)點15。 .2 0-10-1 背包問題的實現(xiàn)背包問題的實現(xiàn) 工作在解空間樹上的 fifo 分枝定界方法非常類似于從根結(jié)點出發(fā)的寬度優(yōu) 先搜索。它們的主要區(qū)別時在 fifo 分枝定界中不可行的結(jié)點不會被搜索。 0-1 背包問題的最

34、大收益分枝定界算法可以使用定界函數(shù)來計算活結(jié)點的 收益上限 upprofit，使得以活結(jié)點為根的子樹中的任一結(jié)點的收益值都不可能 超過 upprofit，活結(jié)點的最大堆使用 upprofit 作為關(guān)鍵值域。在子集樹中執(zhí) 行最大收益分枝定界搜索的函數(shù)首先初始化活結(jié)點的最大堆，并使用一個數(shù)組 bestx 來記錄最優(yōu)解。由于需要不斷地利用收益密度來排序，物品的索引值會 隨之變化，因此必須將函數(shù)所生成的結(jié)果映射回初始時的物品索引。函數(shù)中的 循環(huán)首先檢驗 e-結(jié)點左孩子的可行性，如它是可行的，則將它加入子集樹及活 結(jié)點隊列(即最大堆)，僅當(dāng)結(jié)點右子樹的定界值指明可能找到一個最優(yōu)解時才 將右孩子加入子集樹

35、和隊列中。 則主要算法描述為： class object friend int knapsack(int *,int *,int,int,int *); public: int operator=a.d); private: int id; float d;/單位重量價值 ; template class knap; class bbnode friend knap; friend int knapsack(int *,int *,int,int,int *); private: bbnode *parent; /指向父結(jié)點的指針 bool lchild; /左兒子結(jié)點標(biāo)志 ; templat

36、e class heapnode friend knap; public: operator typep () const return uprofit; private: typep uprofit, /結(jié)點的價值上界 profit; /結(jié)點所相應(yīng)的價值 typew weight; /結(jié)點所相應(yīng)的重量 int level; /活結(jié)點在子集樹中所處的層序號 bbnode *ptr; /指向活結(jié)點在子集樹中相應(yīng)結(jié)點的指針 ； template class knap friend typep knapsack(typep *,typew *,typew,int,int *); public: ty

37、pep maxknapsack(); private: maxheapheapnode*h; typep bound(int i); void addlivenode(typep up,typep cp,typep cw,bool ch,int level); bbnode *e; /指向擴展結(jié)點的指針 typew c; /背包容量 int n; /物品總數(shù) typew *w; /物品重量數(shù)組 typep *p; /物品價值數(shù)組 typew cw; /當(dāng)前裝包重量 typep cp; /當(dāng)前裝包價值 int * bestx; /最優(yōu)解 ; template typep knap:maxknap

38、sack() /優(yōu)先隊列式分支限界法，返回最大價值，bestx 返回最優(yōu)解 /定義最大堆的容量為 1000 h=new maxheapheapnode(1000); /為 bestx 分配存儲空間 bestx=new intn+1; /初始化 int i=1; e=0; cw =cp =0; typep bestp =0; /當(dāng)前最優(yōu)值 typep up =bound(1); /價值上界 /搜索子集空間樹 while(i!=n+1)/ 非葉結(jié)點 /檢查當(dāng)前擴展結(jié)點的左兒子結(jié)點 typew wt =cw +wi; if(wtbestp)bestp=cp+pi; addlivenode(up,cp

39、+pi,cw+wi,ture,i+1); up =bound(i+1); /檢查當(dāng)前擴展結(jié)點的右兒子結(jié)點 if(up=bestp)/右子樹可能含最優(yōu)解 addlivenode(up,cp,cw,false,i+1); /取下一擴展結(jié)點 heapnoden; h-deletemax(n); e=n.ptr; cw=n.weight; cp=n.profit; up=n.uprofit; i=n.level; /構(gòu)造當(dāng)前最優(yōu)解 for(int j=n;j0;j-) bestxj=e-lchild; e=e-parent; return cp; 1 2.42.4 0-10-1 背包問題在遺傳算法中的

40、實現(xiàn)背包問題在遺傳算法中的實現(xiàn) .1 遺傳算法的基本原理與分析遺傳算法的基本原理與分析 遺傳算法作為一種解決復(fù)雜問題的有效方法是在 1975 年首次由美國密西 根大學(xué)的 hol-land 教授和他的同事們借鑒生物界自然選擇和進(jìn)化機制基礎(chǔ)之 上提出的，它是基于生物進(jìn)化中自然選擇、適者生存和物種遺傳思想的一種搜 索算法。它將問題的每一個可能解看作是群體中的一個個體(染色體)，并將每 一個染色體編碼成串的形式，再根據(jù)預(yù)定的目標(biāo)函數(shù)對每個個體進(jìn)行評價，給 出一個適應(yīng)值。算法將根據(jù)適應(yīng)值進(jìn)行尋優(yōu)過程。遺傳算法的尋優(yōu)過程是通過 選擇、雜交和變異等遺傳算子來具體實現(xiàn)的，它的搜索能力由選擇算子

41、和雜交 算子決定，變異算子則保證了算法能夠搜索到問題空間的每一個點，從而使其 具有搜索全局最優(yōu)的能力。遺傳算法的高效性和強壯性可由 holland 提出的模 式定理和隱式并行性得以解釋。在遺傳算法中，定義長度較短、低階且適應(yīng)值 超過平均適應(yīng)值的模式在群體中數(shù)目的期望值按指數(shù)遞增，這個結(jié)論成為遺傳 算法的基本定理。 遺傳算法可看成是在一個定義域為 l 維的向量空問 b。中有一適應(yīng)度函數(shù)， 依其適應(yīng)度大小，隨機進(jìn)行選擇、交叉和變異操作來求此函數(shù)的最大值，即將 遺傳算法看成是在某個空間進(jìn)行求最大值的搜索技術(shù)。在操作中，新點主要是 由交叉操作產(chǎn)生。傳統(tǒng)的交叉算子是隨機操作，后代簡單地繼承了“父母”的

42、一部分基因，并不能保證子代的性能優(yōu)于父輩，而且以這種方式點對點的搜索 范圍有限，可能會忽略鄰域內(nèi)更好的點而使結(jié)果收斂于局部最優(yōu)。 .2 0-10-1 背包問題的實現(xiàn)背包問題的實現(xiàn) (1) 編碼方案: 用遺傳算法來求解 0-1 背包問題，一種很自然的編碼方案 是將待求解的各量 x 表示成長為 n 的二進(jìn)制字符串 xi,j=1,2,n,xi=1 表 示物體 j 放人背包，xj表示物體 j 放入背包。 (2) 適應(yīng)度函數(shù)的設(shè)計: 基于上述編碼，按照所提出的罰函數(shù) 處理約束條 件的方法構(gòu)造背包問題的適應(yīng)度函數(shù) (x):(x)=- = 1 () 這里，對于所有滿足條c 的可行解 x，懲罰

43、函數(shù) va(x)=0 = 1 懲罰函數(shù)可以使用對數(shù)函數(shù)，線性函數(shù)，二次函數(shù)等，分別隨侵犯的程度增加 而順序采用。 (3) 選擇操作：根據(jù)選擇概率選擇染色體，將上述的個體作為第 0 代。對 于每個染色體，計算累積概率 qi，從區(qū)間(0, qi) 種產(chǎn)生一個隨機數(shù) r，若 qi -1rqi，則選擇第 i 個染色體，重復(fù)上述操作，復(fù)制染色體。 (4) 交叉操作：判斷染色體是否為活的染色體，若為活的染色體，則將染 色體進(jìn)行交叉，一般采用單點交叉方式。 (5) 變異操作：染色體變異采用位點變異的方式。使變異后的適應(yīng)度至少 大于等于原適應(yīng)度，否則重新選擇變異位進(jìn)行變異，如此重復(fù)若干次，若適應(yīng) 度值沒有提高

44、，則變異失敗。 (6) 當(dāng)某代得到的結(jié)果滿足要求或當(dāng)前代數(shù)等于結(jié)束代數(shù)時算法結(jié)束得到 結(jié)果，否則重復(fù)上述步驟(3)、(4) 7 7。 則主要算法描述為： procedure search(k,v:integer); 搜索第 k 個物品，剩余空間為 v var i,j:integer; begin if v=best then exit; sn為前 n 個物品的重量和 if kwk then search(k+1,v-wk); search(k+1,v); end; end; l dp fi,j為前 i 個物品中選擇若干個放入使其體積正好為 j 的標(biāo)志，為 布爾型。 實現(xiàn): a:將最優(yōu)化問題轉(zhuǎn)化

45、為判定性問題 f i, j = f i-1, j-wi (wi=j0 then if j+now=n then inc(cj+now,aj); a:=c; end9; 3 3 解解 0-10-1 背包問題的算法比較與分析背包問題的算法比較與分析 這四種算法都得到了驗證，運行結(jié)果證明了算法設(shè)計是可行的，正確的。 通過對 o-1 背包問題的算法設(shè)計及時間復(fù)雜度分析可以看出。無論采用貪婪法 還是動態(tài)規(guī)劃法，都是在已知約束條件下求解最大值建立數(shù)學(xué)模型算法實現(xiàn)的 過程；但算法具體實現(xiàn)和數(shù)據(jù)結(jié)構(gòu)的建立要用到遞歸和棧操作。比較貪婪法和 動態(tài)規(guī)劃法。前者的時間復(fù)雜度低于后者，從耗費上而言優(yōu)于后者。但后者的 實

46、現(xiàn)算法可讀性要優(yōu)于前者。 動態(tài)規(guī)劃算法的基本思想是把原問題分解為一系列子問題，然后從這些子 問題中求出原問題的解?；厮萜鋵嵕褪歉F舉，窮舉所有的解，找出解中最優(yōu)的 值?；厮莘ㄔ诎瑔栴}的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié) 點出發(fā)搜索解空間樹?；厮莘ǖ幕舅悸肥牵捍_定解空間，建立解空間樹，用 深度優(yōu)先搜索算法遞歸搜索解空間樹，并同時注意剪枝,常用的分枝一限界法有 最小耗費法，最大收益法。fifo(先進(jìn)先出)法等。0-1 背包問題的分枝一限界 算法可以使用最大收益算法。該算法跟回溯法類似。但分枝限界法需要 o() n 2 的解空間。故該算法不常用在背包問題求解。遺傳算法是計算數(shù)學(xué)中用于解

47、決 最優(yōu)化的搜索算法，是一種進(jìn)化算法。對于一個最優(yōu)化問題，一定數(shù)量的候選 解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進(jìn)化。通常解用 二進(jìn)制 0 和 1 表示，進(jìn)化從一個個體發(fā)生，然后一代一代發(fā)生。在每一代中， 該種群的價值被評估，從當(dāng)前種群中隨機地選擇多個個體（基于它們的適應(yīng)度） ， 通過自然選擇。 回溯法比分枝限界在占用內(nèi)存方面具有優(yōu)勢?；厮莘ㄕ加玫膬?nèi)存是 0(解空 間的最大路徑長度)，而分枝限界所占用的內(nèi)存為 0(解空間大小)。對于一個子 集空間，回溯法需要 0(n)的內(nèi)存空間，而分枝限界則需要 0(2n)的空間。雖然 最大收益或最小耗費分枝限界在直覺上要好于回溯法，并且在許多

48、情況下可能 會比回溯法檢查更少的結(jié)點，但在實際應(yīng)用中，它可能會在回溯法超出允許的 時間限制之前就超出了內(nèi)存的限制。 為了更直觀更有效地分析動態(tài)規(guī)劃法回溯法兩種算法，下面分別對它們的 計算時間進(jìn)行測試。測試中,每個 0-1 背包問題的效益和重量分別為隨機產(chǎn)生 的兩組數(shù)據(jù),其取值范圍為0,999,背包容量定為 1125。為便于各算法間進(jìn)行 比較，測試之前首先把物品按價值重量比的非增順序排序。每次測試將程序運 行 100 次所得時間為運行 100 次的平均值。測試結(jié)果如下表所示18。 平均計算時間問題 規(guī)模動態(tài)規(guī)劃法回溯法 50.0031120.003817 100.0093700.009630 1

49、50.0125500.013120 200.0151500.015780 250.0171800.018900 500.0264600.026710 1000.0418700.039840 2000.0725500.058430 從表中的測試結(jié)果可以看出 當(dāng)問題規(guī)模較小時，三種方法都有較好的穩(wěn) 定性，計算時間都相差不多。隨著問題規(guī)模的增大，各算法的計算時間都在增 大， 其中遞歸法的計算時間增長速度最快，當(dāng)問題規(guī)模為 50，100 和 200 時， 其計算時間太長以致失去利用該法求解的意義，而動態(tài)規(guī)劃法與回溯法則相對 穩(wěn)定且計算時間也相差不多，但是當(dāng)問題規(guī)模大到一定程度，回溯法要優(yōu)于動 態(tài)規(guī)劃法

50、。 通過以上對 0-1 背包問題的求解分析，我們可以看到各種算法設(shè)計方法有 各內(nèi)不同的特點，針對不同的問題領(lǐng)域，它們有不同的效率，對于求解 0-1 背 包問題，各算法的時問復(fù)雜度、優(yōu)缺點以及改進(jìn)方法的比較如下表所示19: 動態(tài)規(guī)劃 o(minnc,） n 2 可求得最優(yōu)決 策序列 速度較慢 建立動態(tài)規(guī)劃 遞歸方程 回溯法 o(n） n 2 能夠獲得最優(yōu) 解 時間復(fù)雜度較 高 判斷右子樹時， 按效率密度 vi/wi 對剩余 對象排序 分枝-限界 法 o(） n 2 速度較快，易 求解 占用的內(nèi)存較 大，效率不高 最大收益或最 小消耗分枝- 限界法，fifo 法 遺傳算法 o(n） n 2 能夠解

51、決傳統(tǒng) 算法不能解決 的問題，能夠 獲得最優(yōu)解 速度較慢，算 法不成熟 基于懲罰函數(shù) 修正方法和譯 碼方法 4 4 總結(jié)與展望總結(jié)與展望 本文就回溯法，分枝-限界法，遺傳算法這 4 種求解 0-1 背包問題的方法進(jìn) 行研究比較，全方位的了解背包問題在實現(xiàn)的方法,以及各方法的優(yōu)勢和劣勢， 通過比較，了解哪種方法是在什么樣的情況下是最實用的方法，然后在以后的 實際運用中針對實際問題，找到最簡單的方法解決 0-1 背包問題。 當(dāng)然目前存在越來越多的算法來研究 0-1 背包問題，比如蟻群算法、微粒 群算法等群體智能算法在 0-1 背包問題求解方面具有的較好收斂速度、健壯性、 穩(wěn)定性、算法簡單等優(yōu)點.最后,針