理學(xué)背包問題詳解

1解空間設(shè)Xi表示第i件物品的取舍，1代表取，0代表舍，搜索的空間為n元一維數(shù)組（X1,X2,X3,……，Xn）,取值范圍為（0，0，0……，0，0），（0，0，0……，0，1），（0，0，0……，1，0），（0，0，0……，1，1），……，（1，1，1……，1，1）。2解空間圖示以3個物品為例,解(0,1,0)表示(不取物品0,取物品1,不取物品2)root01010101030-1背包問題問題陳述：給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價值最大？在選擇裝入背包的物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。因此，該問題稱為0-1背包問題。

解題思路：此問題可轉(zhuǎn)化為：給定c>0，wi>0，vi>0，1≤i≤n，要求找出一個n元0-1向量(x1，x2，…，xn)，xi∈{0，1}，1≤i≤n，使得∑wixi≤c，而且∑vixi達(dá)到最大。因此，0-1背包是一個特殊的整數(shù)規(guī)劃問題：max∑vixis.t.∑wixi≤c，

xi∈{0，1}，1≤i≤n可用動態(tài)規(guī)劃算法求解。4其他類型背包問題完全背包問題(0/1)：有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費(fèi)用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價值總和最大。多重背包問題有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費(fèi)用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價值總和最大。50-1背包問題設(shè)所給0-1背包問題的子問題的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i，j)的遞歸式如下。算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法需要O(nc)計算時間。當(dāng)背包容量c很大時，算法需要的計算時間較多。例如，當(dāng)c>2n時，算法需要Ω(n2n)計算時間。

6

0/1背包問題可以看作是決策一個序列(x1,x2,…,xn)，對任一變量xi的決策是決定xi=1還是xi=0。在對xi-1決策后，已確定了(x1,…,xi-1)，在決策xi時，問題處于下列兩種狀態(tài)之一：（1）背包容量不足以裝入物品i，則xi=0，背包不增加價值；（2）背包容量可以裝入物品i，則xi=1，背包的價值增加了vi。這兩種情況下背包價值的最大者應(yīng)該是對xi決策后的背包價值。令V(i,j)表示在前i(1≤i≤n)個物品中能夠裝入容量為j（1≤j≤C）的背包中的物品的最大值，則可以得到如下動態(tài)規(guī)劃函數(shù)：

0-1背包問題71、0-1背包問題—動態(tài)規(guī)劃算法voidKnapsack(int*v,int*w,intc,intn,int**m){intj;intjMax;if(w[n]-1>c)jMax=c;elsejMax=w[n]-1;for(j=0;j<=jMax;j++)m[n][j]=0;for(j=w[n];j<=c;j++)m[n][j]=v[n];for(inti=n-1;i>1;i--){intjMax;if(w[n]-1>c)jMax=c;elsejMax=w[n]-1;for(j=0;j<=jMax;j++)m[i][j]=m[i+1][j];for(j=w[i];j<=c;j++)if(m[i+1][j]>m[i+1][j-w[i]]+v[i])m[i][j]=m[i+1][j];elsem[i][j]=m[i+1][j-w[i]]+v[i];}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=((m[1][c]>m[2][c-w[1]]+v[1])?m[1][c]:m[2][c-w[1]]+v[1]); }8根據(jù)動態(tài)規(guī)劃函數(shù)，用一個(n+1)×(C+1)的二維表V，V[i][j]表示把前i個物品裝入容量為j的背包中獲得的最大價值。

例如，有5個物品，其重量分別是{2,2,6,5,4}，價值分別為{6,3,5,4,6}，背包的容量為10。

012345678910

0w1=2v1=61w2=2v2=32w3=6v3=53w4=5v4=44w5=4v5=651、0-1背包問題—動態(tài)規(guī)劃算法舉例9

012345678910

00000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=4v5=6500669912121515150第一階段，只裝入前1個物品，確定在各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；依此類推，直到第n個階段。最后，V(n,C)便是在容量為C的背包中裝入n個物品時取得的最大價值。10x5=1x4=0x3=0x2=1x1=1

012345678910

00000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=4v5=650066991212151515011voidTraceback(int**m,intw[],intc,intn,intx[]){//計算xfor(inti=1;i<n;i++)if(m[i][c]==m[i+1][c])x[i]=0;else { x[i]=1;c-=w[i]; }x[n]=(m[n][c])?1:0;}1、0-1背包問題—動態(tài)規(guī)劃算法12算法改進(jìn)由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1≤i≤n)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由其全部跳躍點(diǎn)唯一確定。如圖所示。對每一個確定的i(1≤i≤n)，用一個表p[i]存儲函數(shù)m(i，j)的全部跳躍點(diǎn)。表p[i]可依計算m(i，j)的遞歸式遞歸地由表p[i+1]計算，初始時p[n+1]={(0，0)}。13一個例子n=3，c=6，w={4，3，2}，v={5，2，1}。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)14函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運(yùn)算得到的。因此，函數(shù)m(i,j)的全部跳躍點(diǎn)包含于函數(shù)m(i+1，j)的跳躍點(diǎn)集p[i+1]與函數(shù)m(i+1，j-wi)+vi的跳躍點(diǎn)集q[i+1]的并集中。易知，(s,t)

q[i+1]當(dāng)且僅當(dāng)wi

s

c且(s-wi,t-vi)

p[i+1]。因此，容易由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個跳躍點(diǎn)，則當(dāng)c

a且d<b時，(c，d)受控于(a，b)，從而(c，d)不是p[i]中的跳躍點(diǎn)。除受控跳躍點(diǎn)外，p[i+1]

q[i+1]中的其它跳躍點(diǎn)均為p[i]中的跳躍點(diǎn)。由此可見，在遞歸地由表p[i+1]計算表p[i]時，可先由p[i+1]計算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點(diǎn)得到表p[i]。算法改進(jìn)15一個例子n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始時p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6]

(w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5]

(w4,v4)={(5,4),(9,10)}。從跳躍點(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)。將受控跳躍點(diǎn)(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}q[4]=p[4]

(6，5)={(6，5)，(10，11)}p[3]={(0，0)，(4，6)，(9，10)，(10，11)}q[3]=p[3]

(2，3)={(2，3)，(6，9)}p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}q[2]=p[2]

(2，6)={(2，6)，(4，9)，(6，12)，(8，15)}p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}p[1]的最后的那個跳躍點(diǎn)(8,15)給出所求的最優(yōu)值為m(1,c)=15。16上述算法的主要計算量在于計算跳躍點(diǎn)集p[i](1≤i≤n)。由于q[i+1]=p[i+1]

(wi，vi)，故計算q[i+1]需要O(|p[i+1]|)計算時間。合并p[i+1]和q[i+1]并清除受控跳躍點(diǎn)也需要O(|p[i+1]|)計算時間。從跳躍點(diǎn)集p[i]的定義可以看出，p[i]中的跳躍點(diǎn)相應(yīng)于xi,…,xn的0/1賦值。因此，p[i]中跳躍點(diǎn)個數(shù)不超過2n-i+1。由此可見，算法計算跳躍點(diǎn)集p[i]所花費(fèi)的計算時間為從而，改進(jìn)后算法的計算時間復(fù)雜性為O(2n)。當(dāng)所給物品的重量wi(1≤i≤n)是整數(shù)時，|p[i]|≤c+1，(1≤i≤n)。在這種情況下，改進(jìn)后算法的計算時間復(fù)雜性為O(min{nc,2n})。算法復(fù)雜度分析172、背包問題—貪心算法

本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

18貪心算法的基本要素1、貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。19貪心算法的基本要素

當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、最優(yōu)子結(jié)構(gòu)性質(zhì)202、背包問題—貪心算法

貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點(diǎn)。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。貪心算法與動態(tài)規(guī)劃算法的差異212、背包問題—貪心算法0-1背包問題：

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。222、背包問題—貪心算法背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

232、背包問題—貪心算法

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下頁：

用貪心算法解背包問題的基本步驟：242、背包問題—貪心算法voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。25對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。>>102030501.￥602.￥1003.￥1204.背包=￥220

=￥160

=￥180

=￥240100201203060101002060

10120306010100208020120

——×2030

0-1背包問題的例子2、背包問題—貪心算法262、背包問題—貪心算法

對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。27有許多問題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。3、0-1背包問題—回溯法28問題的解空間問題的解向量：回溯法希望一個問題的解能夠表示成一個n元式(x1,x2,…,xn)的形式。顯約束：對分量xi的取值限定。隱約束：為滿足問題的解而對不同分量之間施加的約束。解空間：對于問題的一個實例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實例的一個解空間。注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯α可伲阉鞣椒ê唵危?。n=3時的0-1背包問題用完全二叉樹表示的解空間293、0-1背包問題—回溯法n=3,C=30,w={16,15,15},v={45,25,25}開始時，Cr=C=30，V=0，A為唯一活結(jié)點(diǎn)，也是當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展A，先到達(dá)B結(jié)點(diǎn)Cr=Cr-w1=14，V=V+v1=45此時A、B為活結(jié)點(diǎn)，B成為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展B，先到達(dá)DCr<w2，D導(dǎo)致一個不可行解，回溯到B再擴(kuò)展B到達(dá)EE可行，此時A、B、E是活結(jié)點(diǎn)，E成為新的擴(kuò)展結(jié)點(diǎn)擴(kuò)展E，先到達(dá)JCr<w3，J導(dǎo)致一個不可行解，回溯到E再次擴(kuò)展E到達(dá)K由于K是葉結(jié)點(diǎn)，即得到一個可行解x=(1,0,0)，V=45K不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到EE沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到BB沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到AA再次成為擴(kuò)展結(jié)點(diǎn)，擴(kuò)展A到達(dá)CCr=30，V=0，活結(jié)點(diǎn)為A、C，C為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展C，先到達(dá)FCr=Cr-w2=15，V=V+v2=25，此時活結(jié)點(diǎn)為A、C、F，F(xiàn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展F，先到達(dá)LCr=Cr-w3=0，V=V+v3=50L是葉結(jié)點(diǎn)，且50>45，皆得到一個可行解x=(0,1,1)，V=50L不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到F再擴(kuò)展F到達(dá)MM是葉結(jié)點(diǎn)，且25<50，不是最優(yōu)解M不可擴(kuò)展，成為死結(jié)點(diǎn)，返回到FF沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到C再擴(kuò)展C到達(dá)GCr=30，V=0，活結(jié)點(diǎn)為A、C、G，G為當(dāng)前擴(kuò)展結(jié)點(diǎn)擴(kuò)展G，先到達(dá)N，N是葉結(jié)點(diǎn)，且25<50，不是最優(yōu)解，又N不可擴(kuò)展，返回到G再擴(kuò)展G到達(dá)O，O是葉結(jié)點(diǎn)，且0<50，不是最優(yōu)解，又O不可擴(kuò)展，返回到GG沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到CC沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，返回到AA沒有可擴(kuò)展結(jié)點(diǎn)，成為死結(jié)點(diǎn)，算法結(jié)束，最優(yōu)解X=(0,1,1)，最優(yōu)值V=50ACr=C=30，V=0Bw1=16，v1=45Cr=14，V=45CCr=30，V=0DCr<w2不可行解JCr<w3不可行解KCr=14V=45x=(1,0,0)HIECr=14V=45Lw3=15，v3=25Cr=0，V=5050>45x=(0,1,1)Fw2=15，v2=25Cr=15，V=25M25<50不是最優(yōu)解303、0-1背包問題—回溯法解空間：子集樹可行性約束函數(shù)：上界函數(shù)：

0—1背包問題是一個子集選取問題，適合于用子集樹表示0—1背包問題的解空間。在搜索解空間樹是，只要其左兒子節(jié)點(diǎn)是一個可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹，在右子樹中有可能包含最優(yōu)解是才進(jìn)入右子樹搜索。否則將右子樹剪去。例如，對于0-1背包問題的一個實例，n=4,c=7,p=[9,10,7,4]，w=[3,5,2,1]。這4個物品的單位重量價值分別為「3,2,3.5,4]。以物品單位重量價值的遞減序裝入物品。首先裝入物品4，然后裝人物品3和10裝人這3個物品后，剩余的背包容量為1，只能裝人0.2的物品2。由此得到一個解為x=[1,0.2,1,1]，其相應(yīng)的價值為22。盡管這個解不是一個可行解，但可以證明其價值是最優(yōu)值的一個上界。因此，對于這個實例，最優(yōu)值不超過22。313、0-1背包問題—回溯法在實現(xiàn)時，由函數(shù)Bound來計算在當(dāng)前結(jié)點(diǎn)處的上界。它是類Knap的私有成員。Knap的其他成員記錄解空間樹中的結(jié)點(diǎn)信息，以減少函數(shù)參數(shù)的傳遞以及遞歸調(diào)用時所需的?？臻g。在解空問樹的當(dāng)前擴(kuò)展結(jié)點(diǎn)處，僅當(dāng)要進(jìn)人右子樹時才計算L界函數(shù)Bound,以判斷是否可以將右子樹剪去。進(jìn)人左子樹時不需計算上界，因為其上界與其父結(jié)點(diǎn)的上界相同。在調(diào)用函數(shù)Knapsack之前，需先將各物品依其單位重量價值從大到小排序。為此目的，我們定義了類Object。其中，<=運(yùn)算符與通常的定義相反，其口的是為了方便調(diào)用已有的排序算法。在通常情況下，排序算法將待排序元素從小到大排列。323、0-1背包問題—回溯法template<classTypew,classTypep>classKnap{friendTypepKnapsack(Typep*,Typew*,Typew

,int);private:TypepBound(inti);voidBacktrack(inti);Typewc;//背包容量

intn;//物品數(shù)Typew

*w;//物品重量數(shù)組

Typep*p;//物品價值數(shù)組

Typewcw;//當(dāng)前重量

Typepcp;//當(dāng)前價值

Typepbestp;//當(dāng)前最優(yōu)值

Typep*bestx;//當(dāng)前最優(yōu)解

Typep*x;//當(dāng)前解};

333、0-1背包問題—回溯法template<classTypew,classTypep>voidKnap<Typew,Typep>::Backtrack(inti){if(i>n){if(bestp<cp){ for(intj=1;j<=n;j++) bestx[j]=x[j]; bestp=cp;} return;}if(cw+w[i]<=c)//搜索左子樹

{x[i]=1; cw+=w[i]; cp+=p[i]; Backtrack(i+1); cw-=w[i]; cp-=p[i];} if(Bound(i+1)>bestp)//搜索右子樹

{x[i]=0;Backtrack(i+1); }}

343、0-1背包問題—回溯法template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//計算上界

Typewcleft=c-cw;//剩余容量

Typepb=cp;//以物品單位重量價值遞減序裝入物品

while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//裝滿背包

if(i<=n)b+=p[i]/w[i]*cleft;returnb;}353、0-1背包問題—回溯法template<classTypew,classTypep>classObject{friendintKnapsack(int*,int*,int,int);public: intoperator<=(Objecta)const { return(d>=a.d); }private: intID; floatd;};

36template<classTypew,classTypep>intKnapsack(Typepp[],Typeww[],Typewc,intn){//為Knap::Backtrack初始化

TypewW=0; TypepP=0; inti=1; Object*Q=newObject[n]; for(i=1;i<=n;i++) {Q[i-1].ID=i; Q[i-1].d=1.0*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c) returnP;//裝入所有物品

//依物品單位重量排序Sort(Q,n)

floatf; for(i=0;i<n;i++) for(intj=i;j<n;j++) {if(Q[i].d<Q[j].d) {f=Q[i].d;Q[i].d=Q[j].d; Q[j].d=f;} }KnapK; K.p=newint[n+1];K.w=newint[n+1]; K.x=newint[n+1]; K.bestx=newint[n+1]; K.x[0]=0; K.bestx[0]=0; for(i=1;i<=n;i++) {K.p[i]=p[Q[i-1].ID]; K.w[i]=w[Q[i-1].ID]; } K.cp=0; K.cw=0; K.c=c; K.n=n; K.bestp=0; //回溯搜索

K.Backtrack(1);K.print();delete[]Q; delete[]K.w; delete[]K.p; returnK.bestp;}

374、0-1背包問題—分支限界法分支限界法與回溯法（1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。

（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。

38分支限界法的基本思想

分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問題的解空間樹。

此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時為止。

在分支限界法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)