Posted on 2007-10-15 17:12
ZelluX 阅读(4104)
评论(6) 编辑 收藏
开始用Word 2007发布日志
发现书上很多加了星号的题目我都得看Instructor's Manual才会做 =_=
Problem: Show how to solve the fractional knapsack problem in O(n) time. Assume that you have a solution to Problem 9-2.
Problem 9-2就是在最差情况下也能在O(n)时间内求出第k大元素的算法。
解答：
使用线性算法找出Vi / Wi的中位数
将物体分成三个集合，G = { i : Vi / Wi > m } E = { i : Vi / Wi = m} L : { i : Vi / Wi < m}，同样能在线性时间内完成
计算WG = Sigma(Wi), i ∈ G; WE = Sigma(Wi), i ∈ E
-
如果WG > W，则不在G中取出任何物体，而是继续递归分解G
-
如果WG <= W，取出G中所有物体，并尽可能多得取出E中物体
-
如果WG + WE >= W，也就是说步骤2以后背包已经放满，则问题解决
-
否则如果尚未放满，则继续在L上递归调用查找W – WG - WE的方案
以上所有调用都在线性时间内完成，每次递归调用都能减少一半的数据规模
因此运行时间的递归式为
T(n) <= T(n/2) + Omega(n)
有Master Theorem可得
T(n) = O(n)