【正文】 e practical, and to design targeted for the practical algorithms of solving 01 Knapsack Problem and to solve the practical problems very well, is an area of puter workers’ constantly thinking and study. Key words： 01 knapsack problem dynamic programmi backtracking branch Bound method geic algorithm 3 1 緒論 01 背包問題是計算機科學(xué)中的一個非常經(jīng)典的優(yōu)化問題。 它是在 1978 年由 Merkel 和 Hellman 提出的。此人通過秘密地選擇一部分物品并將它們放到背包中來加密消息。附加一定的限制條件，給出重量，而要列出可能的物品，在計算上是不可實現(xiàn)的。但是，大多數(shù)一次背包體制均被破譯了，因此現(xiàn)在很少有人使用它。其中回溯法是常見的一種求解方法。如何將背包問題應(yīng)用于實際問題中，并很好地解決實際問題，是計算機工作者不斷思索、研究的一個領(lǐng) 域。 01 背包是一類很典型的優(yōu)化問題 ,研究它有很重要的實際意義 ， 這不僅是由于它結(jié)構(gòu)簡潔 ， 可以作為子問題為研究更復(fù)雜的問題奠定理論基礎(chǔ) ， 有很高的理論研究價值 ， 而且由于它是許多實際工程應(yīng)用問題的種通用化描述 ， 在很多實際問題當(dāng)中有著非常廣泛的應(yīng)用 背景 ， 例如項目決策 等。 它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，在經(jīng)濟管理、資源分配、投資決 4 策、裝載設(shè)計等領(lǐng)域有著重要的應(yīng)用價值。背包問題就是在資源有限的條件下，追求總的最大收益的資源有效分配問題 。 如 果能提出求解此問題的有效算法， 則具有很好的經(jīng)濟價值和決策價值 。 背包問題的數(shù)學(xué)描述如下： 要求找到一個 n 元向量 (x1， x2? xn)，在滿足約束條件：?????????10 iiixMwx 情況下， 使得目標(biāo)函數(shù) pxii?max，其中， 1? i? n； M0；wi0； pi0。 01 背包問題 ① 01 背包問題的 提出 給定 n 種物品和 1 個背包。問應(yīng)如何裝入背包中的物品，使得裝人背包中物 品的總價值最大 ？ 在選擇裝人背包的物品時，對每種物品 i只有兩種選擇，即裝入背包、不裝入背包。該問題稱為 01背包問題。 5 2 01 背包問題的實現(xiàn) 01 背包問題在動態(tài)規(guī)劃中的實現(xiàn) 動態(tài)規(guī)劃的 基本原理 與分析 動態(tài)規(guī)劃算法 的 基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。不同子問題的數(shù)目常常只有多項式量級。 它把已知問題分為很多子問題，按順序求解子問題，在每一種情況下，列出各種情況的局部解，按條件從中選取那些最有可能產(chǎn)生最佳的結(jié)果舍棄其余。采用此方法求解 01 背包問題的主要步驟如下： ①分析最優(yōu)解的結(jié)構(gòu)：最有子結(jié)構(gòu)性質(zhì)； ②建立遞歸方程 ； ③計算最優(yōu)值 ； ④構(gòu)造最優(yōu)解 [4]。 由上面的動態(tài)規(guī)劃法的介紹，可以看出 01背包問題，是符合多段決策的特點和具有重疊子問題。 01 背包問題的實現(xiàn) ① 最優(yōu)子結(jié)構(gòu)性質(zhì) 01 背包問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。因此 ????ni ii zv2 v1y1 ??ni iiyv1 ??? ni iizw2w1y1 ? c 這說明 (y1， z2? zn)是所給 01 背包問題的一個更優(yōu)解，從而 (y1， y2? yn)不是所給 01 背包問題的最優(yōu)解。 ② 遞歸關(guān)系 設(shè)所給 01 背包問題的子問題 ??nik kkxvmax ??????????? nkixjxwknikkk},1,0{ 的最優(yōu)值為 m(i,j)，即 m(i,j)是背包容量為 j，可選擇物品為 i， i+1， ?? ，n時 01 背包問題的最優(yōu)值。 for (int j=0。j++)m[n][j]=0。j=c。 for (int i=n1。i){ jMax=min(w[i]1,c)。j=jMax。 for(intj=w[i]。j++)m[i][j]=max(m[i+1][j],m[i+1][jw[i]]+v[i])。 if(c=w[1]) m[1][c]=max(m[1][c],m[2][cw[1]]+v[1])。i=n。 else {x[i] =1。} x[n]=(m[n][c])?1:0。動態(tài)規(guī)劃主要是求解最優(yōu)決策序列，當(dāng)最優(yōu)決策序列中包含最優(yōu)決策子序列時，可建立動態(tài)規(guī)劃遞歸方程，它可以幫助高效地解決問題 [8]。 為了實現(xiàn)回溯，首先需要為問題定義一個解空間，這個解空間必須至少包含問題的一個解 (可能是最優(yōu)的 )。 使用遞 歸回溯法解決背包問題的優(yōu)點在于它算法思想簡單，而且它能完全 遍歷搜索空間，肯定能找到問題的最優(yōu)解奉但是由于此問題解的總組合數(shù)有 n2 個，因此隨著物件數(shù) n 的增大， 其解的空間將以 n n2 級增長，當(dāng) n大到一定程度上，用此算法解決背包問題將是不現(xiàn)實的。典型的組織方法是圖或樹 。 01 背包問題的實現(xiàn) ① 回溯法的 算法描述 回溯法是一種系統(tǒng)地搜索問題解答的方法。一旦定義了解空間的組織方 要選擇一個對象的子集，將它們裝人背包，以便獲得的收益最大，則解空間應(yīng)組織成子集樹的形狀。然后，對該算法加以改進(jìn)，形成代碼。 左 子樹 表示一個可行的結(jié)點，無論何時都要移動到它，當(dāng)右子樹可能含有比當(dāng)前最優(yōu)解還優(yōu)的解時，移動到它。一種更有效的方法是按收益密度 vi/wi 對剩余對象排序，將對象按密度遞減的順序去填充背包的剩余容量， 當(dāng)遇到第一個不能全部放人背包的對象時， 就使用它的一部分 。 private： Typep Bound(int i)。 Typew c。 //物品數(shù) Typew*w。 //物品價值 數(shù)組 Typew cw。 //當(dāng)前價值 Typep bestp。 templateclass Typew,class Typep void knapTypew,Typep::Backtrack(int i) { if(in){//到達(dá)葉結(jié)點 bestp=cp。} if(cw+w[i]=c){//進(jìn)入左子數(shù) cw+=w[i]。 Backtrack(i+1)。 cp=p[i]。 10 } templateclass Typew,class Typep Typep KnapTypew,Typep::Bound(int i) {//計算上界 Typew cleft=ccw。 //以物品單位重量價值遞減序裝入物品 while (i=namp。w[i]=cleft){ cleft=w[i]。 i++。 return b。 public。} private: int ID。 }。 Typep P=0。 11 for(int i=1。i++){ Q[i1].ID=i。 p+=p[i]。 } if(w=c)return P。 KnapTypew,TypepK。 =new Typew[n+1]。i=n。 [i]=w[Q[i1].ID]。 =0。 =n。 //回搠搜索 (1)。 delete[]。 reture K,bestp。 12 對回溯法的改進(jìn)主要是對判斷是否移動右子樹上，一種更有效的方法是按效益密度 vi/wi 對剩余對象排序，將對象按密度遞減的順序去填充背包的 剩余容量，當(dāng)遇到第一個不能全部放人背包的對象時，就使用它的一部分。 回溯法的另一個 重要特性就是在搜索執(zhí)行的同時產(chǎn)生解空間 在搜索期間的任何時刻 僅保留從開始結(jié)點到當(dāng)前可擴展結(jié)點的路徑其空間需求為 O(從開始結(jié)點起最長路徑的長度 ),所以 ,此處該算法的空間復(fù)雜度為 O(n),回溯法是算法設(shè)計的基本方法之一 ,它適用于解一些涉及到尋找一組解的問題或者求滿足某些約束條件的最優(yōu)解的問題 ,且適用于求解組合數(shù)量較大的問題 。每個活結(jié)點有且僅有一次會變成 E結(jié)點。在生成的結(jié)點中，拋棄那些不可能導(dǎo)出 (最優(yōu) )可行解的結(jié)點，其余結(jié)點加人活結(jié)點表，然后從表中選擇一個結(jié)點作為下一個 E 結(jié)點。 有兩種常用的方法可用來選擇下一個 E結(jié)點 : ① 先進(jìn)先出 (FIFO)即從活結(jié)點表中取出結(jié)點的順序與加人結(jié)點的順序相同，因此活結(jié)點表的性質(zhì)與隊列相同。如果查找一個具有最小耗費的解，則活結(jié)點表可以最小堆來建立，下一個E結(jié)點就是具有最小耗費的活結(jié)點，如果希望搜索一個具有最大收益的解， 則可用最大堆來構(gòu)造活結(jié)點表，下一個 E結(jié)點是具有最大收益的活結(jié)點 [15]。它們的主要區(qū)別時在 FIFO 分枝定界中不可行的結(jié)點不會被搜索。在子集樹中執(zhí)行最大收益分枝定界搜索的函數(shù)首先初始化活結(jié)點的最大堆，并使用一個數(shù)組bestx來記錄最優(yōu)解。函數(shù)中的循環(huán)首先檢 驗 E結(jié)點左孩子的可行性，如它是可行的，則將它加 入 子集樹及活結(jié)點隊列 (即最大堆 )， 僅當(dāng)結(jié)點右 子樹 的定界值指明可能找到一 個最優(yōu)解時才將右孩子加 入 子集樹和隊列中。 public: int operator=(Object a) const {r