[理學(xué)]背包問題詳解-預(yù)覽頁
【正文】 1≤i≤n ? 可用動(dòng)態(tài)規(guī)劃算法求解。 ? 多重背包問題 ? 有 N種物品和一個(gè)容量為 V的背包。由 01背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算 m(i， j)的遞歸式如下。 7 0/1背包問題可以看作是決策一個(gè)序列 (x1, x2, …, xn)，對任一變量 xi的決策是決定 xi=1還是 xi=0。 int jMax。 j = jMax 。 j++) m[n][j] = v[n] 。 ? if(w[n]1c) jMax=c。 j++) ? m[i][j] = m[i+1][j]。 ? else m[i][j]=m[i+1][jw[i]] + v[i] 。 例如，有 5個(gè)物品，其重量分別是 {2, 2, 6, 5, 4}，價(jià)值分別為 {6, 3, 5, 4, 6}，背包的容量為 10。 in。 ? } ? x[n]=(m[n][c])?1:0。如圖所示。 x (0,0) m(4,x) x (2,1) m(4,x2)+1 x (0,0) (2,1) m(3,x) (3,2) x m(3,x3)+2 (5,3) x (0,0) (2,1) m(2,x) (3,2) (5,3) x m(2,x4)+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) 15 ? 函數(shù) m(i,j)是由函數(shù) m(i+1,j)與函數(shù) m(i+1,jwi)+vi作 max運(yùn)算得到的。除受控跳躍點(diǎn)外， p[i+1]?q[i+1]中的其它跳躍點(diǎn)均為 p[i]中的跳躍點(diǎn)。因此，q[6]=p[6]?(w5,v5)={(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]的最后的那個(gè)跳躍點(diǎn) (8,15)給出所求的最優(yōu)值為 m(1,c)=15。從跳躍點(diǎn)集 p[i]的定義可以看出， p[i]中的跳躍點(diǎn)相應(yīng)于 xi,…,x n的 0/1賦值。在這種情況下，改進(jìn)后算法的計(jì)算時(shí)間復(fù)雜性為 O(min{nc,2n})。 19 貪心算法的基本要素 貪心選擇性質(zhì) 所謂 貪心選擇性質(zhì) 是指所求問題的 整體最優(yōu)解 可以通過一系列 局部最優(yōu) 的選擇，即貪心選擇來達(dá)到。 20 貪心算法的基本要素 當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 貪心算法與動(dòng)態(tài)規(guī)劃算法的差異 22 背包問題 — 貪心算法 ? 01背包問題： 給定 n種物品和一個(gè)背包。 23 背包問題 — 貪心算法 ? 背包問題： 與 01背包問題類似，所不同的是在選擇物品 i裝入背包時(shí)，可以選擇物品 i的一部分，而不一定要全部裝入背包， 1≤i≤n 。依此策略一直地進(jìn)行下去，直到背包裝滿為止。i=n。i=n。 ? } ? if (i=n) x[i]=c/w[i]。 26 ? 對于 01背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。 ? 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解 01背包問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。 01背包問題 — 回溯法 29 問題的解空間 ?問題的解向量：回溯法希望一個(gè)問題的解能夠表示成一個(gè) n元式 (x1,x2,… ,xn)的形式。 注意：同一個(gè)問題可以有多種表示，有些表示方法更簡單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡單）。 例如，對于 01背包問題的一個(gè)實(shí)例， n=4,c=7, p=[9,10,7,4]，w=[3,5,2,1]。由此得到一個(gè)解為x=[1,1,1]，其相應(yīng)的價(jià)值為 22。它是類 Knap的私有成員。 ? 在調(diào)用函數(shù) Knapsack之前，需先將各物品依其單位重量價(jià)值從大到小排序。 33 01背包問題 — 回溯法 templateclass Typew, class Typep class Knap { friend Typep Knapsack(Typep *,Typew*, Typew ,int )。//背包容量 int n。//當(dāng)前重量 Typep cp。//當(dāng)前解 }。 bestp=cp。 cp+=p[i]。 } if(Bound(i+1)bestp)//搜索右子樹 {x[i]=0。 // 以物品單位重量價(jià)值遞減序裝入物品 while (i = n amp。 i++。 public: int operator=(Object a)const { return (d=)。 37 templateclass Typew, class Typep int Knapsack(Typep p[], Typew w[], Typew c,int n) {//為 Knap::Backtrack初始化 Typew W=0。 for(i=1。 P+=p[i]。 for( i=0。j++) { if(Q[i].dQ[j].d) { f=Q[i].d。 = new int[n+1]。 [0]=0。i++) { [i]=p[Q[i1].ID]。 =c。 ()。 return 。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。 （ 1） 隊(duì)列式 (FIFO)分支限界法（子集樹） （ 2）優(yōu)先隊(duì)列式分支限界法（排列樹） 極大堆來表示活結(jié)點(diǎn)表的優(yōu)先隊(duì)列。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。amp。 } if (i = n) b += p[i] / w[i] * cleft。 AddLiveNode(up, cp+p[i], cw+w[i], true, i+1)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1