【文章內(nèi)容簡介】 須至少包含問題的一個(gè)解 (可能是最優(yōu)的 )。 使用遞 歸回溯法解決背包問題的優(yōu)點(diǎn)在于它算法思想簡單，而且它能完全 遍歷搜索空間，肯定能找到問題的最優(yōu)解奉但是由于此問題解的總組合數(shù)有 n2 個(gè)，因此隨著物件數(shù) n 的增大， 其解的空間將以 n n2 級(jí)增長，當(dāng) n大到一定程度上，用此算法解決背包問題將是不現(xiàn)實(shí)的。 下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖或樹 。一旦定義了解空間的組織方法， 這個(gè)空間即可按照深度優(yōu)先的方法從開始結(jié)點(diǎn)進(jìn)行搜索，利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。 01 背包問題的實(shí)現(xiàn) ① 回溯法的 算法描述 回溯法是一種系統(tǒng)地搜索問題解答的方法。為了實(shí)現(xiàn)回溯，首先需要為問題定義一個(gè)解空間，這個(gè)解空間必須至少包含問題的一個(gè)解 (可能是最優(yōu)的 )。一旦定義了解空間的組織方 要選擇一個(gè)對(duì)象的子集，將它們裝人背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹的形狀。首先形成一個(gè)遞歸算法，去找到可獲得的最大收益。然后，對(duì)該算法加以改進(jìn)，形成代碼。改進(jìn)后的代碼可找到獲得最大收益時(shí)包 含在背包中的對(duì)象的集合 。 左 子樹 表示一個(gè)可行的結(jié)點(diǎn)，無論何時(shí)都要移動(dòng)到它，當(dāng)右子樹可能含有比當(dāng)前最優(yōu)解還優(yōu)的解時(shí)，移動(dòng)到它。一種決定是否要移動(dòng)到右子樹的簡單方法是r為還未遍歷的對(duì)象的收益之和，將 r加到 cp (當(dāng)前節(jié)點(diǎn)所獲收益 )之上，若 ( r+cp) 9 ? bestp(目前最優(yōu)解的收益 )，則不 需 搜索右子樹。一種更有效的方法是按收益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的剩余容量， 當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)， 就使用它的一部分 。 ② 解 01背包問題的回溯算法描述如下 ： templateclass Typew,class Typep class Knap{ friend Typep Knapsack(Typep*,Typew*,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à)值 }。 templateclass Typew,class Typep void knapTypew,Typep::Backtrack(int i) { if(in){//到達(dá)葉結(jié)點(diǎn) bestp=cp。 return。} if(cw+w[i]=c){//進(jìn)入左子數(shù) cw+=w[i]。 cp+=p[i]。 Backtrack(i+1)。 cw=w[i]。 cp=p[i]。 if(Bound(i+1)bestp) //進(jìn)入右子數(shù) Backtrack(i+1)。 10 } templateclass Typew,class Typep Typep KnapTypew,Typep::Bound(int i) {//計(jì)算上界 Typew cleft=ccw。 //剩余容量 Typep b=cp。 //以物品單位重量價(jià)值遞減序裝入物品 while (i=namp。amp。w[i]=cleft){ cleft=w[i]。 b+=p[i]。 i++。 } //裝滿背包 if(i=n)b+=p[i]* cleft/w[i]。 return b。 } class Object { friend int Knapsack(int*,int *,int,int)。 public。 int operator=(Object a) const {return(d=)。} private: int ID。 float d。 }。 templateclass Typew,class Typep Typep Knapsack(Typep p[], Typep w[],Typew c,int n) { //為 Knap::Backtrack 初始化 Typew W=0。 Typep P=0。 Object*Q=new Object[n]。 11 for(int i=1。i=n。i++){ Q[i1].ID=i。 Q[i1].d=*p[i]/w[i]。 p+=p[i]。 w+=w[i]。 } if(w=c)return P。//裝入所有物品 //依物品單位重量價(jià)值排序 sort(Q,n)。 KnapTypew,TypepK。 =new Typep[n+1]。 =new Typew[n+1]。 for (int i=1。i=n。i++){ [i]=p[Q[i1].ID]。 [i]=w[Q[i1].ID]。 } =0。 =0。 =c。 =n。 =0。 //回搠搜索 (1)。 delete[]Q。 delete[]。 delete[]。 reture K,bestp。 }[1] ③ 算法效 率 由于計(jì)算上界函數(shù)需要 O(n)時(shí)間 ，在最壞情況下有 O( n2 )個(gè)右孩子結(jié)點(diǎn)需要上界函數(shù)，故計(jì)算 01背包問題的回溯算法所需的計(jì)算時(shí)間復(fù)雜度為 O(nn2 )。 12 對(duì)回溯法的改進(jìn)主要是對(duì)判斷是否移動(dòng)右子樹上，一種更有效的方法是按效益密度 vi/wi 對(duì)剩余對(duì)象排序，將對(duì)象按密度遞減的順序去填充背包的 剩余容量，當(dāng)遇到第一個(gè)不能全部放人背包的對(duì)象時(shí)，就使用它的一部分。 回溯算法的運(yùn)行時(shí)間取決于它在搜索過程中所生成的結(jié)點(diǎn)數(shù) ,而限界函數(shù)可以大量減少所生成的結(jié)點(diǎn)個(gè)數(shù) ,省去許多無謂的搜索 , 使得搜索速度更快 ,其調(diào)用限界函數(shù)計(jì)算上界需花費(fèi) O(n)時(shí)間 ,最壞情況下有 O( n2 )個(gè)結(jié)點(diǎn)需調(diào)用限界函數(shù) ,需花費(fèi) O(n)時(shí)間 ,所以該算法的時(shí)間復(fù)雜度為 O(n n2 )[12]。 回溯法的另一個(gè) 重要特性就是在搜索執(zhí)行的同時(shí)產(chǎn)生解空間 在搜索期間的任何時(shí)刻 僅保留從開始結(jié)點(diǎn)到當(dāng)前可擴(kuò)展結(jié)點(diǎn)的路徑其空間需求為 O(從開始結(jié)點(diǎn)起最長路徑的長度 ),所以 ,此處該算法的空間復(fù)雜度為 O(n),回溯法是算法設(shè)計(jì)的基本方法之一 ,它適用于解一些涉及到尋找一組解的問題或者求滿足某些約束條件的最優(yōu)解的問題 ,且適用于求解組合數(shù)量較大的問題 。 01 背包問題在 分枝 限界法 中的實(shí)現(xiàn) 分枝 限界法 的基本原理與分析 分枝限界 發(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é)束。 有兩種常用的方法可用來選擇下一個(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)或收益。如果查找一個(gè)具有最小耗費(fèi)的解，則活結(jié)點(diǎn)表可以最小堆來建立，下一個(gè)E結(jié)點(diǎn)就是具有最小耗費(fèi)的活結(jié)點(diǎn)，如果希望搜索一個(gè)具有最大收益的解， 則可用最大堆來構(gòu)造活結(jié)點(diǎn)表，下一個(gè) E結(jié)點(diǎn)是具有最大收益的活結(jié)點(diǎn) [15]。 13 01 背包問題的實(shí)現(xiàn) 工作在解空間樹上的 FIFO 分枝定界方法非常類似于從根結(jié)點(diǎn)出發(fā)的寬度優(yōu)先搜索。它們的主要區(qū)別時(shí)在 FIFO 分枝定界中不可行的結(jié)點(diǎn)不會(huì)被搜索。 01 背包問題的最大收益分枝定界算法可以使用定界 函數(shù)來計(jì)算活結(jié)點(diǎn)的收益上限 upprofit，使得以活結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)的收益值都不可能超過 upprofit，活結(jié)點(diǎn)的最大堆使用 upprofit作為關(guān)鍵值域。在子集樹中執(zhí)行最大收益分枝定界搜索的函數(shù)首先初始化活結(jié)點(diǎn)的最大堆，并使用一個(gè)數(shù)組bestx來記錄最優(yōu)解。由于需要不斷地利用收益密度來排序，物品的索引值會(huì)隨之變化，因此必須將函數(shù)所生成的結(jié)果映射回初始時(shí)的物品索引。函數(shù)中的循環(huán)首先檢 驗(yàn) E結(jié)點(diǎn)左孩子的可行性，如它是可行的，則將它加 入 子集樹及活結(jié)點(diǎn)隊(duì)列 (即最大堆 )， 僅當(dāng)結(jié)點(diǎn)右 子樹 的定界值指明可能找到一 個(gè)最優(yōu)解時(shí)才將右孩子加 入 子集樹和隊(duì)列中。 則 主要 算法描述為： class Object{ friend int Knapsack(int *,int *,int,int,int *)。 public: int operator=(Object a) const {return (d=)。} private: int ID。 float d。//單位重量價(jià)值 }。 templateclass Typew,class Typep class Knap。 class bbnode{ friend Knapint,in