posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁(yè) :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          開始用Word 2007發(fā)布日志

          發(fā)現(xiàn)書上很多加了星號(hào)的題目我都得看Instructor's Manual才會(huì)做? =_=

          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)時(shí)間內(nèi)求出第k大元素的算法。

          解答:

          使用線性算法找出Vi / Wi的中位數(shù)
          將物體分成三個(gè)集合,G = { i : Vi / Wi > m }??? E = { i : Vi / Wi = m}?? L : { i : Vi / Wi < m},同樣能在線性時(shí)間內(nèi)完成
          計(jì)算WG = Sigma(Wi), i ∈ G; WE = Sigma(Wi), i E

          1. 如果WG > W,則不在G中取出任何物體,而是繼續(xù)遞歸分解G
          2. 如果WG <= W,取出G中所有物體,并盡可能多得取出E中物體
          3. 如果WG + WE >= W,也就是說步驟2以后背包已經(jīng)放滿,則問題解決
          4. 否則如果尚未放滿,則繼續(xù)在L上遞歸調(diào)用查找W – WG - WE的方案


          以上所有調(diào)用都在線性時(shí)間內(nèi)完成,每次遞歸調(diào)用都能減少一半的數(shù)據(jù)規(guī)模
          因此運(yùn)行時(shí)間的遞歸式為
          T(n) <= T(n/2) + Omega(n)
          有Master Theorem可得
          T(n) = O(n)


          評(píng)論

          # re: CLRS 習(xí)題 16.2-6 部分背包問題的O(n)算法  回復(fù)  更多評(píng)論   

          2011-09-11 21:36 by MKD
          您這裡PO錯(cuò)啦
          4.否則如果尚未放滿,則繼續(xù)在L上遞歸調(diào)用查找W – WG - WG的方案

          修正為:
          4.否則如果尚未放滿,則繼續(xù)在L上遞歸調(diào)用查找W – WG - WE的方案

          # re: CLRS 習(xí)題 16.2-6 部分背包問題的O(n)算法  回復(fù)  更多評(píng)論   

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

          # re: CLRS 習(xí)題 16.2-6 部分背包問題的O(n)算法  回復(fù)  更多評(píng)論   

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

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

          # re: CLRS 習(xí)題 16.2-6 部分背包問題的O(n)算法  回復(fù)  更多評(píng)論   

          2011-09-11 22:01 by ZelluX
          @Makodo
          嗯,的確應(yīng)該是 WG <= W,您看帖如此仔細(xì),真是讓我這個(gè)作者汗顏啊。

          # re: CLRS 習(xí)題 16.2-6 部分背包問題的O(n)算法  回復(fù)  更多評(píng)論   

          2012-03-02 22:27 by ynnej
          T(n)=T(n/2)+O(n)的話,算法復(fù)雜度還是等于O(nlgn)的啊 怎么會(huì)等于O(n)呢?

          # re: CLRS 習(xí)題 16.2-6 部分背包問題的O(n)算法  回復(fù)  更多評(píng)論   

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

          只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


          網(wǎng)站導(dǎo)航:
           
          主站蜘蛛池模板: 祁阳县| 福清市| 张家界市| 莱西市| 松江区| 岚皋县| 新乐市| 荣昌县| 金溪县| 重庆市| 库车县| 柘荣县| 余江县| 永新县| 黑山县| 吴桥县| 敦煌市| 阿尔山市| 济宁市| 包头市| 开原市| 保亭| 西平县| 宁阳县| 内丘县| 扶绥县| 桐乡市| 称多县| 隆安县| 广德县| 潞城市| 福鼎市| 绥芬河市| 施甸县| 通榆县| 武陟县| 京山县| 泰和县| 淮滨县| 分宜县| 宜章县|