[理學(xué)]背包問(wèn)題詳解-文庫(kù)吧
2025-09-20 01:09 本頁(yè)面
【正文】 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 9 9 9 11 11 14 w4=5 v4=4 4 0 0 6 6 9 9 9 10 11 13 14 w5=4 v5=6 5 0 0 6 6 9 9 12 12 15 15 15 0 第一階段，只裝入前 1個(gè)物品，確定在 各種情況下 的背包能夠得到的最大價(jià)值； 第二階段，只裝入前 2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值； 依此類推，直到第 n個(gè)階段。最后， V(n,C)便是在容量為 C的背包中裝入 n個(gè)物品 時(shí)取得的最大價(jià)值。 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 9 9 9 11 11 14 w4=5 v4=4 4 0 0 6 6 9 9 9 10 11 13 14 w5=4 v5=6 5 0 0 6 6 9 9 12 12 15 15 15 0 12 ? void Traceback(int **m, int w[ ], int c, int n, int x[ ]) ? {// 計(jì)算 x ? for (int i=1。 in。 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。 ? } 01背包問(wèn)題 — 動(dòng)態(tài)規(guī)劃算法 13 算法改進(jìn) 由 m(i,j)的遞歸式容易證明，在一般情況下，對(duì)每一個(gè)確定的i(1≤i≤n)，函數(shù) m(i,j)是關(guān)于變量 j的階梯狀單調(diào)不減函數(shù)。跳躍點(diǎn)是這一類函數(shù)的描述特征。在一般情況下，函數(shù) m(i,j)由其全部跳躍點(diǎn)唯一確定。如圖所示。 對(duì)每一個(gè)確定的 i(1≤i≤n)，用一個(gè)表 p[i]存儲(chǔ)函數(shù) m(i， j)的全部跳躍點(diǎn)。表 p[i]可依計(jì)算 m(i， j)的遞歸式遞歸地由表 p[i+1]計(jì)算，初始時(shí) p[n+1]={(0， 0)}。 14 一個(gè)例子 n=3， c=6， w={4， 3， 2}， v={5， 2， 1}。 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)算得到的。因此，函數(shù) m(i,j)的全部跳躍點(diǎn)包含于函數(shù) m(i+1，j)的跳躍點(diǎn)集 p[i+1]與函數(shù) m(i+1， jwi)+vi的跳躍點(diǎn)集 q[i+1]的并集中。易知， (s,t)?q[i+1]當(dāng)且僅當(dāng) wi?s?c且 (swi,tvi)?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個(gè)跳躍點(diǎn)，則當(dāng) c?a且 db時(shí)， (c， d)受控于 (a， b)，從而 (c， d)不是p[i]中的跳躍點(diǎn)。除受控跳躍點(diǎn)外， p[i+1]?q[i+1]中的其它跳躍點(diǎn)均為 p[i]中的跳躍點(diǎn)。 ? 由此可見(jiàn)，在遞歸地由表 p[i+1]計(jì)算表 p[i]時(shí)，可先由 p[i+1]計(jì)算出 q[i+1]，然后合并表 p[i+1]和表 q[i+1]，并清除其中的受控跳躍點(diǎn)得到表 p[i]。 算法改進(jìn) 16 一個(gè)例子 n=5， c=10， w={2， 2， 6， 5， 4}， v={6， 3， 5， 4， 6}。 初始時(shí) 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)，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1