[理工] greedy 举反例

楼主: tank123zzz (哇呼呼)   2020-05-07 14:33:55
先贴题目
下面第二题
https://i.imgur.com/cqVuaTe.png
题目是 select activity
要我们举例子证明如果是先选overlap少的
会产生出不是最佳解的答案
(正解是选先结束的)
我尝试找重叠“事件数”少的先选
但找不到反例可以证明这个方法是错的
感谢大大们
作者: DLHZ ( )   2020-05-07 19:05:00
http://i.imgur.com/ifFRTDX.jpg 这样应该可以吧?针对他要求的找一些极端的情况 通常就是反例如果单纯选重叠最少的就会先选比较长的那两个其中一个

Links booklink

Contact Us: admin [ a t ] ucptt.com