算法分析第六章答案

1、12345674536- 42931WRC44+2+1=77+4+4=1515+2+1=1818+1+1=20012220722 32 3922+4+4=1010+2+1=1313+1+1=150222010 20 2744+1+2=77+1+1=9033071211+1+1=30403100ijj-i=0; j-i=1; j-i=2; j-i=3; j-i=420( (1, )( ,1)1)nn mmiR ijR i j20( (1,)( ,1)1)nn mmiR iimR i im2( (1, )(0,1)1)nmR nmnRmnmn由于我们通常只知道成功检索和不成功检索概率由于我们通常只

2、知道成功检索和不成功检索概率的近似值，因此，在较短的时间内找出几乎是最的近似值，因此，在较短的时间内找出几乎是最优的二分检索树，这也可能是一件很有意义的工优的二分检索树，这也可能是一件很有意义的工作。作。n所谓所谓几乎是最优的几乎是最优的二分检索树，就是对于给定的二分检索树，就是对于给定的P和和Q，该树的成本，该树的成本(由由(6.9)式计算式计算)几乎最小。已经几乎最小。已经证明，由以下方法获得这种检索树的算法可以有证明，由以下方法获得这种检索树的算法可以有O(nlogn)的时间复杂度：的时间复杂度：n选取这样的选取这样的k为根，它使为根，它使|W(0, k-1)- W(k, n) |尽可尽

3、可能地小。重复以上步骤去找这根的左、右子能地小。重复以上步骤去找这根的左、右子树。树。 n 对于习题对于习题6.3的数据，用上述方法找的数据，用上述方法找出一棵这样的二分检索树。它的成本是出一棵这样的二分检索树。它的成本是什么？什么？n 用用SPAKS写一个实现上述方法的算写一个实现上述方法的算法，你的算法的计算时间为法，你的算法的计算时间为O(nlogn)吗？吗？471518202101315479131通过求解递归关系式可通过求解递归关系式可得，时间复杂性平均情得，时间复杂性平均情况是况是O(nlogn)， n给出一个使得给出一个使得DKNAP(算法算法6.7 P141)出现出现最坏情况的

4、例子，它使得最坏情况的例子，它使得| Si |=2i, 0i0 : fi(X) = max fi 1(X) , fi 1(X wi)+pi （6.14）n设设fi(X)是是ZKNAP(1,i,X)最优解的值最优解的值, 则则对于任意的对于任意的fi(X), i0 : nnnn-1nnnn0 x/f (M) = max f(M-x w )+x p Mwiiii-1iiii0 x/f (X) = max f (X-x w )+x p Xwn假定两个仓库假定两个仓库W1和和W2都存有同一种货物，其库存量分别都存有同一种货物，其库存量分别为为r1和和r2. 现要将其全部发往现要将其全部发往n个目的地个

5、目的地D1，D2，Dn.设设发往发往Dj的货物为的货物为dj，因此，因此r1+r2 = dj. 如果由仓库如果由仓库Wi发送量发送量为为xij的货物到目的地的货物到目的地Dj的花费为的花费为Cij (xij) ，那么仓库问题就，那么仓库问题就是求各个仓库应给每个目的地发多少货才使总的花费最小。是求各个仓库应给每个目的地发多少货才使总的花费最小。即要求这些非负整数即要求这些非负整数xij， 1i2，1jn，它使得，它使得x1j+x2j = dj, 1jn ,并且使并且使i,jcij(xij)取最小值。假设当取最小值。假设当W1有有x的库存的库存且按最优方式全部发往目的地且按最优方式全部发往目的地D1，D2，, Di 时所需的花时所需的花费为费为gi(x)(W2的库存为的库存为1jidj-x)。于是，此库存问题的最。于是，此库存问题的最优总花费是优总花费是gn (r1)。 111110min , 11( )min ()