作者kissuo (Evolution ...)
看板Prob_Solve
標題[請益] 一個greedy algo求解 ...
時間Thu Nov 20 08:03:34 2008
今天我們有2個背包
有n個物件
第i個物件的重量是Wi
目標是把這n個物件全放進這2個背包以後
能讓這2個背包裝完以後的最大重量都最小化
（Minize the maximum value of the load of each backpack）
現在有一個Greedy
方法是每次物件要塞進背包的時候都選擇放進比較輕的背包
現在有針對item set 'X' 我們得到：
W*(X)是optimal solution
W (X)是用我們這個greedy以後的solution
要證明
W(X) 小於等於 2 x W*(X)
甚至是
W(X) 小於等於 1.5 x W*(X)
想請問版上的大家這種題目該怎麼證呢?
多謝多謝
※ 編輯: kissuo 來自: 169.235.44.52 (11/20 08:04)