Posted on 2007-10-15 17:12
ZelluX 閱讀(4132)
評論(6) 編輯 收藏
開始用Word 2007發布日志
發現書上很多加了星號的題目我都得看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)時間內求出第k大元素的算法。
解答：
使用線性算法找出Vi / Wi的中位數
將物體分成三個集合，G = { i : Vi / Wi > m }??? E = { i : Vi / Wi = m}?? L : { i : Vi / Wi < m}，同樣能在線性時間內完成
計算WG = Sigma(Wi), i ∈ G; WE = Sigma(Wi), i ∈ E
-
如果WG > W，則不在G中取出任何物體，而是繼續遞歸分解G
-
如果WG <= W，取出G中所有物體，并盡可能多得取出E中物體
-
如果WG + WE >= W，也就是說步驟2以后背包已經放滿，則問題解決
-
否則如果尚未放滿，則繼續在L上遞歸調用查找W – WG - WE的方案
以上所有調用都在線性時間內完成，每次遞歸調用都能減少一半的數據規模
因此運行時間的遞歸式為
T(n) <= T(n/2) + Omega(n)
有Master Theorem可得
T(n) = O(n)