本科 畢業(yè)論文 背包問題

1、 中圖分類號：O224本 科 生 畢 業(yè) 論 文（或設(shè)計）（申請學(xué)士學(xué)位）論文題目 背包問題的算法思想綜述 作者姓名 程兵 所學(xué)專業(yè)名稱 信息與計算科學(xué) 指導(dǎo)教師 翟明清 2011年4月30日學(xué) 號： 2007211420論文答辯日期：2011年 月 日指 導(dǎo) 教 師： （簽字）滁州學(xué)院本科畢業(yè)設(shè)計（論文）原創(chuàng)性聲明本人鄭重聲明：所呈交的設(shè)計（論文）是本人在導(dǎo)師的指導(dǎo)下獨立進行研究所取得的研究成果.除了文中特別加以標注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果.本人完全意識到本聲明的法律后果由本人承擔(dān). 作者簽名： 2011年 5月 30日目 錄摘要1Abstract 1

2、前言2背包問題的算法思想綜述摘要：背包問題是一種組合優(yōu)化的NP完全問題。問題的名稱來源于如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，計算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。傳統(tǒng)求解該問題的方法可以概括為精確算法和近似算法， 近年來利用近似算法求解背包問題成為重點。本文總結(jié)了背包問題的定義和性質(zhì)，給出了背包問題不同的算法以及各算法的思想綜述。關(guān)鍵詞: 動態(tài)規(guī)劃算法；貪婪算法；遺傳算法；螞蟻算法；回溯法。Knapsack problem algorithm thought summaryAbstract:The Knapsack problem is the NP c

3、omplete question which one kind of combination optimizes. How does the question name originate from chooses the most appropriate goods to lay aside in assigning in the knapsack. The similar question appears frequently in the trade, the combinatorics, domains and so on computation complex theory, cry

4、ptology and applied mathematics. The tradition solves this question the method to be possible to summarize for the precise algorithm and the approximate method, in recent years used the approximate method solution knapsack question to become key. This article summarized the knapsack question definit

5、ion and the nature, has given the knapsack question different algorithm as well as various algorithms thought summary. Keywords: Dynamic programming algorithm; Greedy algorithm; Genetic algorithm; Ant algorithm; Backtracking. 前言 背包問題是在1978年由Merkel和Hellman提出的。它的主要思路是假定某人擁有大量物品，重量各不同。此人通過秘密地選擇一部分物品并將它

6、們放到背包中來加密消息。背包中的物品中重量是公開的，所有可能的物品也是公開的，但背包中的物品是保密的。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實現(xiàn)的。背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而其人注目。在解決大量的復(fù)雜組合優(yōu)化問題時，它常常作為一個子問題出現(xiàn)，從實際的觀點看，許多問題可以用背包問題來描述，如裝箱問題，貨倉裝載，預(yù)算控制，存儲分配，項目選擇決策等，都是典型的應(yīng)用例子。隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，背包公鑰密碼在電子商務(wù)中的公鑰設(shè)計中也起著重要的作用。然而當(dāng)問題的規(guī)模較大時，得到最優(yōu)解是極其困難的。算法是一系列解決問題的清晰指令, 一個算法的優(yōu)劣

7、可以用空間復(fù)雜度與時間復(fù)雜度來衡量。算法可以理解為有基本運算及規(guī)定的運算順序所構(gòu)成的完整的解題步驟，或者看成按照要求設(shè)計好的有限的確切的計算序列，并且這樣的步驟和序列可以解決一類問題。傳統(tǒng)求解該問題的方法可以概括為精確算法和近似算法，其中精確算法有動態(tài)規(guī)劃法、回溯法、分支限界法等，近似算法有遺傳算法、貪婪法、 粒子群算法、蟻群算法等,由于精確算法的時間復(fù)雜性和空間復(fù)雜性等缺點， 近年來利用近似算法求解背包問題成為重點。本文主要研究背包問題的總體概況，整理了背包問題的定義、性質(zhì)、算法技巧等，對各個算法思想進行概括總結(jié)，并對各種算法的復(fù)雜度進行分析。1背包問題的概念及算法分析1.1背包問題的定義我

8、們有n種物品，物品j的重量為wj，價格為pj。我們假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W。如果限定每種物品只能選擇0個或1個，則問題稱為0-1背包問題。可以用公式表示為：maximize subject to 如果限定物品j最多只能選擇bj個，則問題稱為有界背包問題?？梢杂霉奖硎緸椋簃aximize subject to 如果不限定每種物品的數(shù)量，則問題稱為無界背包問題。1.2背包問題算法分析根據(jù)背包問題定義，可以將其轉(zhuǎn)化為如下的約束條件和目標函數(shù)：于是，問題就歸結(jié)為尋找一個滿足約束條件（1），并使目標函數(shù)式（2）達到最大的解向量。首先說明一下0-1背包問題擁有最優(yōu)解

9、。假設(shè)是所給的問題的一個最優(yōu)解，則是下面問題的一個最優(yōu)解：。如果不是的話，設(shè)是這個問題的一個最優(yōu)解，則，且。因此，這說明是所給的0-1背包問題比更優(yōu)的解，從而與假設(shè)矛盾。背包問題是算法設(shè)計分析中的經(jīng)典問題。目前, 隨著計算機算法的不斷發(fā)展, 涌現(xiàn)出大量可用于解決背包問題的算法和思想, 背包問題的建模與求解有著廣泛的應(yīng)用前景。其求解方法主要有三類：第一類是精確方法, 如動態(tài)規(guī)劃、回溯法和分枝一限界法等 第二類是近似方法,啟發(fā)式算法, 如貪心算法。第三類是全局優(yōu)化方法, 如遺傳算法、蟻群算法、遺傳退火進化算法等。下面將對這三類求解方法進行分析和比較。2精確算法2.1動態(tài)規(guī)劃法動態(tài)規(guī)劃的基本思想:將

10、一個比較大的問題逐層分解成相對比較小的問題,這些較小的問題一般都可以解決,在這一點與上面提到的貪心算法和分治法很類似,但是動態(tài)規(guī)劃算法有著自身的特點,解決了分治法中相同子問題重復(fù)求解的問題。貪心算法要求找出問題的最佳量度標準,而在現(xiàn)實問題中往往很難找到最佳量度標準,對我們的動態(tài)規(guī)劃法來說,利用了最優(yōu)子結(jié)構(gòu), 由下向上的方法從子問題的最優(yōu)解一步一步地構(gòu)造出整個問題的最優(yōu)解。有時動態(tài)規(guī)劃法可以解決貪心算法不能解決的問題。動態(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),從而

11、形成了一個決策序列, 最終將整個問題解決,這就是典型的多段決策的特性。由上面的動態(tài)規(guī)劃法的介紹,可以看出0 /1背包問題,是符合多段決策的特點和具有重疊子問題。因此,在設(shè)計0 /1背包問題解決方案時, 可以將整個物品放到背包的過程,看成一個取物品的過程。可以當(dāng)背包容量為x時,第i個物品導(dǎo)致的最優(yōu)解為fi ( x) ,顯然, fi (M )為整個問題的最優(yōu)解,M為背包的最大容量, 根據(jù)動態(tài)規(guī)劃的算法思想, 可以得到如下遞歸方程:fi ( x) =max fi - 1 ( x) , fi - 1 ( x - wi ) + pi 其中i代表第i次決策, 0 fi - 1 ( x- wi ) +wi

12、,則fi = fi - 1 ( x)表示物品i不裝入背包的效益比裝入還要大, 反之fi = fi - 1 ( x - wi ) + pi , 可見,第i個物品是否裝入背包就取決于fi - 1 ( x)和fi - 1 ( x - wi ) + pi 的大小的過程。下面對動態(tài)規(guī)劃的算法進行一下相應(yīng)的算法分析,首先是時間復(fù)雜度, 從上面算法的執(zhí)行過程中可以看出假設(shè)有Q ( n)個子問題,每一個子問題最多需要m 次決策, 則計算的頻率為nm, 回溯的頻率為n,那么整個過程的算法的時間復(fù)雜度為T( n) = nm + n, 即為Q ( nm ) 。然后, 我們在看一下另一個考察指標空間復(fù)雜度,根據(jù)上面的

13、得到的計算頻率和回溯頻率,根據(jù)空間復(fù)雜度計算的原則可知為Q ( n) 。從上面的分析可以看出動態(tài)規(guī)劃法的時間復(fù)雜度和空間復(fù)雜度均成直線增長。在整個計算過程中,選擇一種行之有效的決策方法是至關(guān)重要的,能夠分解成比較容易解決的子問題, 是決策設(shè)計的最佳標準。2.2回溯法回溯其實就是窮舉，窮舉所有的解，找出解中最優(yōu)的值。回溯法在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹?；厮菟惴ㄋ阉髦两饪臻g樹的任一結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索。

14、回溯法在用來求問題的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。回溯法在求解空間樹時，只要其左兒子節(jié)點時一個可行結(jié)點時就進行該左子樹，只有右子樹包含可行解時才進入右子樹，否則就剪去右子樹。 回溯法的基本思路是：確定解空間，建立解空間樹，用深度優(yōu)先搜索算法遞歸搜索解空間樹，并同時注意剪枝。 背包問題的算法思路：按照物品的單位價值從大到小排序，計算當(dāng)前節(jié)點的上界，搜索左子樹，如果右子樹包含可行解，就搜索右子樹。剪去右子樹條件：當(dāng)前價值加上剩余物品的總價值小于當(dāng)前的最優(yōu)總價值時，不需搜索右子樹，可將右子樹剪去。用回溯法求解背包問題的偽代碼：void Backtrack(int i)如

15、果已經(jīng)搜索完一條從根節(jié)點到葉節(jié)點的路徑，更新當(dāng)前解的最優(yōu)值bestp；如果左節(jié)點的重量小于剩余的背包重量，進入左子樹進行搜索；如果右子樹包含當(dāng)前解，進入右子樹進行搜索。否則剪去右子樹?；厮莘▽嶋H時窮舉算法，用一定的剪枝進行優(yōu)化，算法的時間復(fù)雜度為O(n*2n)，n為物品個數(shù)。3啟發(fā)式算法31貪心算法貪婪算法是一種逐步構(gòu)造最優(yōu)解的啟發(fā)式算法， 其基本思想是在每一階段它都在一定的規(guī)則下構(gòu)造出當(dāng)前看似最優(yōu)的一個決策，決策一旦做出就不再更改。貪婪算法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮整體情況，所以貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大量時間。雖然這種啟發(fā)

16、式的策略并不一定能夠獲得最優(yōu)解,然而在許多情況下確能達到預(yù)期的目的。貪婪算法解決優(yōu)化問題的最關(guān)鍵問題是制定貪婪策略。對于背包問題來說，貪婪的策略有常用的3種。它們是價值貪婪準則、質(zhì)量貪婪準則和價值密度貪婪準則。每種貪婪策略都采用多步過程來完成背包的裝入。在每一步過程中利用貪婪準則選擇一個物品裝入背包。其中采用價值密度(價值重量比 pi/ci)的貪婪準則是從剩余物品中選擇可以放入背包的 pi/ci值最大的物品，直到超出背包容量限制裝不下為止，并將未裝入背包的物品編碼修正為 0。算法的時間復(fù)雜度為 o(nlogn)。這種策略對于連續(xù)背包問題可保證得到最優(yōu)解，但對于 01背包問題不一定能得到最優(yōu)解。

17、因此出現(xiàn)了一些對于貪婪算法的改進方法，例如文獻中提出的算法在不增加時間復(fù)雜度的基礎(chǔ)上， 保證求解質(zhì)量較穩(wěn)定地優(yōu)于價值密度貪婪算法及價值密度改進算法。近年來還產(chǎn)生了貪婪法與其他算法結(jié)合的混合算法，有趙新超，楊婷婷提出的更貪心粒子群算法 , 該算法對超過背包重量限制的粒子的處理方法是去掉已經(jīng)裝進去且性價比最差的物品，直到滿足重量約束條件為止，這樣在改善粒子質(zhì)量的同時避免了罰函數(shù)方法中敏感的參數(shù)選擇問題； 對于可行粒子的處理措施是將還未裝入背包且性價比最好的物品裝進背包，直到不能裝為止。結(jié)果表明更貪心粒子群算法無論在尋優(yōu)能力、計算速度和穩(wěn)定性方面都有很好的表現(xiàn)，非常適合于求解大規(guī)模背包問題。還有劉茜

18、、馬杰良提出的混合遺傳算法，它針對遺傳操作交叉和變異的過程中不符合約束條件的個體，在解碼過程中引入貪婪算法優(yōu)先裝入價值重量比大且物品標記為1 的物品， 直至背包容量限制裝不下為止，通過引進貪婪算法使得遺傳進化過程以良好的種子為基礎(chǔ)進行，此外算法在變異操作和進化終止條件的設(shè)計上也進行了改進， 結(jié)果表明該算法在解的質(zhì)量和求解速度方面都比遺傳算法有很大的改良。貪婪算法通過一系列的選擇得到問題的解，在每一次總是做出在當(dāng)前狀態(tài)下看來是最好的選擇，也就是希望通過局部的最優(yōu)來達到一個全局的最優(yōu)。這種啟發(fā)式的策略并不總能獲得最優(yōu)解，然而在許多情況下確能達到預(yù)期的目的，而且對于很多NP 問題來說，本身就不存在最

19、優(yōu)解。對于01 背包問題來說，貪婪的策略有常用的3 種。每種貪婪策略都采用多步過程來完成背包的裝入。在每一步過程中利用貪婪準則選擇一個物品裝入背包。第一種貪婪準則：從剩余的物品中，選出可以裝入背包的價值最大的物品，利用這種規(guī)則，價值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個價值最大的物品，如此繼續(xù)下去。第二種貪婪準則：從剩下的物品中選擇可裝入背包的重量最小的物品，如此繼續(xù)下去直到不能滿足條件為止。第三種貪婪準則：價值密度（價值重量比pi wi）貪婪算法，這種選擇準則為： 從剩余物品中選擇可裝入包的pi wi值最大的物品，這也是本文所選擇的貪婪策略，因為它是一個直覺上近似的解。用貪婪算

20、法求解01 背包問題的過程如下：對于給定的物品，分別求出價值密度（價值重量比），ripi wi，i1，2，n；忽略先前的物品排序， 按照價值密度， 進行非升序排列：（p（1）/w（1）（p（2）/w（2）（p（n）/w（n）；重復(fù)以下步驟，直到不滿足條件為止：對于當(dāng)前的物品，如果重量小于包中剩余的容量，則放入，并置物品標志為1（表明被選中），否則就停止。算法主要耗時是在于將各種物品按價值密度大小排序，本文利用MATLAB 軟件中的SORTROWS 函數(shù)進行排序，此函數(shù)是基于快速排序（quicksort）實現(xiàn)的，因此，算法的時間復(fù)雜度為O（nlogn）。4全局優(yōu)化方法4.1遺傳算法遺傳算法是計算

21、數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是一種進化算法。對于一個最優(yōu)化問題，一定數(shù)量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。通常解用二進制0和1表示，進化從一個個體發(fā)生，然后一代一代發(fā)生。在每一代中，該種群的價值被評估，從當(dāng)前種群中隨機地選擇多個個體（基于它們的適應(yīng)度），通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。遺傳算法的一般步驟：確定二進制編碼取值范圍，初始化染色體的個數(shù)，并隨機產(chǎn)生所有的染色體，構(gòu)造評價函數(shù)和個體的適應(yīng)度總和，經(jīng)過交叉運算和變異操作，進行遺傳迭代求解。01背包問題的遺傳算法求解策略：(1)二進制法策略：將物品根據(jù)單位重量價

22、值從大到小排序。用0和1分別表示物品i放入背包和物品i不放入背包，如果Xi表示物品i是否放入背包，則放入背包的總重量為w=w1*x1+w2*x2+wn*xn;放入背包的物品的總價值為P=p1*x1+p2*x2+pn*xn。Fm存放目標函數(shù)值就是個體的適應(yīng)度。Tn存放每個個體的約束條件值1） 初始種群產(chǎn)生，并計算每個適應(yīng)度值和其對應(yīng)的約束條件值(即為染色體中選取的物品的重量)，比較初始種群中各個個體的適應(yīng)度。選擇最大者所對就的個體作為第一代最優(yōu)個體并記錄該個體以及它的適應(yīng)度和約束條件值。2） 計算每個個體的選擇概率PiFi/E(Fi)3） 根據(jù)輪盤睹法進行個體選擇；4） 進行交叉運算，隨即選擇一

23、對個體產(chǎn)生一對有效交叉位置進行交叉運算，并計算新產(chǎn)生的個體的適應(yīng)度值和約束條件值,如果新產(chǎn)生的個體重量大于背包容量，則對新產(chǎn)生的這個個體進行修正，放棄在一個個體中的一個物品，增加另一個個體的一個物品使其重量小于背包重量。5） 進行變異操作，如果一個個體的一個基因為1，則變?yōu)?，如果使0則變?yōu)?，重新計算該個體的適應(yīng)度和約束值。6） 選取具有最大值的適應(yīng)度個體，如果其適應(yīng)度大于當(dāng)前的最優(yōu)值的適應(yīng)度，則更新當(dāng)前的最優(yōu)值為選取的個體，更新當(dāng)前最優(yōu)值的約束條件和迭代次數(shù)。7） 循環(huán)迭代直到迭代次數(shù)超過設(shè)定最大值。算法的時間復(fù)雜度為O(N*n2)N為迭代次數(shù)，n為物品個數(shù)4.2蟻群算法蟻群算法是由意大利

24、學(xué)者 Dorigo M.等提出的一類模擬螞蟻群體覓食行為的仿生優(yōu)化算法。算法的基本思想是螞蟻將根據(jù)信息素的多少選擇走哪一條路，螞蟻在覓食過程中會留下一種稱為信息素的物質(zhì)，若螞蟻從巢穴到食物源所走的路徑較短，則該螞蟻從巢穴到食物源后再返回巢穴的時間也就較短，這樣同時間內(nèi)在較短路徑上螞蟻分泌的信息素就會較多。后面的螞蟻將根據(jù)其他螞蟻留下來信息素的多少而選擇路徑，某一條路徑上的信息素越多，則這條路徑被選擇的概率越大。螞蟻群體的這種集體行為構(gòu)成了一種學(xué)習(xí)信息的正反饋機制，螞蟻之間通過信息素來交流信息。蟻群算法模擬了這種優(yōu)化機制，通過個體之間的信息交流與協(xié)作來尋找最優(yōu)解。蟻群算法現(xiàn)已成功運用在 TSP、

25、圖像處理、車輛路徑系統(tǒng)、通信系統(tǒng)等領(lǐng)域。它具有較強的魯棒性、分布性、全局優(yōu)化性和易與其它優(yōu)化算法融合的優(yōu)點,現(xiàn)已是解決 NP-hard問題的一個有效工具。 蟻群算法解決 0/1 背包問題的核心是：在某一物品上聚集的信息素越多，則該物品被選擇的概率就越大。背包問題的蟻群算法求解過程是：設(shè)置迭代次數(shù)；將各螞蟻置于相應(yīng)變量的 0、1位置點； 按轉(zhuǎn)移概率移動各螞蟻； 按強度更新方程更新信息素軌跡； 記錄當(dāng)前最佳螞蟻位置； 返回步驟循環(huán)直到滿足退出條件。 就蟻群算法而言當(dāng)處理的數(shù)據(jù)比較小時其具有很快的收斂速度， 而隨著數(shù)據(jù)規(guī)模的增大算法的收斂速度明顯降低。蟻群算法在減少尋優(yōu)計算量和縮短算法運行時間方面，

26、有待進一步改進。針對蟻群算法的缺點，許多學(xué)者對蟻群算法進行了改進。 趙朝卿，胡小兵等提出了一種求解 0-1背包問題的混合型算法(KPAICACA)，先利用蟻群算法求優(yōu)化解，然后利用抗體克隆選擇算法擴大解的搜索空間，使得在收斂速度和尋優(yōu)能力兩方面都有明顯改善。具體方法是：每個物品 i的屬性有重量 ci，價值 pi和信息素 i，即信息素積累在物品上。選擇物品 i的期望度為 i=pi/ci。每只螞蟻都附一個背包和一個禁忌表， 螞蟻將根據(jù)選中物品的重量來決定是否將其裝入背包。 若物品裝入背包而不超過其容量，則繼續(xù)選擇下一個物品；否則將其編號放入禁忌表中，以后選擇物品時不再考慮。經(jīng)過 n次選擇，構(gòu)建了一

27、個由物品編號表示的解，當(dāng) m 只螞蟻都構(gòu)建了自己的解，將這些編號解變換為 0-1 序列解，每個序列解被視做一個抗體，抗體編碼的長度為 n，抗體群的規(guī)模等于螞蟻種群的規(guī)模 m。隨后對抗體群進行克隆、變異和選擇操作。抗體免疫克隆算法搜索完成后，根據(jù)背包中物品的價值總和 P，記錄最優(yōu)解以及對應(yīng)的物品價值總和，并對物品上的信息素進行更新。 43 量子算法求解背包問題 量子算法從概率算法出發(fā)，系統(tǒng)由一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)有一個狀態(tài)幾率矢量，通過狀態(tài)幾率矢量和狀態(tài)轉(zhuǎn)移矩陣得到下一個狀態(tài)。長度為 的量子字節(jié)串A1n在 1-n中Ai=Xi (xi (O，1 )則 A顯然有N2 種狀態(tài)用量子算法求解背包問題的

28、步驟如下：1.給定常數(shù)c，井隨機選取A的N種狀態(tài)在N種狀態(tài)中選擇最大的Y=Ai*Pi.且 wi*PiW2. 重復(fù)下列操作 c次2.1對2n個狀態(tài)給定初始幾率幅均為(1/N, 1/N,-, 1/N),并將y綁定在一起，滿足1條件的做標記。2.2.1給定常數(shù)m=1并且r=6/5 2.2.2隨機選取非負整數(shù) jy且重量小于背包重量，則y狀態(tài)的值改為y1退出 2.2. 2.2.6否則 mmin(r, N)，goto 2.2.2 3得到最優(yōu)解 Y量子算法的時間復(fù)雜度為O(C*2n)c為重復(fù)的次數(shù)。4.4 模擬退火算法1983 年，Kirkpatric 等將熱力學(xué)中的退火思想引入組合優(yōu)化領(lǐng)域，提出了一種解

29、大規(guī)模組合優(yōu)化問題，特別是NP 完全組合優(yōu)化問題的有效近似算法模擬退火算法。它源于對固體退火過程的模擬，使算法在多項式時間內(nèi)給出一個近似最優(yōu)解。模擬退火算法是模仿固體物質(zhì)的退火過程。高溫物質(zhì)降溫時其內(nèi)能隨之下降，如果降溫過程充分緩慢，則在降溫過程中物質(zhì)體系始終處于平衡狀態(tài)，反之降溫太快，則降到同一低溫時會保持內(nèi)能。用模擬退火算法求解01 背包問題的過程如下：（1）解空間S由于模擬退火算法已經(jīng)證明，最后的最優(yōu)解并不太依賴初始解的選取，所以在這里可任選一初始解，本文初始解為（0，0，0）1n。（2）目標函數(shù)。最大價值的目標函數(shù)為：（3）新解的產(chǎn)生。隨機選取物品，若i 不在背包中，則將其直接放入背包

30、中，或同時從背包中隨機取出另一物品j；若i 已在背包中，則將其取出，并同時隨機裝入另一物品j。（4）背包的價值差和重量差。根據(jù)上述新解產(chǎn)生的3 種可能，相應(yīng)的背包價值差為：相應(yīng)的背包重量差為其中m 為當(dāng)前狀態(tài)下背包重量m 的增量。（5）接受準則。由于01 背包問題是個有約束的最優(yōu)化問題，所以本文采用的是擴充了的Metropolis 準則其中t 為溫度控制參數(shù)。在算法實現(xiàn)過程中，其退火溫度t 控制著求解過程向最小值的優(yōu)化方向進行，同時又以概率exp（f t）來接收劣質(zhì)解，因此模擬算法可跳出局部極小值點。只要初始溫度足夠高，退火過程足夠慢，算法能收斂到全局最優(yōu)解。5 其它算法和各種算法的改進除了以

31、上介紹的算法外，還有DNA 算法、分支限界法、粒子群優(yōu)化算法、人工神經(jīng)網(wǎng)絡(luò)、遞歸法、克隆選擇算法、禁忌搜索與GA 算法，混合算法等。由于各種算法都有其自身的優(yōu)點和不足，許多學(xué)者通過利用一種算法的優(yōu)點同時通過結(jié)合其它算法避免該算法的不足，出現(xiàn)了混合算法，這些算法都取得了很大的成功。5.1遞歸法遞歸算法的基本思想是假設(shè)用布爾函數(shù)knap(s，n)表示孢件物品放人可容質(zhì)量為s的背包中是否有解，當(dāng)knap函數(shù)的值為真時說明問題有解，相反當(dāng)值為假時，無解。這里可以通過輸入s和行的值，進行以下幾種情況的討論。(1)當(dāng)s=0時，可知問題有解，即函數(shù)knap(s，n)的值為true。(2)當(dāng)s0且n0且n1時

32、，才符合實際情況，這時又分為兩種情況。即：若選擇的一組物體中不包括。則knap(s，n)的解就是knap(s，n-1)的解；若選擇的一組物體中包括訓(xùn)。則knap(s，n)的解就是knap(，n-1)的解。這樣，一組叫。的值就是問題的最佳解，就能將規(guī)模為姐的問題轉(zhuǎn)化為規(guī)模為n一1的問題。綜上所述“背包問題”的遞歸函數(shù)定義為：上述算法對于所有物品中的某幾件恰好裝滿背包時，能準確求出最佳解。一般情況，對于某一些物品無論怎么裝都不能裝滿背包，必須按背包的最大容量來裝。若物品件數(shù)為4，其質(zhì)量分別為10，2，5，4，背包的容量為20，則這四件物品無論怎么放都不能恰好裝滿背包，只能最大限度地裝入背包，即必須

33、裝下10，5，4這三件物品，這樣就能得到最大重量19。對于這種裝不滿的背包，它的解決辦法是按所有物品的組合質(zhì)量最大來裝背包的。如果還裝不滿，則可以考慮剩余空間能否裝下所有物品中最小的那件；如果連最小的都裝不下了。此時則說明得到的解是最佳解，問題解決。這樣必須先找出所有鉀件物品中質(zhì)量最小的(它的重量為min)，但是為了解決問題，不能增加太多的運算次數(shù)，并且必須運用上述遞歸函數(shù)。那么可通過修改s的值，即背包的容量，從背包容量s中減去是(它的值是。到大于min一1之間的一個整數(shù)值)，再調(diào)用遞歸函數(shù)。當(dāng)是一。時，即能裝滿背包，其他值也能保證背包能最大限度裝滿，這樣所有問題都解決了。5.2優(yōu)先策略的算法

34、按重量，進行調(diào)整，作為待選隊列。假設(shè)前面已經(jīng)選擇了s個，即為最優(yōu)選擇的前s件物品，則應(yīng)滿足：對后面等待選擇的物品來說，與之對應(yīng)的無疑滿足：即所選擇的物品重量比其所有待選擇的物品重量大。因此，對待選擇的物品是否被選中將分為：和兩種情況。(1) 對于的情況，將插入已選擇的J隊列中，然后根據(jù)ci，的大小找到其相應(yīng)的位置。(2) 對于的情況，有：若存在，則將插入并按ci排序后，將從已選擇的隊列中刪除并插入按ci從大到小、重量從小到大地排序到二次篩選隊列中。若存在，則在待選隊列中選擇滿足的物品插入已選擇的J隊列中并按ci排序，將從已選擇的隊列中刪除并插入按ci從大到小、重量從小到大排序到二次篩選隊列中；若不存在滿足的待選物品，則將插入到二次篩選隊列中。當(dāng)待選隊列為空時，選擇隊列從s到1與從二次篩選隊列中選擇的元素進行優(yōu)化選擇。若存在：將組合的各元素X，插入已選擇的，隊列中，然后根據(jù)ci的大小找到其相應(yīng)的位置：。當(dāng)中已完成對首元素組合的篩選后，此時的J隊列為最優(yōu)選擇。結(jié)束語通過計算復(fù)雜度的研究表明，背包問題是一個經(jīng)典的NP問題。對于規(guī)模過大的01 背包問題，人們還是無法找到完美的求解方法。所有智能算法都是在一定范圍內(nèi)求解。許多算法有其局限性，例如只能解決特定的 背包問題，但用于其它背包問題時求解結(jié)果不一定好。背包問題未