【正文】 在此，我向尊敬的賓云峰、楊健老師致以崇高的敬意和衷心的感謝!同時(shí)，向參加論文審閱和答辯的各位專家和老師表示衷心的感謝。在此，我要感謝華中師范大學(xué)漢口分校信息科學(xué)與技術(shù)學(xué)院的各位領(lǐng)導(dǎo)和老師們，感謝關(guān)心幫助過我的同學(xué)們。但是，往往由于問題的計(jì)算量遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)在有效時(shí)間內(nèi)的計(jì)算能力，使問題的求解變?yōu)楫惓５睦щy。隨著問題規(guī)模的增大，各算法的計(jì)算時(shí)間都在增大， 其中遞歸法的計(jì)算時(shí)間增長(zhǎng)速度最快，當(dāng)問題規(guī)模為 50，100 和 200 時(shí)，其計(jì)算時(shí)間太長(zhǎng)以致失去利用該法求解的意義，而動(dòng)態(tài)規(guī)劃法與回溯法則相對(duì)穩(wěn)定且計(jì)算時(shí)間也相差不多，但是當(dāng)問題規(guī)模大到一定程度，回溯法要優(yōu)于動(dòng)態(tài)規(guī)劃法。為便于各算法間進(jìn)行比較，測(cè)試之前首先把物品按價(jià)值重量比的非增順序排序。對(duì)于一個(gè)子21集空間，回溯法需要 0(n)的內(nèi)存空間，而分枝限界則需要 0(2n)的空間。通常解用二進(jìn)制 0 和 1 表示，進(jìn)化從一個(gè)個(gè)體發(fā)生，然后一代一代發(fā)生。但分枝限界法需要 O( )n2的解空間?；厮莘ǖ幕舅悸肥牵捍_定解空間，建立解空間樹，用深度優(yōu)先搜索算法遞歸搜索解空間樹，并同時(shí)注意剪枝,常用的分枝一限界法有最小耗費(fèi)法，最大收益法。但后者的實(shí)現(xiàn)算法可讀性要優(yōu)于前者。通過對(duì) O1 背包問題的算法設(shè)計(jì)及時(shí)間復(fù)雜度分析可以看出。 for j:=0 to n do if a[j]0 then if j+now=n then inc(c[j+now],a[j])。 F [i,j] = max { f [ i – w [ j ], j1] + p [ j ], f[ i,j1] } C:求恰好裝滿的情況數(shù)。 19F:=f1。 優(yōu)化：當(dāng)前狀態(tài)只與前一階段狀態(tài)有關(guān)，可降至一維。 end。 begin if vbest then best:=v。使變異后的適應(yīng)度至少大于等于原適應(yīng)度，否則重新選擇變異位進(jìn)行變異，如此重復(fù)若干次，若適應(yīng)度值沒有提高，則變異失敗。 (3) 選擇操作：根據(jù)選擇概率選擇染色體，將上述的個(gè)體作為第 0 代。在操作中，新點(diǎn)主要是由交叉操作產(chǎn)生。遺傳算法的高效性和強(qiáng)壯性可由 Holland 提出的模17式定理和隱式并行性得以解釋。 }[1] 01 背包問題在遺傳算法中的實(shí)現(xiàn) 遺傳算法的基本原理與分析 遺傳算法作為一種解決復(fù)雜問題的有效方法是在 1975 年首次由美國密西根大學(xué)的 Holland 教授和他的同事們借鑒生物界自然選擇和進(jìn)化機(jī)制基礎(chǔ)之上提出的，它是基于生物進(jìn)化中自然選擇、適者生存和物種遺傳思想的一種搜索算法。j0。 cp=。 //取下一擴(kuò)展結(jié)點(diǎn) HeapNodeTypep,TypewN。 if(wt=c){//左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn) if(cp+p[i]bestp)bestp=cp+p[i]。 cw =cp =0。templateclass Typew,class TypepTypep KnapTypew, Typep::MaxKnapsack(){//優(yōu)先隊(duì)列式分支限界法，返回最大價(jià)值，bestx 返回最優(yōu)解 //定義最大堆的容量為 1000 H=new MaxHeapHeapNodeTypep,Typew(1000)。 //物品價(jià)值數(shù)組 Typew cw。 //指向擴(kuò)展結(jié)點(diǎn)的指針15 Typew c。 private: MaxHeapHeapNodeTypep,Typew*H。 //結(jié)點(diǎn)所相應(yīng)的重量 int level。templateclass Typew,class Typep class HeapNode { friend KnapTypew,Typep。 friend int Knapsack(int *,int *,int,int,int *)。 float d。函數(shù)中的循環(huán)首先檢驗(yàn) E結(jié)點(diǎn)左孩子的可行性，如它是可行的，則將它加入子集樹及活結(jié)點(diǎn)隊(duì)列(即最大堆)，僅當(dāng)結(jié)點(diǎn)右子樹的定界值指明可能找到一個(gè)最優(yōu)解時(shí)才將右孩子加入子集樹和隊(duì)列中。它們的主要區(qū)別時(shí)在 FIFO 分枝定界中不可行的結(jié)點(diǎn)不會(huì)被搜索。 有兩種常用的方法可用來選擇下一個(gè) E結(jié)點(diǎn): ① 先進(jìn)先出(FIFO)即從活結(jié)點(diǎn)表中取出結(jié)點(diǎn)的順序與加人結(jié)點(diǎn)的順序相同，因此活結(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。每個(gè)活結(jié)點(diǎn)有且僅有一次會(huì)變成 E結(jié)點(diǎn)。n2對(duì)回溯法的改進(jìn)主要是對(duì)判斷是否移動(dòng)右子樹上，一種更有效的方法是按效益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量，當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)，就使用它的一部分。 delete[]。 =n。 [i]=w[Q[i1].ID]。 =new Typew[n+1]。 }if(w=c)return P。i++){ Q[i1].ID=i。 Typep P=0。} private: int ID。return b。w[i]=cleft){ cleft=w[i]。}templateclass Typew,class TypepTypep KnapTypew,Typep::Bound(int i){//計(jì)算上界 Typew cleft=ccw。10Backtrack(i+1)。templateclass Typew,class Typepvoid knapTypew,Typep::Backtrack(int i){ if(in){//到達(dá)葉結(jié)點(diǎn)bestp=cp。 //物品價(jià)值數(shù)組Typew cw。Typew c。一種更有效的方?法是按收益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量， 當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)， 就使用它的一部分。然后，對(duì)該算法加以改進(jìn)，形成代碼。 01 背包問題的實(shí)現(xiàn)① 回溯法的算法描述回溯法是一種系統(tǒng)地搜索問題解答的方法。使用遞歸回溯法解決背包問題的優(yōu)點(diǎn)在于它算法思想簡(jiǎn)單，而且它能完全遍歷搜索空間，肯定能找到問題的最優(yōu)解奉但是由于此問題解的總組合數(shù)有個(gè)，因此隨著物件數(shù) n 的增大，其解的空間將以 n 級(jí)增長(zhǎng)，當(dāng) n 大到一定n2 2程度上，用此算法解決背包問題將是不現(xiàn)實(shí)的。動(dòng)態(tài)規(guī)劃主要是求解最優(yōu)決策序列，當(dāng)最優(yōu)決策序列中包含最優(yōu)決策子序列時(shí)，可建立動(dòng)態(tài)規(guī)劃遞歸方程，它可以幫助高效地解決問題 [8]。8 else {x[i] =1。 if(c=w[1]) m[1][c]=max(m[1][c],m[2][cw[1]]+v[1])。for(intj=w[i]。i){ jMax=min(w[i]1,c)。j=c。 for (int j=0。因此???ni2iiyv??niizw21? ??niizv2 1y?ni1c?niizw2?這說明(y1，z2…zn)是所給 01 背包問題的一個(gè)更優(yōu)解，從而(y1，y2…yn)不是所給 01 背包問題的最優(yōu)解。由上面的動(dòng)態(tài)規(guī)劃法的介紹，可以看出 01 背包問題，是符合多段決策的特點(diǎn)和具有重疊子問題。它把已知問題分為很多子問題，按順序求解子問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最佳的結(jié)果舍棄其余。Mwxi??pxi2 01 背包問題的實(shí)現(xiàn) 01 背包問題在動(dòng)態(tài)規(guī)劃中的實(shí)現(xiàn) 動(dòng)態(tài)規(guī)劃的基本原理與分析動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。問應(yīng)如何裝入背包中的物品，使得裝人背包中物品的總價(jià)值最大？在選擇裝人背包的物品時(shí)，對(duì)每種物品 i 只有兩種選擇，即裝入背包、不裝入背包。背包問題的數(shù)學(xué)描述如下：要求找到一個(gè) n 元向量(x1，x2…xn)，在滿足約束條件： 情況下，使得目標(biāo)函數(shù) ，其中，??????10iixwpxi?ma1 i n；M0 ；wi0；pi0。背包問題就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。01 背包是一類很典型的優(yōu)化問題,研究它有很重要的實(shí)際意義，這不僅是由于它結(jié)構(gòu)簡(jiǎn)潔，可以作為子問題為研究更復(fù)雜的問題奠定理論基礎(chǔ)，有很高的理論研究?jī)r(jià)值，而且由于它是許多實(shí)際工程應(yīng)用問題的種通用化描述，在很多實(shí)際問題當(dāng)中有著非常廣泛的應(yīng)用背景，例如項(xiàng)目決策等。其中回溯法是常見的一種求解方法。附加一定的限制條件，給出重量，而要列出可能的物品，在計(jì)算上是不可實(shí)現(xiàn)的。它是在 1978 年由 Merkel 和 Hellman 提出的。并以具體實(shí)例詳細(xì)描述不同方法求解問題解時(shí)算法基本思想，然后就解決 01 背包問題對(duì)這四種算法進(jìn)行詳細(xì)的比較，總結(jié)四種方法實(shí)現(xiàn)的優(yōu)缺點(diǎn)并得出結(jié)論。（請(qǐng)?jiān)谝陨舷鄳?yīng)方框內(nèi)打“√” ）學(xué)位論文作者簽名： 日期： 年 月 日導(dǎo)師簽名： 日