作者Franckie ( )
看板Prob_Solve
标题Re: [问题] 一个感觉是 dynamic programming 的题目
时间Fri Apr 23 10:54:04 2010
l大的算法有问题
input: weight{10,20,30} capacity{11,100,10}
l大跑出来的是2,
但正确的是3
※ 引述《Franckie ( )》之铭言：
: ※ 引述《locomotion (locomotion)》之铭言：
: : 换个方向思考吧，不要先放最下面的那一个
: : 先放最上面的那一个呢?
: : 1.先将所有箱子依载重量由小到大排 (Sorting:O(nlogn))
: : 2.依载重量由小到大放进list
: : a.如果累积的重量比当前箱子的载重量小，将箱子放进list
: : b.如果累积的重量超过当前箱子的载重量
: : 将目前list中最重的箱子拿走
: 请问l大 2.b 这个步骤您要怎样实做呢?
: 这个步骤的复杂度应该不太可能是O(1)吧?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.218.212.227
1F：→ bleed1979:这就是有没有包含自己影响排序。文章里倒是没细讲。 04/23 11:48
2F：推 keeperkai:没有包含都是一样的，请看我下面的文章可以进行mapping 04/23 12:13
3F：→ suhorng:必须把自己的载重加上去排序才是正确的，前文都有证明 04/23 21:51