作者Franckie ( )
看板Prob_Solve
標題Re: [問題] 一個感覺是 dynamic programming 的題目
時間Fri Apr 23 09:36:38 2010
※ 引述《locomotion (locomotion)》之銘言：
: : 題目是這樣的:
: : 給定 n 個箱子, 每個箱子有其自己的 重量 以及 載重量
: : 現在要將箱子一層一層往上疊, 順序不拘
: : 每個箱子上方所有的重量加起來不能超過自己的載重量
: : 試問, 最高可以疊到幾層?
: 換個方向思考吧，不要先放最下面的那一個
: 先放最上面的那一個呢?
: 1.先將所有箱子依載重量由小到大排 (Sorting:O(nlogn))
: 2.依載重量由小到大放進list
: a.如果累積的重量比當前箱子的載重量小，將箱子放進list
: b.如果累積的重量超過當前箱子的載重量
: 將目前list中最重的箱子拿走
請問l大 2.b 這個步驟您要怎樣實做呢?
這個步驟的複雜度應該不太可能是O(1)吧?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.218.212.227
1F：推 Fenikso:O(logn), 用heap 04/23 09:38
2F：→ Franckie:不需要建heap的cost? 04/23 09:44
4F：→ bleed1979:用priority_queue 速度0.020s F兄的0.096s 04/23 09:50
5F：→ bleed1979:我的還在debug, 速度超慢。 04/23 09:50
6F：推 Fenikso:to 2F: 不需要 因為一開始heap是空的 04/23 12:02
7F：→ Fenikso: 然後push pop都是O(logn) 04/23 12:03
8F：推 Fenikso: total複雜度是nlogn 04/23 12:08
9F：推 suhorng:我用 std::push_heap/std::pop_heap, 0.008 04/23 21:50