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

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

          發(fā)現(xiàn)書上很多加了星號的題目我都得看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)


          評論

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

          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ù)  更多評論   

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

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

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

          修改成:
          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ì),真是讓我這個(gè)作者汗顏啊。

          # 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)的啊 怎么會(huì)等于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 注意其中有一個(gè)2

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


          網(wǎng)站導(dǎo)航:
           
          主站蜘蛛池模板: 瓮安县| 都匀市| 龙江县| 资溪县| 武乡县| 左贡县| 新乡县| 嘉定区| 石河子市| 连平县| 米脂县| 黄石市| 宣威市| 江孜县| 古浪县| 修文县| 桑日县| 梅州市| 韩城市| 丘北县| 将乐县| 阳谷县| 分宜县| 玉田县| 汉源县| 永康市| 宣化县| 翁源县| 海原县| 马鞍山市| 锡林郭勒盟| 阳东县| 达日县| 麻城市| 迭部县| 屯门区| 渝北区| 安塞县| 车致| 搜索| 融水|