例44利用向前处理法求解0/1背包问题 设g(×)是KNAP(+1,n,X)的最优解。 ●go(M):KNAP(1n,M)的最优解。 ●由于X1的取值等于1或0,可得 最优解是g0(M) go(M)=max(9, (M),g1(M-W1)+p11 ●对于某个X,x等于1或0,则有 gi (x=maxgi+ ( X), gi+, (X-Wi+1)+pi+11 初始值: 0Ⅹ≥0 gn() -X<0 2021/2/20
2021/2/20 16 例4.4 利用向前处理法求解0/1背包问题 设gi (x)是KNAP(i+1,n,X)的最优解。 ● g0 (M)：KNAP(1,n,M)的最优解。 ● 由于x1的取值等于1或0,可得： g0 (M)=max{g1 (M),g1 (M-w1)+p1 } ● 对于某个xi，xi等于1或0，则有： gi (X)=max{gi+1(X),gi+1(X-wi+1)+pi+1} 初始值： 0 X≥0 gn (X) = -∞ X＜0 最优解是g0 (M)
2)向后处理法 列出根据X1,,1的最优决策序列求取x决策值的关系式 从第一个阶段,逐步向后递推求出各阶段的决策值 2021/2/20 17
2021/2/20 17 2） 向后处理法 列出根据x1 ,…,xi-1的最优决策序列求取xi决策值的关系式。 从第一个阶段，逐步向后递推求出各阶段的决策值
例4.5k段图问题(向后处理策略) 设Vk-1∈Vk1,1sjk1pk,=pk1 vk-1,k-1 是由s到 k-1,jk-1 的最短路径,则s到t的最短路径是 Tt vkI∈∨k1sjk1spk1}中最短的那条路径。 若s, t是s到t的一条最短路径,Ⅵ是其中的 个中间点,则s,v2,v3,…,V和v1,Wk1,t分别是由s到v和到t 的最短路径(最优性原理) 从s到中的结点的最短路径将是: min >∈E, ∈V+1,1S+1Sp+ v-1,i-1 2021/2/20
2021/2/20 18 例4.5 k段图问题（向后处理策略） 设 ∈Vk-1，1≤jk-1≤pk-1，|Vk-1 |=pk-1 ; 是由s到 的最短路径，则s到t的最短路径是 { t | ∈Vk-1 ,1≤jk-1≤pk-1 }中最短的那条路径。 若s,v2 ,v3 ,…,vi ,…,vk-1 ,t是s到t的一条最短路径，vi是其中的 一个中间点，则s,v2 ,v3 ,…,vi和 vi ,…,vk-1 ,t分别是由s到vi和vi到t 的最短路径（最优性原理） 从s到Vi中的结点j i的最短路径将是： min{ |< > ∈E, ∈Vi+1,1≤ji+1≤pi+1} 1 1, − k− k j v 1 −1, − k k j v 1 1, − k− k j v 1 −1, − k k j v 1 1, − k− k j v 1 −1, − i i j v 1 1, − i− i j v i i j v , 1 1, − i− i j v i i j v
V2 4 6 6 5 7 3 2 3 10 12 4 6 8)0→ 11 8 5段图 2021/2/20
2021/2/20 19 1 2345 678 9 10 11 12 9732 4 3 2 7 11 11 8 1 4 563 5 6 425 V 1 V2 V3 V4 V5 5段图
例4.60/1背包问题(向后处理策略) 设f(x)是KNAP(1)X)的最优解 则,f1M)=KNAP(1n,M) ●由于xn的取值等于1或0,可得: fn(M)=max f-1 M ), -1 M-Wp)+pJ ●对于某个X,X等于1或0,则有: 向后递推关系式: f, X)=max fi-1(X), -1 -Wi+p1 初始值: 0X≥0 (×) X<0 2021/2/20
2021/2/20 20 例4.6 0/1背包问题（向后处理策略） 设f i (x)是KNAP(1,i,X)的最优解。 则，fn (M) = KNAP(1,n,M) ● 由于xn的取值等于1或0,可得： fn (M)=max{fn-1 (M),fn-1 (M-wn )+pn } ● 对于某个xi，xi等于1或0，则有： 向后递推关系式： f i (X)=max{fi-1 (X),fi-1 (X-wi )+pi } 初始值： 0 X≥0 f0 (X) = -∞ X＜0