包裝物流系統(tǒng)優(yōu)化方法(參考版)
2025-01-02 23:15本頁面
【正文】 ）（ 2 }),1(),1( m ax{ ),1(),(???????????iiiiwjvwjiVjiVwjjiVjiV0/1背包求解 （ 填表 ） 過程 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}。由此，得到如下函數(shù)： ??????????),1(),(,1),1(),(0jiVjiVwjjjiVjiVxii例如，有 5個(gè)物品，其重量分別是 {2, 2, 6, 5, 4}，價(jià)值分別為 {6, 3, 5, 4, 6}，背包的容量為 10，求裝入背包的物品和獲得的最大價(jià)值。為了確定裝入背包的具體物品，從 V(n,C)的值向前推，如果 V(n,C)V(n1,C)，表明第 n個(gè)物品被裝入背包，前 n1個(gè)物品被裝入容量為 Cwn的背包中；否則，第 n個(gè)物品沒有被裝入背包，前 n1個(gè)物品被裝入容量為 C的背包中。 第一階段，只裝入前 1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值； 第二階段，只裝入前 2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第 n個(gè)階段。 ）（ 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è)物品沒有裝入背包，則背包中物品的價(jià)值就等于把前 i1個(gè)物品裝入容量為 j的背包中所取得的價(jià)值。 這兩種情況下背包價(jià)值的最大者應(yīng)該是對 xi決策后的背包價(jià)值。 ?????niiiniii xvyv22Cywxwniii ?? ?? 211 ??????????niiiniiiniii xvxvxvyvxv1211211 0/1背包問題可以看作是決策一個(gè)序列 (x1, x2, …, x n)，對任一變量 xi的決策是決定 xi=1還是 xi=0。 設(shè) (x1, x2, … , xn)是所給 0/1背包問題的一個(gè)最優(yōu)解 ， 則 ( x2, … , xn)是下面一個(gè)子問題的最優(yōu)解： ????????????)2(}1,0{112nixxwCxwiniii如若不然，設(shè) (y2, …, yn)是上述子問題的一個(gè)最優(yōu)解，則 ， 且 。 根據(jù)問題的要求 ， 有如下約束條件和目標(biāo)函數(shù)： ???????????)1(}1,0{1nixCxwiniii???niii xv1zm ax問題歸結(jié)為尋找一個(gè)滿足約束條件 ， 并使目標(biāo)函數(shù)達(dá)到最大的解向量X=(x1, x2, … , xn)。 背包問題是如何選擇裝入背包的物品 ， 使得裝入背包中物品的總價(jià)值最大 ?如果在選擇裝入背包的物品時(shí) ， 對每種物品 i只有兩種選擇：裝入背包或不裝入背包 ， 即不能將物品 i裝入背包多次 ， 也不能只裝入物品 i的一部分 ， 則稱為 0/1背包問題 。 所以問題就是求 fn(a) 其遞推關(guān)系式為： ? ?nkxayfxcyf kkkkkayxkkk????? ???2)(max)( 10 其中當(dāng) k=1 時(shí)，有： 的最大整數(shù)表示不超過其中1111111 , )(ayayayxaycyf????????????????????????????????例題：求下面背包問題的最優(yōu)解 ??????????且為整數(shù)0,55231258max321321321xxxxxxxxxZ物品 1 2 3 重量（斤） 3 2 5 使用價(jià)值 8 5 12 解： a＝ 5 ，問題是求 f3(5) ? ?3333 3 2 350 ( 5 ) m a x 12 ( 5 5 )xaxf x f x??? ? ?整 數(shù)? ?? ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1