Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:对于此题使用贪心算法的分析(希望大牛补充哦)

Posted by 20120702 at 2012-07-04 09:48:07 on Problem 1083
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator