【正文】 狀態(tài)轉(zhuǎn)移規(guī)律 。 第四步 把自己的求解放到一邊，看書中的求解方法，要充分理解教材中的論述。由于這是一個(gè)離散的函數(shù)，取值用列表表示： f 4 (x 4 ) 的表達(dá)式 x 4 f 4 (x 4 ) 最優(yōu)決策 d 4 * D 1 5 D 1 ? E D 2 2 D 2 ? E 求 最 短 路 徑 16 第三階段的遞推方程為： 從 f 4 (x 4 ) 到 f 3 (x 3 ) 的遞推過程用表格表示如下： x 3 D 3 (x 3 ) x 4 v 3 (x 3 ,d 3) v 3 (x 3 ,d 3 )+f 4 (x4 ) f 3 (x 3) 最優(yōu)決策 d 3 * C 1 C 1 ? D 1 C 1 ? D 2 D 1 D 2 3 9 3+5=8* 9+2=11 8 C 1 ? D 1 C 2 C 2 ? D 1 C 2 ? D 2 D 1 D 2 6 5 6+5=11 5+2=7* 7 C 2 ? D 2 C 3 C 3 ? D 1 C 3 ? D 2 D 1 D 2 8 10 8+5=13 10+2=12* 12 C 3 ? D 2 )}(),({m in)( 44333)(33 333xfdxvxfxDd??? 求 最 短 路 徑 17 由此得到 f3(x3)的表達(dá)式： x 3 f 3 ( x 3 ) 最優(yōu)決策 d 3 * C 1 8 C 1 ? D 1 C 2 7 C 2 ? D 2 C 3 12 C 3 ? D 2 第二階段的遞推方程為： )}(),({min)( 33222)(22 222xfdxvxfxDd???從 f 3 ( x 3 ) 到 f 2 ( x 2 ) 的遞推過程用表格表示如下： 求 最 短 路 徑 18 x 2 D 2 (x 2 ) x 3 v 2 (x 2 ,d 2 ) v 2 (x 2 ,d 2 )+f 3 (x 3 ) f 2 (x 2 ) 最優(yōu)決策 d 2 * B1 B1? C1 B1? C2 B1? C3 C1 C2 C3 12 14 10 12+8=20* 14+7=21 10+12=22 20 B1? C1 B2 B2? C1 B2? C2 B2? C3 C1 C2 C3 6 10 4 6+8=14* 10+7=17 4+12=16 14 B2? C1 B3 B3? C1 B3? C2 B3? C3 C1 C2 C3 13 12 11 13+8= 21 12+7=19* 11+12=23 19 B3? C2 求 最 短 路 徑 19 由此得到 f2(x2)的表達(dá)式： x 2 f 2 (x 2 ) 最優(yōu)決策 d 2 * B 1 20 B 1 ? C 1 B 2 14 B 2 ? C 1 B 3 19 B 3 ? C 2 求 最 短 路 徑 20 第一階段的遞推方程為： )}(),({m in)( 22111)(11 111xfdxvxfxDd??? 從 f 2 ( x 2 ) 到 f 1 ( x 1 ) 的遞推過程用表格表示如下： x 1 D 1 (x 1 ) x 2 v 1 (x 1 ,d 1 ) v 1 (x 1 ,d 1 )+f 2 (x 2 ) f 1 (x 1 ) 最優(yōu)決策 d 1 * A A ? B 1 A ? B 2 A ? B 3 B 1 B 2 B 3 2 5 1 2+20=22 5+14=19* 1+19=20 19 A ? B 2 求 最 短 路 徑 21 由此得到 f1(x1)的表達(dá)式 x 1 f 1 (x 1 ) 最優(yōu)決策 d 1 * A 19 A ? B 2 從表達(dá)式 f 1 ( x 1 ) 可以看出，從 A 到 E 的最短路徑長度為 19 。 設(shè)第 i種物品取 x i 件（ i =1,2, … , n ， x i 為非負(fù)整數(shù) ） ，背包中物品的價(jià)值為 z ， 則 背 包 問 題 30 則 Max z= c1x1+c2x2+… +xn . w1x1+w2x2+… +wnxn≤ W x1,x2,…,x n為正整數(shù) 1. 階段 k：第 k次裝載第 k種物品（ k=1,2,… ,n） 2. 狀態(tài)變量 xk：第 k次裝載時(shí)背包還可以裝載的重量； 3. 決策變量 dk：第 k次裝載第 k種物品的件數(shù)； 背 包 問 題 31 4. 決策允許集合： Dk(xk)={dk|0? dk?xk/wk， dk為整數(shù) }； 5. 狀態(tài)轉(zhuǎn)移方程： xk+1=xkwkdk 6. 階段指標(biāo)： vk=ckdk 7. 遞推方程 fk(xk)=max{ckdk+fk+1(xk+1)} =max{ckdk+fk+1(xkwkdk)} 8. 終端條件： fn+1(xn+1)=0 背 包 問 題 32 例 :對(duì)于一個(gè)具體問題 c1=65，c2=80， c3=30； w1=2， w2=3， w3=1；以及 W=5 用動(dòng)態(tài)規(guī)劃求解 f4(x4)=0 對(duì)于 k=3 }30{max)}({max)(3/04433/033333333dxfdcxfwxdwxd???????列出 f 3 ( x 3 ) 的數(shù)值表 背 包 問 題 33 x 3 D 3 ( x 3 ) x 4 30 d 3 + f 4 ( x 4 ) f 3 ( x 3 ) d 3 * 0 0 0 0 + 0 = 0 0 0 1 1 0 3 0 + 0 = 3 0 * 30 1 2 2 0 6 0 + 0 = 6 0 * 60 2 3 3 0 9 0 + 0 = 9 0 * 90 3 5 5 0 1 5 0 + 0 = 1 5 0 * 150 5 }30{max)}({max)(3/04433/033333333dxfdcxfwxdwxd???????對(duì)于 k =3 列出 f3(x3)的數(shù)值表如下： 34 x 2 D 2 ( x 2 ) x 3 80 d 2 + f 3 ( x 3 ) f 2 ( x 2 ) d 2 * 1 0 1 0+ f 3 (1 )= 0 + 3 0 = 3 0 * 30 0 3 0 1 3 0 0+ f 3 (3 )= 0 + 9 0 = 9 0 * 80+ f 3 (0 )= 8 0 + 0 = 8 0 90 0 5 0 1 5 2 0+ f 3 (5 )= 0 + 1 5 0 = 1 5 0 * 80+ f 3 (2 )= 8 0 + 6 0 = 1 4 0 150 0 對(duì)于 k=2 )}3(80{max)}({max)(22323/03322/02222222dxfdxfdcxfxdwxd?????????列出 f2(x2)的數(shù)值表 35 x 1 D 1 ( x 1 ) x 2 65 d 1 + f 2 ( x 2 ) f 1 ( x 1 ) d 1 * 5 0 1 2 5 3 1 0+ f 2 (5 )= 0 + 1 5 0 = 1 5 0 65+ f 2 (3 )= 6 5 + 9 0 = 1 5 5 130+ f 2 (1 )= 1 3 0 + 3 0 = 1 6 0 * 160 2 對(duì)于 k=1 )}2(65{max)}({max)(11212/02211/01111111dxfdxfdcxfxdwxd?????????列出 f1(x1)的數(shù)值表 36 由題意知， x1=5 ，由表 f1( x1) 、 f2( x2) 、f3( x3) ，經(jīng)回朔可得： d1* = 2 ， x2= x1 2 d1=1 ， d2* = 0 ， x3= x2 3 d2=1 ，d3*=1 ， x4= x3 d3=0 即應(yīng)取第一種物品 2 件 , 第三種物品 1 件 , 最高價(jià)值為 1 6 0 元 , 背包沒有余量。