→ bleed1979:這就是有沒有包含自己影響排序。文章裡倒是沒細講。 04/23 11:48
推 keeperkai:沒有包含都是一樣的，請看我下面的文章可以進行mapping 04/23 12:13
→ suhorng:必須把自己的載重加上去排序才是正確的，前文都有證明 04/23 21:51
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