Log2(1,000,000)/500,000=
第六章 动态规划
习题8.1 P224
1 a. 两者都具有最优子结构性质, 即将问题分解为较小的问题，分别解决，然
后合并到一起。
b. 动态规划技术解决的问题一般由交叠的子问题构成。 分治法分解后的子问题是相互独立的，可以用于并行计算。 2
C F
F(0)=0, F(1)=C1=5;
F(2)=max{ c2+F(n-2), F(n-1) } = max{ c2+F(2-2), F(1)} =max{1+0, 5}=5 F(3)=max{ c3+F(n-2), F(n-1) } = max{ c3+F(3-2), F(2)} =max{2+5, 5}=7 F(4)=max{ c4+F(n-2), F(n-1) } = max{ c4+F(4-2), F(3)} =max{10+5, 7}=15 F(5)=max{ c5+F(n-2), F(n-1) } = max{ c5+F(5-2), F(4)} =max{6+7,15}=15 总金额：15
习题8.2 P229
1 a. w = 3, 2, 1, 4, 5 v= 25 20 15 40 50 W=6
0 0 0 1 5 5 2 1 5 3 2 7 4 10 15 5 6 15 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 0 0 25 25 25 25 2 0 0 20 25 25 45 45 3 0 15 20 35 40 45 60 4 0 15 20 35 40 55 60 5 0 15 20 35 40 55 65
b. 最优子集：{3,5}
c. 看列的变化，如果总价值不变，则只看到一个最优子集 变化，则不止一个最优子集
4 a, b 正确
习题8.4 P241 1 该图的传递闭包： 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 0 7
a b c d e
a 0 2 w 1 8 b 6 0 3 2 w
D0= c w w 0 4 w
d w w 2 0 3
e 3 w w w 0
a b c d e a 0 2 w 1 8 b 6 0 3 2 14
D1 = c w w 0 4 w
d w w 2 0 3
e 3 5 w 4 0
a b c d e a 0 2 5 1 8 b 6 0 3 2 14
D2 = c w w 0 4 w
d w w 2 0 3
e 3 5 8 4 0
a b c d e a 0 2 5 1 8 b 6 0 3 2 14
D3 = c w w 0 4 w
d w w 2 0 3
e 3 5 8 4 0
a b c d e a 0 2 3 1 4 b 6 0 3 2 5
D4 = c w w 0 4 7
d w w 2 0 3
e 3 5 6 4 0
a b c d e
a 0 2 3 1 4 b 6 0 3 2 5
D5 = c 10 12 0 4 7
d 6 8 2 0 3
e 3 5 6 4 0
最后的最短距离矩阵为： a b c d e
a 0 2 3 1 4 b 6 0 3 2 5
D = c 10 12 0 4 7
d 6 8 2 0 3
e 3 5 6 4 0