Re: [問題] 一個感覺是 dynamic programming 的題目
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間14年前 (2010/04/22 12:52)推噓1(1推 0噓 4→)留言5則, 2人參與討論串5/12 (看更多)
※ 引述《locomotion (locomotion)》之銘言：
: 1.先將所有箱子依載重量由小到大排 (Sorting:O(nlogn))
: 2.依載重量由小到大放進list
: a.如果累積的重量比當前箱子的載重量小，將箱子放進list
: b.如果累積的重量超過當前箱子的載重量
: 將目前list中最重的箱子拿走
這裡舉個反例。
這是一組合理的答案：
重量 載重量 累積重量
1 1 0
20 10 1
3 37 21
152 47 24
10 490 176
500 401 186
1 999 686
2 998 687
這是用載重量排序之後的情況，有個地方疊不上去....
重量 載重量 累積重量
1 1 0
20 10 1
3 37 21
152 47 24
500 401 176
10 490 676 ＜－－－－ 載重量小於累積重量，需捨棄某個箱子。
2 998 686
1 999 688
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.137.22.201
推
04/22 12:56, , 1F
04/22 12:56, 1F
→
04/22 12:58, , 2F
04/22 12:58, 2F
→
04/22 12:58, , 3F
04/22 12:58, 3F
→
04/22 12:58, , 4F
04/22 12:58, 4F
→
04/22 12:59, , 5F
04/22 12:59, 5F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
