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)航:
           
          主站蜘蛛池模板: 台山市| 泰来县| 阿瓦提县| 灌阳县| 苍山县| 阜南县| 永仁县| 昌乐县| 密云县| 巴中市| 叙永县| 琼结县| 峨眉山市| 新宾| 乌兰察布市| 漾濞| 东乌| 陵川县| 庆安县| 阿巴嘎旗| 泰兴市| 沁源县| 象州县| 潍坊市| 启东市| 吉首市| 时尚| 天柱县| 沁水县| 崇仁县| 嘉义市| 南京市| 潼南县| 榆树市| 景德镇市| 虞城县| 永胜县| 石棉县| 水富县| 榕江县| 黑水县|