Re: [問題] 一個感覺是 dynamic programming 的題目

[Franckie ( )]

※ 引述《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
推 Fenikso:O(logn), 用heap
→ Franckie:不需要建heap的cost?
→ bleed1979:l大的方法程式碼  http://nopaste.csie.org/c3293
→ bleed1979:用priority_queue  速度0.020s F兄的0.096s
→ bleed1979:我的還在debug, 速度超慢。
推 Fenikso:to 2F: 不需要 因為一開始heap是空的
→ Fenikso:      然後push pop都是O(logn)
推 Fenikso:      total複雜度是nlogn
推 suhorng:我用 std::push_heap/std::pop_heap, 0.008