Re: [問題] 一個感覺是 dynamic programming 的題目
看板Prob_Solve (計算數學 Problem Solving)作者Franckie ( )時間14年前 (2010/04/23 10:54)推噓1(1推 0噓 2→)留言3則, 3人參與討論串10/12 (看更多)
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
→
04/23 11:48, , 1F
04/23 11:48, 1F
推
04/23 12:13, , 2F
04/23 12:13, 2F
→
04/23 21:51, , 3F
04/23 21:51, 3F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
