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