作者DJWS (...)
看板Prob_Solve
標題Re: [問題] 一個感覺是 dynamic programming 的題目
時間Thu Apr 22 12:51:58 2010
※ 引述《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
1F：推 suhorng:嗯……可能跟 l 大討論的情況不太一樣喔 04/22 12:56
2F：→ suhorng:我們之前討論的情況，好像是在"累積重量"包含自己重量的前 04/22 12:58
3F：→ suhorng:題之下,那我們不妨把載重量加上自己的重量,並在累積重量時 04/22 12:58
4F：→ suhorng:把自己的重量也加進去Y 04/22 12:58
5F：→ DJWS:好...那我再想想看 04/22 12:59