Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:对于此题使用贪心算法的分析(希望大牛补充哦)In Reply To:对于此题使用贪心算法的分析(希望大牛补充哦) Posted by:lqc at 2010-04-09 10:19:28 > 将s从大到小排序或将t从小到大排序进行贪心是不能得到全局最优的,它只能保证是当前剩余房间的局部最优,看看这组数据便知: > 1 > 4 > 2 4 > 1 6 > 10 12 > 5 14 > 答案为20 > (数据来自dicuss) > > 将s从小到大排序进行贪心则可以得到全局最优,但不能保证局部最优(局部最优是指选取最多的桌子进行移动)。 > 另外,注意看题目中给出的图,1-2,3-4,5-6...是占用走廊的相同空间,所以2-3 4-5的最优时间为20。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator