Posted on 2007-10-15 17:12
ZelluX 閱讀(4138)
評(píng)論(6) 編輯 收藏
開始用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
-
如果WG > W，則不在G中取出任何物體，而是繼續(xù)遞歸分解G
-
如果WG <= W，取出G中所有物體，并盡可能多得取出E中物體
-
如果WG + WE >= W，也就是說步驟2以后背包已經(jīng)放滿，則問題解決
-
否則如果尚未放滿，則繼續(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)