Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

开始用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

  1. 如果WG > W,则不在G中取出任何物体,而是继续递归分解G
  2. 如果WG <= W,取出G中所有物体,并尽可能多得取出E中物体
  3. 如果WG + WE >= W,也就是说步骤2以后背包已经放满,则问题解决
  4. 否则如果尚未放满,则继续在L上递归调用查找W – WG - WE的方案


以上所有调用都在线性时间内完成,每次递归调用都能减少一半的数据规模
因此运行时间的递归式为
T(n) <= T(n/2) + Omega(n)
有Master Theorem可得
T(n) = O(n)


评论

# re: CLRS 习题 16.2-6 部分背包问题的O(n)算法  回复  更多评论   

2011-09-11 21:36 by MKD
您這裡PO錯啦
4.否则如果尚未放满,则继续在L上递归调用查找W – WG - WG的方案

修正為:
4.否则如果尚未放满,则继续在L上递归调用查找W – WG - WE的方案

# re: CLRS 习题 16.2-6 部分背包问题的O(n)算法  回复  更多评论   

2011-09-11 21:38 by ZelluX
@MKD
谢谢指出,已修正。

# re: CLRS 习题 16.2-6 部分背包问题的O(n)算法  回复  更多评论   

2011-09-11 21:55 by Makodo
不客氣,您修改的速度好快!!
但, 那時間允許的話順便修改一下:

修改成:
2. 如果WG <= W,取出中G所有物体,并尽可能多得取出E中物体

# re: CLRS 习题 16.2-6 部分背包问题的O(n)算法  回复  更多评论   

2011-09-11 22:01 by ZelluX
@Makodo
嗯,的确应该是 WG <= W,您看帖如此仔细,真是让我这个作者汗颜啊。

# re: CLRS 习题 16.2-6 部分背包问题的O(n)算法  回复  更多评论   

2012-03-02 22:27 by ynnej
T(n)=T(n/2)+O(n)的话,算法复杂度还是等于O(nlgn)的啊 怎么会等于O(n)呢?

# re: CLRS 习题 16.2-6 部分背包问题的O(n)算法  回复  更多评论   

2012-10-28 19:28 by 荒废庭院
@ynnej
T(n)=2T(n/2)+O(n) 才是 nlgn 注意其中有一个2

只有注册用户登录后才能发表评论。


网站导航: