PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者 ( )時間14年前 (2010/04/23 09:36), 編輯推噓4(4推 0噓 5→)
留言9則, 4人參與, 最新討論串9/12 (看更多)
※ 引述《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
推
04/23 09:38, , 1F
O(logn), 用heap
04/23 09:38, 1F
→
04/23 09:44, , 2F
不需要建heap的cost?
04/23 09:44, 2F
→
04/23 09:49, , 3F
l大的方法程式碼 http://nopaste.csie.org/c3293
04/23 09:49, 3F
→
04/23 09:50, , 4F
用priority_queue 速度0.020s F兄的0.096s
04/23 09:50, 4F
→
04/23 09:50, , 5F
我的還在debug, 速度超慢。
04/23 09:50, 5F
推
04/23 12:02, , 6F
to 2F: 不需要 因為一開始heap是空的
04/23 12:02, 6F
→
04/23 12:03, , 7F
然後push pop都是O(logn)
04/23 12:03, 7F
推
04/23 12:08, , 8F
total複雜度是nlogn
04/23 12:08, 8F
推
04/23 21:50, , 9F
我用 std::push_heap/std::pop_heap, 0.008
04/23 21:50, 9F
‣ 更多 Franckie 的文章
文章代碼(AID): #1BqFceCP (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 9 之 12 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共12篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Franckie 的文章
文章代碼(AID): #1BqFceCP (Prob_Solve)