大家好:
最近小弟在台大上高等演算法,下面有份作業,我一直想不通當中的關鍵所在.....
The job is to distribute n gifts g_1, g_2, g_n to two children A and B.
Gift g_i has nonnegative value v_i. These gifts cannot be split.
Every child must receive at least one gift with non-zero value.
Every gift must be given to one of the two children.
All gifts and their values are known in advance.
Let child A receives set of gifts S_A; child B receives set of gifts S_B.
Their total values are
V_A=\sum_{g_i \in S_A}v_i and V_B=\sum_{g_i \in S_B}v_i,resp.
The goal is to minimize r=max(V_A,V_B)/min(V_A,V_B)
Now, Consider the following greedy algorithm:
For i = 1 to n,
Assign gift gi to the child who currently has lower total value.
Prove that the above greedy algorithm is an O(1)-approximation algorithm.
(代過一些例子,可得知greedy的解和最佳解最多應該會差3倍)
假設此問題的最佳解是r*,我們根據題目要求可以得知1<=r*<=r.
但要證r<=3r*時,我曾嘗試過參考load-balance的作法解,但行不太通......
想跟各路高手請教看看有何提示與建議?謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.16.95
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1491813494.A.9F8.html