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