[請益] 一個greedy algo求解 ...
看板Prob_Solve (計算數學 Problem Solving)作者kissuo (Evolution ...)時間16年前 (2008/11/20 08:03)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/1
今天我們有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)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
