【正文】 nd int Knapsack(int *,int *,int,int,int *)。函數(shù)中的循環(huán)首先檢驗 E結點左孩子的可行性，如它是可行的，則將它加入子集樹及活結點隊列(即最大堆)，僅當結點右子樹的定界值指明可能找到一個最優(yōu)解時才將右孩子加入子集樹和隊列中。 有兩種常用的方法可用來選擇下一個 E結點: ① 先進先出(FIFO)即從活結點表中取出結點的順序與加人結點的順序相同，因此活結點表的性質(zhì)與隊列相同。n2對回溯法的改進主要是對判斷是否移動右子樹上，一種更有效的方法是按效益密度 vi/wi 對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量，當遇到第一個不能全部放人背包的對象時，就使用它的一部分。 =n。 =new Typew[n+1]。i++){ Q[i1].ID=i。} private: int ID。w[i]=cleft){ cleft=w[i]。10Backtrack(i+1)。 //物品價值數(shù)組Typew cw。一種更有效的方?法是按收益密度 vi/wi 對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量， 當遇到第一個不能全部放人背包的對象時， 就使用它的一部分。 01 背包問題的實現(xiàn)① 回溯法的算法描述回溯法是一種系統(tǒng)地搜索問題解答的方法。動態(tài)規(guī)劃主要是求解最優(yōu)決策序列，當最優(yōu)決策序列中包含最優(yōu)決策子序列時，可建立動態(tài)規(guī)劃遞歸方程，它可以幫助高效地解決問題 [8]。 if(c=w[1]) m[1][c]=max(m[1][c],m[2][cw[1]]+v[1])。i){ jMax=min(w[i]1,c)。 for (int j=0。由上面的動態(tài)規(guī)劃法的介紹，可以看出 01 背包問題，是符合多段決策的特點和具有重疊子問題。Mwxi??pxi2 01 背包問題的實現(xiàn) 01 背包問題在動態(tài)規(guī)劃中的實現(xiàn) 動態(tài)規(guī)劃的基本原理與分析動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。背包問題的數(shù)學描述如下：要求找到一個 n 元向量(x1，x2…xn)，在滿足約束條件： 情況下，使得目標函數(shù) ，其中，??????10iixwpxi?ma1 i n；M0 ；wi0；pi0。01 背包是一類很典型的優(yōu)化問題,研究它有很重要的實際意義，這不僅是由于它結構簡潔，可以作為子問題為研究更復雜的問題奠定理論基礎，有很高的理論研究價值，而且由于它是許多實際工程應用問題的種通用化描述，在很多實際問題當中有著非常廣泛的應用背景，例如項目決策等。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實現(xiàn)的。并以具體實例詳細描述不同方法求解問題解時算法基本思想，然后就解決 01 背包問題對這四種算法進行詳細的比較，總結四種方法實現(xiàn)的優(yōu)缺點并得出結論。學位論文作者簽名： 日期： 年 月 日學位論文版權使用授權書本學位論文作者完全了解學校有關保障、使用學位論文的規(guī)定，同意學校保留并向有關學位論文管理部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱。本人授權省級優(yōu)秀學士學位論文評選機構將本學位論文的全部或部分內(nèi)容編入有關數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存和匯編本學位論文。如何將背包問題應用于實際問題中，有針對性地設計適合求解實際 01 背包問題的算法，并很好地解決實際問題，是計算機工作者不斷思索、研究的一個領域。背包問題是熟知的不可計算問題，背包體制以其加密，解密速度快而其人注目。他是最基本的背包問題，即對一個物體要么選用，要么就拋棄，不能將一個物體再繼續(xù)細分的4情況。滿足約束條件的任何向量都是一個可行解，而使?得目標函數(shù)達到最大的那個可行解則為最優(yōu)解 [1]。但是經(jīng)分解得到的子問題往往不是互相獨立的。因此，在設計 01 背包問題解決方案時，可以將整個物品放到背包的過程，看成一個取物品的過程。j=jMax。 for (int j=0。}templateclass Typevoid Traceback(Type* * m,int w,int c,int n,int x){ for (int i=1。 01 背包問題在回溯法中的實現(xiàn) 回溯法的基本原理與分析回溯是一種系統(tǒng)地搜索問題解答的方法。為了實現(xiàn)回溯，首先需要為問題定義一個解空間，這個解空間必須至少包含問題的一個解(可能是最優(yōu)的)。② 解 01 背包問題的回溯算法描述如下：templateclass Typew,class Typepclass Knap{ friend Typep Knapsack(Typep*,Typew*,Typew,int)。 //當前重量Typep cp。cw=w[i]。 b+=p[i]。 float d。 Q[i1].d=*p[i]/w[i]。 for (int i=1。 =0?；厮菟惴ǖ倪\行時間取決于它在搜索過程中所生成的結點數(shù),而限界函數(shù)可以大量減少所生成的結點個數(shù),省去許多無謂的搜索, 使得搜索速度更快 ,其調(diào)用限界函數(shù)計算上界需花費 O(n)時間 ,最壞情況下有 O( )個結點需調(diào)用n2限界函數(shù) ,需花費 O(n)時間,所以該算法的時間復雜度為 O(n )[12]。 ② 最小耗費或最大收益法在這種模式中，每個結點都有一個對應的耗費13或收益。則主要算法描述為：class Object{ friend int Knapsack(int *,int *,int,int,int *)。 private: bbnode *parent。 //活結點在子集樹中所處的層序號 bbnode *ptr。 //背包容量 int n。 //為 bestx 分配存儲空間 bestx=new int[n+1]。 AddliveNode(up,cp+p[i],cw+w[i],ture,i+1)。 up=。它將問題的每一個可能解看作是群體中的一個個體(染色體)，并將每一個染色體編碼成串的形式，再根據(jù)預定的目標函數(shù)對每個個體進行評價，給出一個適應值。傳統(tǒng)的交叉算子是隨機操作，后代簡單地繼承了“父母”的一部分基因，并不能保證子代的性能優(yōu)于父輩，而且以這種方式點對點的搜索范圍有限，可能會忽略鄰域內(nèi)更好的點而使結果收斂于局部最優(yōu)。18 (6) 當某代得到的結果滿足要求或當前代數(shù)等于結束代數(shù)時算法結束得到結果，否則重復上述步驟(3)、(4) [7]。 end。 End。 a:=c。動態(tài)規(guī)劃算法的基本思想是把原問題分解為一系列子問題，然后從這些子問題中求出原問題的解。故該算法不常用在背包問題求解。雖然最大收益或最小耗費分枝限界在直覺上要好于回溯法，并且在許多情況下可能會比回溯法檢查更少的結點，但在實際應用中，它可能會在回溯法超出允許的時間限制之前就超出了內(nèi)存的限制。通過以上對 01 背包問題的求解分析，我們可以看到各種算法設計方法有各內(nèi)不同的特點，針對不同的問題領域，它們有不同的效率，對于求解 01 背包問題，各算法的時問復雜度、優(yōu)缺點以及改進方法的比較如下表所示 [19]:動態(tài)規(guī)劃 O(min{nc, }）n2可求得最優(yōu)決 策序列 速度較慢 建立動態(tài)規(guī)劃 遞歸方程回溯法 O(n ）n能夠獲得最優(yōu) 解 時間復雜度較 高判斷右子樹時，按效率密度vi/wi 對剩余對象排序22分枝限界法 O( ）n2速度較快，易求解占用的內(nèi)存較大，效率不高最大收益或最小消耗分枝限界法，F(xiàn)IFO法遺傳算法 O(n ）n能夠解決傳統(tǒng)算法不能解決的問題，能夠獲得最優(yōu)解速度較慢，算法不成熟基于懲罰函數(shù)修正方法和譯碼方法4 總結與展望 本文就回溯法，分枝限界法，遺傳算法這 4 種求解 01 背包問題的方法進行研究比較，全方位的了解背包問題在實現(xiàn)的方法,以及各方法的優(yōu)勢和劣勢，通過比較，了解哪種方法是在什么樣的情況下是最實用的方法，然后在以后的實際運用中針對實際問題，找到最簡單的方法解決 01 背包問題。本文之得以完成，要特別感謝我的指導老師賓云峰、楊健老師。他們嚴謹?shù)闹螌W精神、淵博的理論知識和豐富的實踐經(jīng)驗使我受益匪淺。比如資源分配、投資決策、裝載設計、公交車調(diào)度等一系列的問題都可以歸結到組合優(yōu)化問題中來。測試中,每個 01 背包問題的效益和重量分別為隨機產(chǎn)生的兩組數(shù)據(jù),其取值范圍為[0,999],背包容量定為 1125。對于一個最優(yōu)化問題，一定數(shù)量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。回溯法在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結點出發(fā)搜索解空間樹。203 解 01 背包問題的算法