迭代
S {1}
u
dist[2] dist[3] dist[4] dist[5]
初始 1 2 3 4
参考解答：（13分）
迭代 S {1} {1，2} {1，2，4} {1，2，4，3} {1，2，3，4，5}
u - 2 4 3 5
dist[2] 10 10 10 10 10
dist[3]
60 50 50 50
dist[4] 30 30 30 30 30
dist[5] 100 100 90 60 60
初始 1 2 3 4
6.（13分）有0-1背包问题如下：
n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。
其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。
P=(15，8，6，4，3，1) W=(2，3，4，5，8，10)，单位重量物品价值（7.5，2.67，1.5,0.8,0.375,0.1）
参考解答：（13分）
可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。 2.把重量为3的物品放进背包，此时剩余载重量为14，P为23； 3.把重量为4的物品放进背包，此时剩余载重量为10，P为29； 4.把重量为5的物品放进背包，此时剩余载重量为5，P为33. 由于8>5，所以不能再放进背包。
结果是把重量为2，3，4，5的物品装进背包，总价值最大为33.
7、将所给定序列a[1:n]分为长度相等的两段a[1:n/2]和a[n/2+1:n]，分别求出这两段的最大子段和，则a[1:n]的最大子段和有哪三种情形？(10分)
参考解答：（1）a[1:n]的最大子段和与a[1:n/2]的最大子段和相同。 （2）a[1:n]的最大子段和与的最大子段a[n/2+1:n]和相同。
⑶a[1:n]的最大子段和为∑ak(i= 8 写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=(48,12,61,3,5,19,32,7) 参考解答：写出maxmin算法对下列实例中找最大数和最小数的过程。 数组 A=() 1、 48,12,61,3, 5,19,32,7 2、 48,12 61,3 5,19 32,7 3、 48～61, 12～3 19～32，5～7 4、 61～32 3～5 5、 61 3 9 速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。 A=(65,70,75,80,85,55,50,2) 参考解答：第一个分割元素为65 (1) (2) (3) (4) (5) (6) (7) (8) i p 65 70 75 80 85 55 50 2 2 8 65 2 75 80 85 55 50 70 3 7 65 2 50 80 85 55 75 70 4 6 65 2 50 55 85 80 75 70 4 6 55 70 75 80 85 65 50 2 10 归并排序算法对下列实例排序，写出算法执行过程。 A=(48,12,61,3,5,19,32,7) 参考解答： 48,12,61,3 5,19,32,7 48,12 61,3 5,19 32,7 12,48 3,61 5,19 7,32 3, 12, 48, 61 5, 7, 19，32 3,5, 7,12，19，32，48,61
相关推荐：
loading