作者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