背包問(wèn)題的算法研究與實(shí)現(xiàn)本科

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

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

3、錄錄內(nèi)容摘要.1關(guān) 鍵 詞.1abstract.2key words.21 緒論.31.1 問(wèn)題的提出及研究意義 .31.2 0-1 背包問(wèn)題的算法研究的分析.31.3 課題的主要研究?jī)?nèi)容 .42 0-1 背包問(wèn)題的實(shí)現(xiàn) .52.1 0-1 背包問(wèn)題在動(dòng)態(tài)規(guī)劃中的實(shí)現(xiàn).52.2 0-1 背包問(wèn)題在回溯法中的實(shí)現(xiàn).82.3 0-1 背包問(wèn)題在分枝-限界法中的實(shí)現(xiàn).122.4 0-1 背包問(wèn)題在遺傳算法中的實(shí)現(xiàn).163 解 0-1 背包問(wèn)題的算法比較與分析.204 總結(jié)與展望 .22參考文獻(xiàn).23致 謝.251內(nèi)容摘要內(nèi)容摘要：背包問(wèn)題是一個(gè)在運(yùn)籌學(xué)領(lǐng)域里常見的典型 np-c 難題，也是算法設(shè)計(jì)分

4、析中的經(jīng)典問(wèn)題，對(duì)該問(wèn)題的求解方法的研究無(wú)論是在理論上,還是在實(shí)踐中都具有重要意義。對(duì)這個(gè)問(wèn)題的求解已經(jīng)研究出了不少的經(jīng)典方法，對(duì)該問(wèn)題的探索和應(yīng)用研究一直在進(jìn)行。在先進(jìn)理論指導(dǎo)下，求解 0-1 背包問(wèn)題具有科學(xué)、高效、經(jīng)濟(jì)、靈活、方便等顯著特點(diǎn)。那么要解決背包問(wèn)題，首要的前提就是設(shè)計(jì)出好的算法，想求得背包問(wèn)題的解，就要先設(shè)計(jì)出算法,本文采用動(dòng)態(tài)規(guī)劃法，回溯法，分枝-限界法，遺傳算法四種方法分別對(duì)背包問(wèn)題、0-1 背包問(wèn)題及簡(jiǎn)單 0-1 背包問(wèn)題進(jìn)行算法設(shè)計(jì)和時(shí)間復(fù)雜度分析，給出具體算法設(shè)計(jì)和實(shí)現(xiàn)過(guò)程。并以具體實(shí)例詳細(xì)描述不同方法求解問(wèn)題解時(shí)算法基本思想，然后就解決 0-1 背包問(wèn)題對(duì)這四種算

5、法進(jìn)行詳細(xì)的比較，總結(jié)四種方法實(shí)現(xiàn)的優(yōu)缺點(diǎn)并得出結(jié)論。如何將背包問(wèn)題應(yīng)用于實(shí)際問(wèn)題中，有針對(duì)性地設(shè)計(jì)適合求解實(shí)際 0-1 背包問(wèn)題的算法，并很好地解決實(shí)際問(wèn)題，是計(jì)算機(jī)工作者不斷思索、研究的一個(gè)領(lǐng)域。關(guān)關(guān) 鍵鍵 詞詞：0-1 背包 動(dòng)態(tài)規(guī)劃 回溯法 分枝-限界法 遺傳算法2abstractabstract： knapsack problem is a typical np-c problem as well as algorithm design and analysis of the classical problems in the common field of operations r

6、esearch. 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 has been ongoing. under the guidance of advanced t

7、heory, 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 solution of knapsack problem, it is necessary to design a

8、lgorithms 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 problem carry out the algorithm design and analysis

9、 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-1 knapsack problem , compare four algorithms in deta

10、il 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 solve the practical problems very well, is an area

11、of computer workers constantly thinking and study. keykey wordswords：0-1 knapsack problem dynamic programmi backtracking branch - bound method genetic algorithm31 1 緒論緒論1.11.1 問(wèn)題的提出及研究意義問(wèn)題的提出及研究意義0-1 背包問(wèn)題是計(jì)算機(jī)科學(xué)中的一個(gè)非常經(jīng)典的優(yōu)化問(wèn)題。也是被證明了的 np 難度問(wèn)題。它是在 1978 年由 merkel 和 hellman 提出的。它的主要思路是假定某人擁有大量物品，重量各不同。此人通

12、過(guò)秘密地選擇一部分物品并將它們放到背包中來(lái)加密消息。背包中的物品中重量是公開的，所有可能選擇的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計(jì)算上是不可實(shí)現(xiàn)的。背包問(wèn)題是熟知的不可計(jì)算問(wèn)題，背包體制以其加密，解密速度快而其人注目。但是，大多數(shù)一次背包體制均被破譯了，因此現(xiàn)在很少有人使用它。圍繞這個(gè)問(wèn)題的求解方法很多，比如貪婪算法、動(dòng)態(tài)規(guī)劃、分枝限界、回溯法、遺傳算法等等。其中回溯法是常見的一種求解方法。多年來(lái)，背包問(wèn)題吸引了許多理論和實(shí)際工作者對(duì)此問(wèn)題作深入的研究，在理論上，盡管背包問(wèn)題的結(jié)構(gòu)簡(jiǎn)單，但它卻具有組合爆炸的性質(zhì)，在實(shí)際應(yīng)用中，許多工業(yè)問(wèn)

13、題都可以用背包問(wèn)題來(lái)描述求解，如資金運(yùn)算、貨艙裝載、存儲(chǔ)分配等都是其典型的應(yīng)用例子。如何將背包問(wèn)題應(yīng)用于實(shí)際問(wèn)題中，并很好地解決實(shí)際問(wèn)題，是計(jì)算機(jī)工作者不斷思索、研究的一個(gè)領(lǐng)域。1.21.2 0-10-1 背包問(wèn)題的算法研究的分析背包問(wèn)題的算法研究的分析 0-1 背包問(wèn)題的算法研究主要是通過(guò)算法設(shè)計(jì)與分析知識(shí)，設(shè)計(jì)解決相關(guān)問(wèn)題的盡可能高效的算法并程序?qū)崿F(xiàn)，而且能夠分析算法的復(fù)雜性，通過(guò)實(shí)驗(yàn)進(jìn)一步領(lǐng)會(huì)各種算法設(shè)計(jì)技術(shù)的基本原理，掌握算法設(shè)計(jì)和分析方法，提高算法設(shè)計(jì)與分析的應(yīng)用能力。0-1 背包是一類很典型的優(yōu)化問(wèn)題,研究它有很重要的實(shí)際意義，這不僅是由于它結(jié)構(gòu)簡(jiǎn)潔，可以作為子問(wèn)題為研究更復(fù)雜的問(wèn)

14、題奠定理論基礎(chǔ)，有很高的理論研究?jī)r(jià)值，而且由于它是許多實(shí)際工程應(yīng)用問(wèn)題的種通用化描述，在很多實(shí)際問(wèn)題當(dāng)中有著非常廣泛的應(yīng)用背景，例如項(xiàng)目決策等。他是最基本的背包問(wèn)題，即對(duì)一個(gè)物體要么選用，要么就拋棄，不能將一個(gè)物體再繼續(xù)細(xì)分的4情況。它包含了背包問(wèn)題中設(shè)計(jì)狀態(tài)、方程的最基本思想，在經(jīng)濟(jì)管理、資源分配、投資決策、裝載設(shè)計(jì)等領(lǐng)域有著重要的應(yīng)用價(jià)值。在計(jì)算理論中屬于np-c 完全問(wèn)題，其計(jì)算復(fù)雜度，傳統(tǒng)上采用動(dòng)態(tài)規(guī)劃來(lái)求解。背包問(wèn)題就是在資源有限的條件下，追求總的最大收益的資源有效分配問(wèn)題。1.31.3 課題的主要研究?jī)?nèi)容課題的主要研究?jī)?nèi)容.1 背包問(wèn)題的描述背包問(wèn)題的描述背包問(wèn)題是

15、整數(shù)規(guī)劃中的一類特殊問(wèn)題，在現(xiàn)實(shí)生活中具有廣泛應(yīng)用。如果能提出求解此問(wèn)題的有效算法，則具有很好的經(jīng)濟(jì)價(jià)值和決策價(jià)值。問(wèn)題的一般描述是：旅行者背包登山，背包的最大承重為 m，現(xiàn)有 n 個(gè)物品可供選擇裝入背包，第 i 個(gè)物品鶯量為 wi，價(jià)值為 pi，假定物品 i 的一部分xi(0 xi1)放人背包，獲得價(jià)值為 xipi，由于背包最大承重為 m，要求裝入物品總質(zhì)量不過(guò)超過(guò) m，問(wèn)旅行者應(yīng)該如何選擇物品裝入背包，使得裝入物品的價(jià)值總和達(dá)到最大值。背包問(wèn)題的數(shù)學(xué)描述如下：要求找到一個(gè) n 元向量(x1，x2xn)，在滿足約束條件：情況下，使得目標(biāo)函數(shù)，其中，10iiixmwxpxiimax1in；m0

16、；wi0；pi0。滿足約束條件的任何向量都是一個(gè)可行解，而使 得目標(biāo)函數(shù)達(dá)到最大的那個(gè)可行解則為最優(yōu)解1。 .2 0-10-1 背包問(wèn)題背包問(wèn)題 0-1 背包問(wèn)題的提出給定 n 種物品和 1 個(gè)背包。物品 i 的重量是 wi，其價(jià)值為 pi，背包的容量為 m。問(wèn)應(yīng)如何裝入背包中的物品，使得裝人背包中物品的總價(jià)值最大？在選擇裝人背包的物品時(shí)，對(duì)每種物品 i 只有兩種選擇，即裝入背包、不裝入背包。不能將物品 i 裝人背包多次，也不能只裝入部分的物品 i。該問(wèn)題稱為 0-1 背包問(wèn)題。 問(wèn)題符號(hào)化 0-1 背包問(wèn)題的符號(hào)化表示是，給定 m0， w i 0， pi 0，1in ， 要求

17、找到一個(gè) n 元 0-1 向量向量(x1，x2xn)， x i =0 或 1 , 1in, 使得 5 ，而且達(dá)到最大2。mwxiipxii2 2 0-10-1 背包問(wèn)題的實(shí)現(xiàn)背包問(wèn)題的實(shí)現(xiàn)2.12.1 0-10-1 背包問(wèn)題在動(dòng)態(tài)規(guī)劃中的實(shí)現(xiàn)背包問(wèn)題在動(dòng)態(tài)規(guī)劃中的實(shí)現(xiàn).1 動(dòng)態(tài)規(guī)劃的基本原理與分析動(dòng)態(tài)規(guī)劃的基本原理與分析動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。不同子問(wèn)題的數(shù)目常常只有多項(xiàng)式量級(jí)。如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量

18、重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。它把已知問(wèn)題分為很多子問(wèn)題，按順序求解子問(wèn)題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最佳的結(jié)果舍棄其余。前一子問(wèn)題為后面子問(wèn)題提供信息，而減少計(jì)算量，最后一個(gè)子問(wèn)題的解即為問(wèn)題解。采用此方法求解 0-1 背包問(wèn)題的主要步驟如下：分析最優(yōu)解的結(jié)構(gòu)：最有子結(jié)構(gòu)性質(zhì)；建立遞歸方程；計(jì)算最優(yōu)值；構(gòu)造最優(yōu)解4。動(dòng)態(tài)規(guī)劃算法的每一步?jīng)Q策都是根據(jù)前一步的狀態(tài)參量來(lái)決定這一步狀態(tài)參量的設(shè)置，也就是說(shuō)，從初始狀態(tài)到最終狀態(tài)要經(jīng)過(guò)多個(gè)過(guò)程，經(jīng)歷不同的狀態(tài)，不斷地根據(jù)上一步狀態(tài)決定下一狀態(tài)，從而形成了一個(gè)決策序列，最終將整個(gè)問(wèn)題解決，這就是典型的多段決

19、策的特性。由上面的動(dòng)態(tài)規(guī)劃法的介紹，可以看出 0-1 背包問(wèn)題，是符合多段決策的特點(diǎn)和具有重疊子問(wèn)題。因此，在設(shè)計(jì) 0-1 背包問(wèn)題解決方案時(shí)，可以將整個(gè)物品放到背包的過(guò)程，看成一個(gè)取物品的過(guò)程。 .2 0-10-1 背包問(wèn)題的實(shí)現(xiàn)背包問(wèn)題的實(shí)現(xiàn) 最優(yōu)子結(jié)構(gòu)性質(zhì)0-1 背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。設(shè)(y1，y2yn)是所給 0-1 背包問(wèn)題的一個(gè)最優(yōu)解，則(y2，y3yn)是下面相應(yīng)子問(wèn)題的一個(gè)最優(yōu)解：6nikkkxvmaxnkixjxwknikkk,1 , 0因若不然，設(shè)(z2，z3zn)是上述問(wèn)題的一個(gè)最優(yōu)解，而(y2，y3yn)不是它的最優(yōu)解，由此可見,且c。因此ni 2

20、niiiyv2niiizw2w1y1 niiizv2 v1y1niiiyv1cniiizw2w1y1這說(shuō)明(y1，z2zn)是所給 0-1 背包問(wèn)題的一個(gè)更優(yōu)解，從而(y1，y2yn)不是所給 0-1 背包問(wèn)題的最優(yōu)解。此為矛盾1。 遞歸關(guān)系設(shè)所給 0-1 背包問(wèn)題的子問(wèn)題nikkkxvmaxnkixjxwknikkk,1 , 0 的最優(yōu)值為 m(i,j)，即 m(i,j)是背包容量為 j，可選擇物品為i，i+1，n 時(shí) 0-1 背包問(wèn)題的最優(yōu)值。由 0-1 背包問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i,j)的遞歸式如下：wjjjimwijviwijimjim0), 1(,), 1(),),

21、1(maxj)m(i,wnjwnvnj0j)m(n,7 算法描述基于以上討論，當(dāng) wi(1 i n)為正整數(shù)時(shí)，用二維數(shù)組 m來(lái)存儲(chǔ) m(i,j)的相應(yīng)值，可設(shè)計(jì)解 0-1 背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法 knapsack 入下：templatevoid 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(int

22、j=wi;j=w1) m1c=max(m1c,m2c-w1+v1);templatevoid traceback(type* * m,int w,int c,int n,int x) for (int i=1;i=n;i+) if(mic=mi+1c) xi=0;8 else xi =1;c-= wi; xn=(mnc)?1:0;1 計(jì)算復(fù)雜性分析利用動(dòng)態(tài)規(guī)劃求解 0-1 背包問(wèn)題的復(fù)雜度為 0(minnc,2n。動(dòng)態(tài)規(guī)劃主要是求解最優(yōu)決策序列，當(dāng)最優(yōu)決策序列中包含最優(yōu)決策子序列時(shí)，可建立動(dòng)態(tài)規(guī)劃遞歸方程，它可以幫助高效地解決問(wèn)題8。2.22.2 0-10-1 背包問(wèn)題在回溯法中的實(shí)現(xiàn)背包問(wèn)題

23、在回溯法中的實(shí)現(xiàn).1 回溯法的基本原理與分析回溯法的基本原理與分析回溯是一種系統(tǒng)地搜索問(wèn)題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問(wèn)題定義一個(gè)解空間，這個(gè)解空間必須至少包含問(wèn)題的一個(gè)解(可能是最優(yōu)的)?；厮莘ㄐ枰獮閱?wèn)題定義一個(gè)解空間，這個(gè)解空間必須至少包含問(wèn)題的一個(gè)解(可能是最優(yōu)的)。使用遞歸回溯法解決背包問(wèn)題的優(yōu)點(diǎn)在于它算法思想簡(jiǎn)單，而且它能完全遍歷搜索空間，肯定能找到問(wèn)題的最優(yōu)解奉但是由于此問(wèn)題解的總組合數(shù)有個(gè)，因此隨著物件數(shù) n 的增大，其解的空間將以 n級(jí)增長(zhǎng)，當(dāng) n 大到一定n2n2程度上，用此算法解決背包問(wèn)題將是不現(xiàn)實(shí)的。下一步是組織解空間以便它能被容易地搜索。典型的組

24、織方法是圖或樹。一旦定義了解空間的組織方法，這個(gè)空間即可按照深度優(yōu)先的方法從開始結(jié)點(diǎn)進(jìn)行搜索，利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。.2 0-10-1 背包問(wèn)題的實(shí)現(xiàn)背包問(wèn)題的實(shí)現(xiàn) 回溯法的算法描述回溯法是一種系統(tǒng)地搜索問(wèn)題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問(wèn)題定義一個(gè)解空間，這個(gè)解空間必須至少包含問(wèn)題的一個(gè)解(可能是最優(yōu)的)。一旦定義了解空間的組織方要選擇一個(gè)對(duì)象的子集，將它們裝人背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹的形狀。首先形成一個(gè)遞歸算法，去找到可獲得的最大收益。然后，對(duì)該算法加以改進(jìn)，形成代碼。改進(jìn)后的代碼可找到獲得最大收益時(shí)包含在背包中的對(duì)象的集

25、合。9左子樹表示一個(gè)可行的結(jié)點(diǎn)，無(wú)論何時(shí)都要移動(dòng)到它，當(dāng)右子樹可能含有比當(dāng)前最優(yōu)解還優(yōu)的解時(shí)，移動(dòng)到它。一種決定是否要移動(dòng)到右子樹的簡(jiǎn)單方法是 r 為還未遍歷的對(duì)象的收益之和，將 r 加到 cp (當(dāng)前節(jié)點(diǎn)所獲收益)之上，若( r+cp) bestp(目前最優(yōu)解的收益)，則不需搜索右子樹。一種更有效的方法是按收益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量， 當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)， 就使用它的一部分。 解 0-1 背包問(wèn)題的回溯算法描述如下：templateclass knap friend typep knapsack(typep*,typew

26、*,typew,int); private：typep bound(int i);void backtrack(int i);typew c; /背包容量 int n; /物品數(shù)typew*w; /物品重量數(shù)組typep*p; /物品價(jià)值數(shù)組typew cw; /當(dāng)前重量typep cp; /當(dāng)前價(jià)值typep bestp; /當(dāng)前最優(yōu)價(jià)值 ;templatevoid knap:backtrack(int i) if(in)/到達(dá)葉結(jié)點(diǎn)bestp=cp;return;if(cw+wibestp) /進(jìn)入右子數(shù)backtrack(i+1);templatetypep knap:bound(int

27、 i)/計(jì)算上界 typew cleft=c-cw; /剩余容量 typep b=cp; /以物品單位重量?jī)r(jià)值遞減序裝入物品 while (i=n&wi=cleft) cleft-=wi; 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; ;templatetypep knapsack(typep p, typep w,typew c,in

28、t n)11 /為 knap:backtrack 初始化 typew w=0; typep p=0; object*q=new 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;/裝入所有物品 /依物品單位重量?jī)r(jià)值排序 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;

29、 k.n=n; k.bestp=0; /回搠搜索 k.backtrack(1); deleteq; deletek.w; deletek.p; reture k,bestp;121 算法效率 由于計(jì)算上界函數(shù)需要 o(n)時(shí)間，在最壞情況下有 o()個(gè)右孩子結(jié)點(diǎn)需n2要上界函數(shù)，故計(jì)算 0-1 背包問(wèn)題的回溯算法所需的計(jì)算時(shí)間復(fù)雜度為 o(n)。n2對(duì)回溯法的改進(jìn)主要是對(duì)判斷是否移動(dòng)右子樹上，一種更有效的方法是按效益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量，當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)，就使用它的一部分?；厮菟惴ǖ倪\(yùn)行時(shí)間取決于它在搜索過(guò)程中所生成的

30、結(jié)點(diǎn)數(shù),而限界函數(shù)可以大量減少所生成的結(jié)點(diǎn)個(gè)數(shù),省去許多無(wú)謂的搜索, 使得搜索速度更快 ,其調(diào)用限界函數(shù)計(jì)算上界需花費(fèi) o(n)時(shí)間 ,最壞情況下有 o()個(gè)結(jié)點(diǎn)需調(diào)用n2限界函數(shù) ,需花費(fèi) o(n)時(shí)間,所以該算法的時(shí)間復(fù)雜度為 o(n)12。n2 回溯法的另一個(gè)重要特性就是在搜索執(zhí)行的同時(shí)產(chǎn)生解空間 在搜索期間的任何時(shí)刻 僅保留從開始結(jié)點(diǎn)到當(dāng)前可擴(kuò)展結(jié)點(diǎn)的路徑其空間需求為 o(從開始結(jié)點(diǎn)起最長(zhǎng)路徑的長(zhǎng)度),所以 ,此處該算法的空間復(fù)雜度為 o(n),回溯法是算法設(shè)計(jì)的基本方法之一 ,它適用于解一些涉及到尋找一組解的問(wèn)題或者求滿足某些約束條件的最優(yōu)解的問(wèn)題,且適用于求解組合數(shù)量較大的問(wèn)題。2

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

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

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

34、指明可能找到一個(gè)最優(yōu)解時(shí)才將右孩子加入子集樹和隊(duì)列中。則主要算法描述為：class object friend int knapsack(int *,int *,int,int,int *); public: int operator=a.d); private: int id; float d;/單位重量?jī)r(jià)值 ; template class knap;class bbnode14 friend knap; friend int knapsack(int *,int *,int,int,int *); private: bbnode *parent; /指向父結(jié)點(diǎn)的指針 bool lchil

35、d; /左兒子結(jié)點(diǎn)標(biāo)志 ;template class heapnode friend knap; public: operator typep () const return uprofit; private: typep uprofit, /結(jié)點(diǎn)的價(jià)值上界 profit; /結(jié)點(diǎn)所相應(yīng)的價(jià)值 typew weight; /結(jié)點(diǎn)所相應(yīng)的重量 int level; /活結(jié)點(diǎn)在子集樹中所處的層序號(hào) bbnode *ptr; /指向活結(jié)點(diǎn)在子集樹中相應(yīng)結(jié)點(diǎn)的指針 ；templateclass knap friend typep knapsack(typep *,typew *,typew,int,

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

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

38、addlivenode(up,cp+pi,cw+wi,ture,i+1); up =bound(i+1); /檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)16 if(up=bestp)/右子樹可能含最優(yōu)解 addlivenode(up,cp,cw,false,i+1); /取下一擴(kuò)展結(jié)點(diǎn) 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; 12.42.4

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

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

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

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

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

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

45、本思想是把原問(wèn)題分解為一系列子問(wèn)題，然后從這些子問(wèn)題中求出原問(wèn)題的解。回溯其實(shí)就是窮舉，窮舉所有的解，找出解中最優(yōu)的值?；厮莘ㄔ诎瑔?wèn)題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹?；厮莘ǖ幕舅悸肥牵捍_定解空間，建立解空間樹，用深度優(yōu)先搜索算法遞歸搜索解空間樹，并同時(shí)注意剪枝,常用的分枝一限界法有最小耗費(fèi)法，最大收益法。fifo(先進(jìn)先出)法等。0-1 背包問(wèn)題的分枝一限界算法可以使用最大收益算法。該算法跟回溯法類似。但分枝限界法需要 o()n2的解空間。故該算法不常用在背包問(wèn)題求解。遺傳算法是計(jì)算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是一種進(jìn)化算法。對(duì)于一個(gè)最優(yōu)化問(wèn)題，一定

46、數(shù)量的候選解（稱為個(gè)體）的抽象表示（稱為染色體）的種群向更好的解進(jìn)化。通常解用二進(jìn)制 0 和 1 表示，進(jìn)化從一個(gè)個(gè)體發(fā)生，然后一代一代發(fā)生。在每一代中，該種群的價(jià)值被評(píng)估，從當(dāng)前種群中隨機(jī)地選擇多個(gè)個(gè)體（基于它們的適應(yīng)度） ，通過(guò)自然選擇?；厮莘ū确种ο藿缭谡加脙?nèi)存方面具有優(yōu)勢(shì)?；厮莘ㄕ加玫膬?nèi)存是 0(解空間的最大路徑長(zhǎng)度)，而分枝限界所占用的內(nèi)存為 0(解空間大小)。對(duì)于一個(gè)子21集空間，回溯法需要 0(n)的內(nèi)存空間，而分枝限界則需要 0(2n)的空間。雖然最大收益或最小耗費(fèi)分枝限界在直覺上要好于回溯法，并且在許多情況下可能會(huì)比回溯法檢查更少的結(jié)點(diǎn)，但在實(shí)際應(yīng)用中，它可能會(huì)在回溯法超出允

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

48、8900500.0264600.0267101000.0418700.0398402000.0725500.058430從表中的測(cè)試結(jié)果可以看出 當(dāng)問(wèn)題規(guī)模較小時(shí)，三種方法都有較好的穩(wěn)定性，計(jì)算時(shí)間都相差不多。隨著問(wèn)題規(guī)模的增大，各算法的計(jì)算時(shí)間都在增大， 其中遞歸法的計(jì)算時(shí)間增長(zhǎng)速度最快，當(dāng)問(wèn)題規(guī)模為 50，100 和 200 時(shí)，其計(jì)算時(shí)間太長(zhǎng)以致失去利用該法求解的意義，而動(dòng)態(tài)規(guī)劃法與回溯法則相對(duì)穩(wěn)定且計(jì)算時(shí)間也相差不多，但是當(dāng)問(wèn)題規(guī)模大到一定程度，回溯法要優(yōu)于動(dòng)態(tài)規(guī)劃法。通過(guò)以上對(duì) 0-1 背包問(wèn)題的求解分析，我們可以看到各種算法設(shè)計(jì)方法有各內(nèi)不同的特點(diǎn)，針對(duì)不同的問(wèn)題領(lǐng)域，它們有不同的

49、效率，對(duì)于求解 0-1 背包問(wèn)題，各算法的時(shí)問(wèn)復(fù)雜度、優(yōu)缺點(diǎn)以及改進(jìn)方法的比較如下表所示19:動(dòng)態(tài)規(guī)劃o(minnc,）n2可求得最優(yōu)決策序列速度較慢建立動(dòng)態(tài)規(guī)劃遞歸方程回溯法o(n）n2能夠獲得最優(yōu)解時(shí)間復(fù)雜度較高判斷右子樹時(shí)，按效率密度vi/wi 對(duì)剩余對(duì)象排序22分枝-限界法o(）n2速度較快，易求解占用的內(nèi)存較大，效率不高最大收益或最小消耗分枝-限界法，fifo法遺傳算法o(n）n2能夠解決傳統(tǒng)算法不能解決的問(wèn)題，能夠獲得最優(yōu)解速度較慢，算法不成熟基于懲罰函數(shù)修正方法和譯碼方法4 4 總結(jié)與展望總結(jié)與展望 本文就回溯法，分枝-限界法，遺傳算法這 4 種求解 0-1 背包問(wèn)題的方法進(jìn)行研究比較，全方位的了解背包問(wèn)題在實(shí)現(xiàn)的方法,以及各方法的優(yōu)勢(shì)和劣勢(shì)，通過(guò)比較，了解哪種方法是在什么樣的情況下是最實(shí)用的方法，然后在以后的實(shí)際運(yùn)用中針對(duì)實(shí)際問(wèn)題，找到最簡(jiǎn)單的方法解決 0-1 背包問(wèn)題。 當(dāng)然目前存在越來(lái)越多的算法來(lái)研究 0-1 背包問(wèn)題，比如蟻群算法、微粒群算法等群體智能算法在 0-1 背包問(wèn)題求解方面具有的較好收斂速度、健壯性、穩(wěn)定性、算法簡(jiǎn)單等優(yōu)點(diǎn).最后,針對(duì)群體