【正文】 述如下： 要求找到一個(gè) n 元向量 (x1， x2? xn)，在滿足約束條件：?????????10 iiixMwx 情況下， 使得目標(biāo)函數(shù) pxii?max，其中， 1? i? n； M0；wi0； pi0。 由上面的動(dòng)態(tài)規(guī)劃法的介紹，可以看出 01背包問題，是符合多段決策的特點(diǎn)和具有重疊子問題。i){ jMax=min(w[i]1,c)。動(dòng)態(tài)規(guī)劃主要是求解最優(yōu)決策序列，當(dāng)最優(yōu)決策序列中包含最優(yōu)決策子序列時(shí)，可建立動(dòng)態(tài)規(guī)劃遞歸方程，它可以幫助高效地解決問題 [8]。一種更有效的方法是按收益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量， 當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)， 就使用它的一部分 。 Backtrack(i+1)。} private: int ID。 =new Typew[n+1]。 12 對(duì)回溯法的改進(jìn)主要是對(duì)判斷是否移動(dòng)右子樹上，一種更有效的方法是按效益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的 剩余容量，當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)，就使用它的一部分。函數(shù)中的循環(huán)首先檢 驗(yàn) E結(jié)點(diǎn)左孩子的可行性，如它是可行的，則將它加 入 子集樹及活結(jié)點(diǎn)隊(duì)列 (即最大堆 )， 僅當(dāng)結(jié)點(diǎn)右 子樹 的定界值指明可能找到一 個(gè)最優(yōu)解時(shí)才將右孩子加 入 子集樹和隊(duì)列中。 //結(jié)點(diǎn)所相應(yīng)的重量 int level。 templateclass Typew,class Typep Typep KnapTypew, Typep::MaxKnapsack() {//優(yōu)先隊(duì)列式分支限界法，返回最大價(jià)值， bestx 返回最優(yōu)解 //定義最大堆的容量為 1000 H=new MaxHeapHeapNodeTypep,Typew(1000)。 cp=。在操作中，新點(diǎn)主要是由交叉操作產(chǎn)生。 end。 for j:=0 to n do if a[j]0 then if j+now=n then inc(c[j+now],a[j])。但分枝限界法需要 O( n2 )的解空間。隨著問題規(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ī)劃法。在此，我向尊敬的 賓云峰、楊健 老師 致以崇高的敬意和衷心的感謝 ! 同時(shí)，向參加論文 審閱和答辯的各位專家和老師表示衷心的感謝。為便于各算法間進(jìn)行比較，測(cè)試之前首先把物品按價(jià)值重量比的非增順序排序。回溯法的基本思路是：確定解空間，建立解空間樹，用深度優(yōu)先搜索算法遞歸搜索解空間樹，并同時(shí)注意剪枝 ,常用的分枝一限界法有最小耗費(fèi)法，最大收益法 。 F [i,j] = max { f [ i – w [ j ], j1] + p [ j ], f[ i,j1] } C:求恰好裝滿的情況數(shù)。 begin if vbest then best:=v。 遺傳算法的高效性和強(qiáng)壯性可由 Holland 提出 的模式定理和隱式并行性得以解釋 。 //取下一擴(kuò)展結(jié)點(diǎn) HeapNodeTypep,TypewN。 //物品價(jià)值數(shù)組 Typew cw。 templateclass Typew,class Typep class HeapNode { friend KnapTypew,Typep。它們的主要區(qū)別時(shí)在 FIFO 分枝定界中不可行的結(jié)點(diǎn)不會(huì)被搜索。 delete[]。 } if(w=c)return P。 return b。 templateclass Typew,class Typep void knapTypew,Typep::Backtrack(int i) { if(in){//到達(dá)葉結(jié)點(diǎn) bestp=cp。然后，對(duì)該算法加以改進(jìn)，形成代碼。 else {x[i] =1。j=c。 它把已知問題分為很多子問題，按順序求解子問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最佳的結(jié)果舍棄其余。背包問題就是在資源有限的條件下，追求總的最大收益的資源有效分配問題 。 它是在 1978 年由 Merkel 和 Hellman 提出的。 華中師范大學(xué)漢口分校 本 科 畢 業(yè) 論 文 01 背包問題的算法研究與實(shí)現(xiàn) 院 系 ： 信息科學(xué)技術(shù)學(xué)院 專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 年 級(jí)： 2021級(jí) 學(xué) 生： 劉念 學(xué) 號(hào)： 2021911032 指導(dǎo)老師： 賓云峰、 楊健 華中師范大學(xué)漢口分校 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下獨(dú)立進(jìn)行研究工作所取得的研究成果。它的主要思路是假定某人擁有大量物品，重量各不同。 背包問題 的描 述 背包問題是整數(shù)規(guī)劃中的一類特殊問題，在現(xiàn)實(shí)生活中具有廣泛應(yīng)用 。前一子問題為后面子問題提供信息，而減少計(jì)算量，最后一個(gè)子問題的解即為問題解。j++)m[n][j]=v[n]。c= w[i]。改進(jìn)后的代碼可找到獲得最大收益時(shí)包 含在背包中的對(duì)象的集合 。 return。 } class Object { friend int Knapsack(int*,int *,int,int)。//裝入所有物品 //依物品單位重量?jī)r(jià)值排序 sort(Q,n)。 delete[]。 01 背包問題的最大收益分枝定界算法可以使用定界 函數(shù)來計(jì)算活結(jié)點(diǎn)的收益上限 upprofit，使得以活結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)的收益值都不可能超過 upprofit，活結(jié)點(diǎn)的最大堆使用 upprofit作為關(guān)鍵值域。 public: operator Typep () const {return uprofit。 //當(dāng)前裝包重量 15 Typep cp。 HdeleteMax(N)。 在遺傳算法中，定義長(zhǎng)度較短、低階且適應(yīng)值超過平均適應(yīng)值的模式在群體中數(shù)目的期望值按指數(shù)遞增，這個(gè)結(jié)論成為遺傳算法的基本定理 。 18 if v(s[n]s[k1])=best then exit。 DP: Procedure update。 FIFO(先進(jìn)先出 )法等。每次測(cè)試將程序運(yùn)行 100 21 次所得時(shí)間為運(yùn)行 100 次的平均值。 。 問題規(guī)模 平均計(jì)算時(shí)間 動(dòng)態(tài)規(guī)劃法 回溯法 5 10 15 20 25 50 100 200 從表中的測(cè)試結(jié)果可以看出 當(dāng)問題規(guī)模較小時(shí)，三種方法都有較好的穩(wěn)定性， 計(jì)算時(shí)間都相差不多。該算法跟回溯法類似 。 begin c:=a。 search(k+1,v)。中有一適應(yīng)度函數(shù)，依其適應(yīng)度大小，隨機(jī)進(jìn)行選擇、交叉和變異操作來求此函數(shù)的最大值，即將遺 17 傳算法看成是在某個(gè)空間進(jìn)行求最大值的搜索技術(shù)。 cw=。 //最優(yōu)解 }。 //結(jié)點(diǎn)所相應(yīng)的價(jià)值 Typew weight。由于需要不斷地利用收益密度來排序，物品的索引值會(huì)隨之變化，因此必須將函數(shù)所生成的結(jié)果映射回初始時(shí)的物品索引。 }[1] ③ 算法效 率 由于計(jì)算上界函數(shù)需要 O(n)時(shí)間 ，在最壞情況下有 O( n2 )個(gè)右孩子結(jié)點(diǎn)需要上界函數(shù)，故計(jì)算 01背包問題的回溯算法所需的計(jì)算時(shí)間復(fù)雜度為 O(nn2 )。 =new Typep[n+1]。 int operator=(Object a) const {return(d=)。 cp+=p[i]。一種決定是否要移動(dòng)到右子樹的簡(jiǎn)單方法是r為還未遍歷的對(duì)象的收益之和，將 r加到 cp (當(dāng)前節(jié)點(diǎn)所獲收益 )之上，若 ( r+cp) 9 ? bestp(目前最優(yōu)解的收益 )，則不 需 搜索右子樹。 }[1] 8 ④ 計(jì)算復(fù)雜性分析 利用動(dòng)態(tài)規(guī)劃求解 01 背包問題的復(fù)雜度為 0(min{nc,2n}。i1。 動(dòng)態(tài)規(guī)劃算法的每一步?jīng)Q策都是根據(jù)前一步的 狀態(tài)參量來決定這一步狀態(tài)參量的設(shè)置，也就是說，從初始狀態(tài)到最終狀態(tài)要經(jīng)過多個(gè)過程 ，經(jīng)歷不同的狀態(tài)，不斷地根據(jù)上一步狀態(tài)決定下一狀態(tài)，從而形成了一個(gè)決策序列，最終將整個(gè)問題解決，這就是典型的多段決策的特性。 問題的一般描述是：旅行者背包登山，背包的最大承重為 M，現(xiàn)有 n 個(gè)物品可供選擇裝入背包，第 i 個(gè)物品鶯量為 wi，價(jià)值為 pi，假定物品 i 的一部分xi(0? xi ? 1)放人背包，獲得價(jià)值為 xipi，由于背包最大承重為 M，要求裝入物品總質(zhì)量不過超過 M，問旅行者應(yīng)該如何選擇物品裝入背包，使得裝入物品的價(jià)值總和達(dá)到最大值。背包中的物品中重量是公開的，所有可能 選擇 的物品也是公開的，但背包中的物品是保密的。本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。 關(guān) 鍵 詞 ： 01 背包 動(dòng)態(tài)規(guī)劃 回溯法 分枝 限界法 遺傳 算 法