作者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)