【正文】 ypew, class Typep Typep KnapTypew, Typep::Bound(int i) {// 計算上界 Typew cleft = c cw。 // 剩余容量 Typep b = cp。 // 以物品單位重量價值遞減序裝入物品 while (i = n amp。amp。 w[i] = cleft) { cleft = w[i]。 b += p[i]。 i++。 } // 裝滿背包 if (i = n) b += p[i]/w[i] * cleft。 return b。 } 36 01背包問題 — 回溯法 templateclass Typew, class Typep class Object { friend int Knapsack(int *,int *,int ,int )。 public: int operator=(Object a)const { return (d=)。 } private: int ID。 float d。 }。 37 templateclass Typew, class Typep int Knapsack(Typep p[], Typew w[], Typew c,int n) {//為 Knap::Backtrack初始化 Typew W=0。 Typep P=0。 int i=1。 Object *Q=new Object[n]。 for(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) float f。 for( i=0。in。i++) for(int j=i。jn。j++) { if(Q[i].dQ[j].d) { f=Q[i].d。Q[i].d=Q[j].d。 Q[j].d=f。} } Knap K。 = new int[n+1]。 = new int[n+1]。 = new int[n+1]。 = new int[n+1]。 [0]=0。 [0]=0。 for( 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 [] 。 return 。 } 38 01背包問題 — 分支限界法 分支限界法與回溯法 （ 1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。 （ 2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹 。 39 分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。 此后，從活結(jié)點表中取下一結(jié)點成為當前擴展結(jié)點，并重復上述結(jié)點擴展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點表為空時為止。 在分支限界法中，每一個活結(jié)點只有一次機會成為擴展結(jié)點?；罱Y(jié)點一旦成為擴展結(jié)點，就一次性產(chǎn)生其所有兒子結(jié)點。在這些兒子結(jié)點中，導致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點被舍棄，其余兒子結(jié)點被加入活結(jié)點表中。 40 01背包問題 — 分支限界法 常見的兩種分支限界法 （ 1）隊列式 (FIFO)分支限界法 按照隊列先進先出（ FIFO） 原則選取下一個節(jié)點為擴展節(jié)點。 （ 2）優(yōu)先隊列式分支限界法 按照優(yōu)先隊列中規(guī)定的優(yōu)先級選取優(yōu)先級最高的節(jié)點成為當前擴展節(jié)點。 41 n=3時的 01背包問題，用完全二叉樹表示的解空間 ,實例如下： w=[16,15,15],p=[45,25,25],c=30。 （ 1） 隊列式 (FIFO)分支限界法（子集樹） （ 2）優(yōu)先隊列式分支限界法（排列樹） 極大堆來表示活結(jié)點表的優(yōu)先隊列。 01背包問題 — 分支限界法 42 01背包問題 — 分支限界法 算法的思想 首先，要對輸入數(shù)據(jù)進行預處理，將各物品依其單位重量價值從大到小進行排列。 在下面描述的優(yōu)先隊列分支限界法中，節(jié)點的優(yōu)先級由已裝袋的物品價值加上剩下的最大單位重量價值的物品裝滿剩余容量的價值和。 算法首先檢查當前擴展結(jié)點的左兒子結(jié)點的可行性。如果該左兒子結(jié)點是可行結(jié)點，則將它加入到子集樹和活結(jié)點優(yōu)先隊列中。當前擴展結(jié)點的右兒子結(jié)點一定是可行結(jié)點，僅當右兒子結(jié)點滿足上界約束時才將它加入子集樹和活結(jié)點優(yōu)先隊列。當擴展到葉節(jié)點時為問題的最優(yōu)值。 43 01背包問題 — 分支限界法 上界函數(shù) while (i = n amp。amp。 w[i] = cleft) // n表示物品總數(shù) ， cleft為剩余空間 { cleft = w[i]。 //w[i]表示 i所占空間 b += p[i]。 //p[i]表示 i的價值 i++。 } if (i = n) b += p[i] / w[i] * cleft。 // 裝填剩余容量裝滿背包 return b。 //b為上界函數(shù) 44 01背包問題 — 分支限界法 while (i != n+1) {// 非葉結(jié)點 // 檢查當前擴展結(jié)點的左兒子結(jié)點 Typew wt = cw + w[i]。 if (wt = c) {// 左兒子結(jié)點為可行結(jié)點 if (cp+p[i] bestp) bestp = cp+p[i]。 AddLiveNode(up, cp+p[i], cw+w[i], true, i+1)。} up = Bound(i+1)。 // 檢查當前擴展結(jié)點的右兒子結(jié)點 if (up = bestp) // 右子樹可能含最優(yōu)解 AddLiveNode(up, cp, cw, false, i+1)。 // 取下一個擴展節(jié)點 （ 略 ） } 分支限界搜索過程