【正文】 cw + w[i]。 //w[i]表示 i所占空間 b += p[i]。 在分支限界法中，每一個活結(jié)點(diǎn)只有一次機(jī)會成為擴(kuò)展結(jié)點(diǎn)。 } =0。i++) for(int j=i。 float d。 cw=w[i]。//物品重量數(shù)組 Typep *p。因此，對于這個實(shí)例，最優(yōu)值不超過 22。算法搜索至解空間樹的任意一點(diǎn)時，先判斷該結(jié)點(diǎn)是否包含問題的解。因此，算法的計(jì)算時間上界為 O（ nlogn）。 24 背包問題 — 貪心算法 首先計(jì)算每種物品單位重量的價(jià)值 Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價(jià)值最高的物品裝入背包。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢 ?這個問題很難給予肯定的回答。 算法改進(jìn) 16 一個例子 n=5， c=10， w={2， 2， 6， 5， 4}， v={6， 3， 5， 4， 6}。 ? else ? { ? x[i]=1。 ? for (j = 0。 這兩種情況下背包價(jià)值的最大者應(yīng)該是 對 xi決策后 的背包價(jià)值 。因此，該問題稱為 01背包問題。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量，且價(jià)值總和最大。 ? for (j = 0。 j++) ? if(m[i+1][j] m[i+1][jw[i]] + v[i] ) m[i][j]=m[i+1][j]。在一般情況下，函數(shù) m(i,j)由其全部跳躍點(diǎ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)。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。 ? for (i=1。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 ?解空間：對于問題的一個實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個解空間。進(jìn)人左子樹時不需計(jì)算上界，因?yàn)槠渖辖缗c其父結(jié)點(diǎn)的上界相同。//當(dāng)前最優(yōu)解 Typep *x。 // 剩余容量 Typep b = cp。 Object *Q=new Object[n]。} } Knap K。 //回溯搜索 (1)。 41 n=3時的 01背包問題，用完全二叉樹表示的解空間 ,實(shí)例如下： w=[16,15,15],p=[45,25,25],c=30。 if (wt = c) {// 左兒子結(jié)點(diǎn)為可行結(jié)點(diǎn) if (cp+p[i] bestp) bestp = cp+p[i]。 w[i] = cleft) // n表示物品總數(shù) ， cleft為剩余空間 { cleft = w[i]。這個過程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時為止。 [i]=w[Q[i1].ID]。in。 } private: int ID。 Backtrack(i+1)。 //物品數(shù) Typew *w。盡管這個解不是一個可行解，但可以證明其價(jià)值是最優(yōu)值的一個上界。 ? 回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。 ? } 算法 knapsack的主要計(jì)算時間在于將各種物品依其單位重量的價(jià)值從大到小排序。 這 2類問題都具有 最優(yōu)子結(jié)構(gòu) 性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而 01背包問題卻不能用貪心算法求解。 算法復(fù)雜度分析 ? ?nniinniOOipO 22|]1[|22?????????????? ? ?????18 背包問題 — 貪心算法 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 ? 由此可見，在遞歸地由表 p[i+1]計(jì)算表 p[i]時，可先由 p[i+1]計(jì)算出 q[i+1]，然后合并表 p[i+1]和表 q[i+1]，并清除其中的受控跳躍點(diǎn)得到表 p[i]。 i++) ? if (m[i][c]==m[i+1][c]) ? x[i]=0。 else jMax=w[n]1。在對 xi1決策后，已確定了(x1, …, xi1)，在決策 xi時，問題處于下列兩種狀態(tài)之一： （ 1） 背包容量不足以裝入物品 i， 則 xi=0， 背包不增加價(jià)值； （ 2） 背包容量可以裝入物品 i， 則 xi=1， 背包的價(jià)值增加了 vi。不能將物品 i裝入背包多次，也不能只裝入部分的物品 i。 ? 多重背包問題 ? 有 N種物品和一個容量為 V的背包。 j = jMax 。 ? else m[i][j]=m[i+1][jw[i]] + v[i] 。如圖所示。將受控跳躍點(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。 20 貪心算法的基本要素 當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。i=n。 ? 實(shí)際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解 01背包問題。 注意：同一個問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更小（存儲量少，搜索方法簡單）。 ? 在調(diào)用函數(shù) Knapsack之前，需先將各物品依其單位重量價(jià)值從大到小排序。//當(dāng)前解 }。 // 以物品單位重量價(jià)值遞減序裝入物品 while (i = n amp。 for(i=1。 = new int[n+1]。 ()。 （ 1） 隊(duì)列式 (FIFO)分支限界法（子集樹） （ 2）優(yōu)先隊(duì)列式分支限界法（排列樹） 極大堆來表示活結(jié)點(diǎn)表的優(yōu)先隊(duì)列。 AddLiveNode(up, cp+p[i], cw+w[i], true, i+1)。amp。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。i++) { [i]=p[Q[i1].ID]。 for( i=0。 public: int operator=(Object a)const { return (d=