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

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

          發(fā)現(xiàn)書上很多加了星號的題目我都得看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)時間內(nèi)求出第k大元素的算法。

          解答:

          使用線性算法找出Vi / Wi的中位數(shù)
          將物體分成三個集合,G = { i : Vi / Wi > m }??? E = { i : Vi / Wi = m}?? L : { i : Vi / Wi < m},同樣能在線性時間內(nèi)完成
          計算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)用都在線性時間內(nèi)完成,每次遞歸調(diào)用都能減少一半的數(shù)據(jù)規(guī)模
          因此運(yùn)行時間的遞歸式為
          T(n) <= T(n/2) + Omega(n)
          有Master Theorem可得
          T(n) = O(n)


          評論

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

          2011-09-11 21:36 by MKD
          您這裡PO錯啦
          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ù)  更多評論   

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

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

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

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

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

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

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

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

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

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

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


          網(wǎng)站導(dǎo)航:
           
          主站蜘蛛池模板: 沛县| 革吉县| 邹平县| 正镶白旗| 肥乡县| 茶陵县| 廊坊市| 五指山市| 静乐县| 绵阳市| 尼勒克县| 桓台县| 平凉市| 双鸭山市| 赤水市| 巴彦县| 广宗县| 海原县| 寻甸| 集贤县| 凉山| 华宁县| 卢氏县| 鸡西市| 中卫市| 泌阳县| 香港| 安泽县| 米易县| 绥芬河市| 淮安市| 重庆市| 万年县| 独山县| 博野县| 杭锦旗| 依安县| 即墨市| 商水县| 宣恩县| 青岛市|