【正文】 // 取下一個擴展節(jié)點 （ 略 ） } 分支限界搜索過程 。} up = Bound(i+1)。 if (wt = c) {// 左兒子結(jié)點為可行結(jié)點 if (cp+p[i] bestp) bestp = cp+p[i]。 // 裝填剩余容量裝滿背包 return b。 //p[i]表示 i的價值 i++。 w[i] = cleft) // n表示物品總數(shù) ， cleft為剩余空間 { cleft = w[i]。 43 01背包問題 — 分支限界法 上界函數(shù) while (i = n amp。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當右兒子結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。 算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。 01背包問題 — 分支限界法 42 01背包問題 — 分支限界法 算法的思想 首先，要對輸入數(shù)據(jù)進行預(yù)處理，將各物品依其單位重量價值從大到小進行排列。 41 n=3時的 01背包問題，用完全二叉樹表示的解空間 ,實例如下： w=[16,15,15],p=[45,25,25],c=30。 40 01背包問題 — 分支限界法 常見的兩種分支限界法 （ 1）隊列式 (FIFO)分支限界法 按照隊列先進先出（ FIFO） 原則選取下一個節(jié)點為擴展節(jié)點。活結(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。 39 分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。 } 38 01背包問題 — 分支限界法 分支限界法與回溯法 （ 1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 delete [] 。 delete [] Q。 //回溯搜索 (1)。 =n。 =0。 [i]=w[Q[i1].ID]。i=n。 [0]=0。 = new int[n+1]。 = new int[n+1]。} } Knap K。Q[i].d=Q[j].d。jn。in。//裝入所有物品 //依物品單位重量排序 Sort(Q,n) float f。 W+=w[i]。 Q[i1].d=*p[i]/w[i]。i=n。 Object *Q=new Object[n]。 Typep P=0。 }。 } private: int ID。 } 36 01背包問題 — 回溯法 templateclass Typew, class Typep class Object { friend int Knapsack(int *,int *,int ,int )。 } // 裝滿背包 if (i = n) b += p[i]/w[i] * cleft。 b += p[i]。amp。 // 剩余容量 Typep b = cp。 Backtrack(i+1)。 cp=p[i]。 Backtrack(i+1)。 cw+=w[i]。} return。j++) bestx[j]=x[j]。 34 01背包問題 — 回溯法 templateclass Typew, class Typep void Knap Typew,Typep::Backtrack(int i) { if(in) { if(bestpcp){ for(int j=1。//當前最優(yōu)解 Typep *x。//當前價值 Typep bestp。//物品價值數(shù)組 Typew cw。 //物品數(shù) Typew *w。 Typew c。 private: Typep Bound(int i)。在通常情況下，排序算法將待排序元素從小到大排列。為此目的，我們定義了類 Object。進人左子樹時不需計算上界，因為其上界與其父結(jié)點的上界相同。 Knap的其他成員記錄解空間樹中的結(jié)點信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時所需的?？臻g。 32 01背包問題 — 回溯法 ? 在實現(xiàn)時，由函數(shù) Bound來計算在當前結(jié)點處的上界。盡管這個解不是一個可行解，但可以證明其價值是最優(yōu)值的一個上界。首先裝入物品 4，然后裝人物品 3和 10裝人這 3個物品后，剩余的背包容量為 1，只能裝人 2。這 4個物品的單位重量價值分別為「 3,2,4]。否則將右子樹剪去。 n=3時的 01背包問題用完全二叉樹表示的解空間 30 01背包問題 — 回溯法 ? n=3, C=30, w={16, 15, 15}, v={45, 25, 25} ? 開始時， Cr=C=30， V=0， A為唯一活結(jié)點，也是當前擴展結(jié)點 ? 擴展 A，先到達 B結(jié)點 ? Cr=Crw1=14， V=V+v1=45 ? 此時 A、 B為活結(jié)點， B成為當前擴展結(jié)點 ? 擴展 B，先到達 D ? Crw2， D導(dǎo)致一個不可行解，回溯到 B ? 再擴展 B到達 E ? E可行，此時 A、 B、 E是活結(jié)點， E成為新的擴展結(jié)點 ? 擴展 E，先到達 J ? Crw3， J導(dǎo)致一個不可行解，回溯到 E ? 再次擴展 E到達 K ? 由于 K是葉結(jié)點，即得到一個可行解 x=(1,0,0)， V=45 ? K不可擴展，成為死結(jié)點，返回到 E ? E沒有可擴展結(jié)點，成為死結(jié)點，返回到 B ? B沒有可擴展結(jié)點，成為死結(jié)點，返回到 A ? A再次成為擴展結(jié)點，擴展 A到達 C ? Cr=30， V=0，活結(jié)點為 A、 C， C為當前擴展結(jié)點 ? 擴展 C，先到達 F ? Cr=Crw2=15， V=V+v2=25，此時活結(jié)點為 A、 C、 F， F成為當前擴展結(jié)點 ? 擴展 F，先到達 L ? Cr=Crw3=0， V=V+v3=50 ? L是葉結(jié)點，且 5045，皆得到一個可行解 x=(0,1,1)， V=50 ? L不可擴展，成為死結(jié)點，返回到 F ? 再擴展 F到達 M ? M是葉結(jié)點，且 2550，不是最優(yōu)解 ? M不可擴展，成為死結(jié)點，返回到 F ? F沒有可擴展結(jié)點，成為死結(jié)點，返回到 C ? 再擴展 C到達 G ? Cr=30， V=0，活結(jié)點為 A、 C、 G， G為當前擴展結(jié)點 ? 擴展 G，先到達 N， N是葉結(jié)點，且 2550，不是最優(yōu)解，又 N不可擴展，返回到 G ? 再擴展 G到達 O， O是葉結(jié)點，且 050，不是最優(yōu)解，又 O不可擴展，返回到 G ? G沒有可擴展結(jié)點，成為死結(jié)點，返回到 C ? C沒有可擴展結(jié)點，成為死結(jié)