包裝物流系統(tǒng)優(yōu)化方法-資料下載頁(yè)
2024-12-31 23:15本頁(yè)面
【正文】 xwiniii???niii xv1zm ax問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件 ， 并使目標(biāo)函數(shù)達(dá)到最大的解向量X=(x1, x2, … , xn)。 首先證明 0/1背包問(wèn)題滿足最優(yōu)性原理 。 設(shè) (x1, x2, … , xn)是所給 0/1背包問(wèn)題的一個(gè)最優(yōu)解 ， 則 ( x2, … , xn)是下面一個(gè)子問(wèn)題的最優(yōu)解： ????????????)2(}1,0{112nixxwCxwiniii如若不然，設(shè) (y2, …, yn)是上述子問(wèn)題的一個(gè)最優(yōu)解，則 ， 且 。同時(shí)， ， 這說(shuō)明 (x1, y2, …, yn)是所給 0/1背包問(wèn)題比 (x1, x2, …, xn)更優(yōu)的解，從而導(dǎo)致矛盾。 ?????niiiniii xvyv22Cywxwniii ?? ?? 211 ??????????niiiniiiniii xvxvxvyvxv1211211 0/1背包問(wèn)題可以看作是決策一個(gè)序列 (x1, x2, …, x n)，對(duì)任一變量 xi的決策是決定 xi=1還是 xi=0。在對(duì) xi1決策后，已確定了 (x1, …, xi1)，在決策 xi時(shí)，問(wèn)題處于下列兩種狀態(tài)之一： i，則 xi=0，背包不增加價(jià)值； i，則 xi=1，背包的價(jià)值增加了 vi。 這兩種情況下背包價(jià)值的最大者應(yīng)該是對(duì) xi決策后的背包價(jià)值。令 V(i, j)表示在前 i(1≤ i≤ n)個(gè)物品中能夠裝入容量為 j（ 0≤ j≤ C）的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)規(guī)劃函數(shù)： V(i, 0)= V(0, j)=0 （ 1） 表明：把前面 i個(gè)物品裝入容量為 0的背包和把 0個(gè)物品裝入容量為 j的背包，得到的價(jià)值均為 0。 ）（ 2 }),1(),1( m ax{),1(),(???????????iiiiwjvwjiVjiVwjjiVjiV第一個(gè)式子表明：如果第 i個(gè)物品的重量大于背包的容量，則裝入前 i個(gè)物品得到的最大價(jià)值和裝入前 i1個(gè)物品得到的最大價(jià)值是相同的，即物品 i不能裝入背包；第二個(gè)式子表明：如果第 i個(gè)物品的重量小于背包的容量，則會(huì)有以下兩種情況：（ 1）如果把第 i個(gè)物品裝入背包，則背包中物品的價(jià)值等于把前 i1個(gè)物品裝入容量為 jwi的背包中的價(jià)值加上第 i個(gè)物品的價(jià)值 vi；（ 2）如果第 i個(gè)物品沒(méi)有裝入背包，則背包中物品的價(jià)值就等于把前 i1個(gè)物品裝入容量為 j的背包中所取得的價(jià)值。顯然，取二者中價(jià)值較大者作為把前 i個(gè)物品裝入容量為 j的背包中的最優(yōu)解。 第一階段，只裝入前 1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值； 第二階段，只裝入前 2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第 n個(gè)階段。 最后， V(n,C)便是在容量為 C的背包中裝入 n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從 V(n,C)的值向前推，如果 V(n,C)V(n1,C)，表明第 n個(gè)物品被裝入背包，前 n1個(gè)物品被裝入容量為 Cwn的背包中；否則，第 n個(gè)物品沒(méi)有被裝入背包，前 n1個(gè)物品被裝入容量為 C的背包中。依此類推，直到確定第 1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)： ??????????),1(),(,1),1(),(0jiVjiVwjjjiVjiVxii例如，有 5個(gè)物品，其重量分別是 {2, 2, 6, 5, 4}，價(jià)值分別為 {6, 3, 5, 4, 6}，背包的容量為 10，求裝入背包的物品和獲得的最大價(jià)值。 根據(jù)動(dòng)態(tài)規(guī)劃函數(shù)，用一個(gè) (n+1) (C+1)的二維表 V， V[i][j]表示把前 i個(gè)物品裝入容量為 j的背包中獲得的最大價(jià)值，把表的第 0行和第 0列初始化為 0，然后一行一行地計(jì)算 V[i][j]，如圖所示。 ）（ 2 }),1(),1( m ax{ ),1(),(???????????iiiiwjvwjiVjiVwjjiVjiV0/1背包求解 （ 填表 ） 過(guò)程 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=5 v5=6 5 0 0 6 6 9 9 9 12 15 15 15 }),1(),1( m ax{ ),1(),(???????????iiiiwjvwjiVjiVwjjiVjiV??????????),1(),(,1),1(),(0jiVjiVwjjjiVjiVxii可以看到 ， 裝入背包的物品的最大價(jià)值是 15， 裝入背包的物品為 X={1, 1, 0, 0, 1}。 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1