【正文】 30， V=0，活結(jié)點(diǎn)為 A、 C， C為當(dāng)前擴(kuò)展結(jié)點(diǎn) ? 擴(kuò)展 C，先到達(dá) F ? Cr=Crw2=15， V=V+v2=25，此時(shí)活結(jié)點(diǎn)為 A、 C、 F， F成為當(dāng)前擴(kuò)展結(jié)點(diǎn) ? 擴(kuò)展 F，先到達(dá) L ? Cr=Crw3=0， V=V+v3=50 ? L是葉結(jié)點(diǎn)，且 5045，皆得到一個(gè)可行解 x=(0,1,1)， V=50 ? L不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到 F ? 再擴(kuò)展 F到達(dá) M ? M是葉結(jié)點(diǎn)，且 2550，不是最優(yōu)解 ? M不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到 F ? F沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到 C ? 再擴(kuò)展 C到達(dá) G ? Cr=30， V=0，活結(jié)點(diǎn)為 A、 C、 G， G為當(dāng)前擴(kuò)展結(jié)點(diǎn) ? 擴(kuò)展 G，先到達(dá) N， N是葉結(jié)點(diǎn)，且 2550，不是最優(yōu)解，又 N不可擴(kuò)展，返回到 G ? 再擴(kuò)展 G到達(dá) O， O是葉結(jié)點(diǎn)，且 050，不是最優(yōu)解，又 O不可擴(kuò)展，返回到 G ? G沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到 C ? C沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到 A ? A沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，算法結(jié)束，最優(yōu)解 X=(0,1,1)，最優(yōu)值 V=50 A Cr=C=30， V=0 B w1=16， v1=45 Cr=14， V=45 C Cr=30， V=0 D Crw2 不可行解 J Crw3 不可行解 K Cr=14 V=45 x=(1,0,0) H I E Cr=14 V=45 L w3=15， v3=25 Cr=0， V=50 5045 x=(0,1,1) F w2=15， v2=25 Cr=15， V=25 M 2550 不是 最優(yōu) 解 31 01背包問題 — 回溯法 ?解空間：子集樹 ?可行性約束函數(shù)： ?上界函數(shù)： 11 cxwniii ??? 0— 1背包問題是一個(gè)子集選取問題，適合于用子集樹表示 0— 1背包問題的解空間。盡管這個(gè)解不是一個(gè)可行解，但可以證明其價(jià)值是最優(yōu)值的一個(gè)上界。為此目的，我們定義了類 Object。 //物品數(shù) Typew *w。 34 01背包問題 — 回溯法 templateclass Typew, class Typep void Knap Typew,Typep::Backtrack(int i) { if(in) { if(bestpcp){ for(int j=1。 Backtrack(i+1)。amp。 } private: int ID。i=n。in。 = new int[n+1]。 [i]=w[Q[i1].ID]。 delete [] Q。這個(gè)過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。 01背包問題 — 分支限界法 42 01背包問題 — 分支限界法 算法的思想 首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)行排列。 w[i] = cleft) // n表示物品總數(shù) ， cleft為剩余空間 { cleft = w[i]。} up = Bound(i+1)。 if (wt = c) {// 左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn) if (cp+p[i] bestp) bestp = cp+p[i]。 43 01背包問題 — 分支限界法 上界函數(shù) while (i = n amp。 41 n=3時(shí)的 01背包問題，用完全二叉樹表示的解空間 ,實(shí)例如下： w=[16,15,15],p=[45,25,25],c=30。 39 分支限界法的基本思想 分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。 //回溯搜索 (1)。i=n。} } Knap K。//裝入所有物品 //依物品單位重量排序 Sort(Q,n) float f。 Object *Q=new Object[n]。 } 36 01背包問題 — 回溯法 templateclass Typew, class Typep class Object { friend int Knapsack(int *,int *,int ,int )。 // 剩余容量 Typep b = cp。 cw+=w[i]。//當(dāng)前最優(yōu)解 Typep *x。 Typew c。進(jìn)人左子樹時(shí)不需計(jì)算上界，因?yàn)槠渖辖缗c其父結(jié)點(diǎn)的上界相同。首先裝入物品 4，然后裝人物品 3和 10裝人這 3個(gè)物品后，剩余的背包容量為 1，只能裝人 2。 ?解空間：對(duì)于問題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。 ? 回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 ? c=w[i]。 ? for (i=1。不能將物品 i裝入背包多次，也不能只裝入部分的物品 i。 對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。當(dāng)所給物品的重量 wi(1≤i≤n)是整數(shù)時(shí)， |p[i]|≤c+1，(1≤i≤n)。從跳躍點(diǎn)集 p[5]與 q[5]的并集p[5]?q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳躍點(diǎn) (5,4)受控于跳躍點(diǎn) (4,6)。因此，容易由 p[i+1]確定跳躍點(diǎn)集 q[i+1]如下q[i+1]=p[i+1]?(wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))?p[i+1]} ? 另一方面，設(shè) (a， b)和 (c， d)是 p[i+1]?q[i+1]中的 2個(gè)跳躍點(diǎn)，則當(dāng) c?a且 db時(shí)， (c， d)受控于 (a， b)，從而 (c， d)不是p[i]中的跳躍點(diǎn)。在一般情況下，函數(shù) m(i,j)由其全部跳躍點(diǎn)唯一確定。 11 x5=1 x4=0 x3=0 x2=1 x1=1 0 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 0 w1=2 v1=6 1 0 0 6 6 6 6 6 6 6 6 6 w2=2 v2=3 2 0 0 6 6 9 9 9 9 9 9 9 w3=6 v3=5 3 0 0 6 6 9