作者tank123zzz (哇呼呼)
看板Grad-ProbAsk
标题[理工] greedy 举反例
时间Thu May 7 14:33:55 2020
先贴题目
下面第二题
https://i.imgur.com/cqVuaTe.png
题目是 select activity
要我们举例子证明如果是先选overlap少的
会产生出不是最佳解的答案
（正解是选先结束的）
我尝试找重叠“事件数”少的先选
但找不到反例可以证明这个方法是错的
感谢大大们
-----
Sent from JPTT on my Sony G3426.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.10.42.222 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1588833237.A.05F.html
※ 编辑: tank123zzz (39.10.42.222 台湾), 05/07/2020 14:34:38
※ 编辑: tank123zzz (39.10.42.222 台湾), 05/07/2020 14:35:45
※ 编辑: tank123zzz (39.10.42.222 台湾), 05/07/2020 15:19:06
2F：→ DLHZ: 求的找一些极端的情况 通常就是反例 05/07 19:05
3F：→ DLHZ: 如果单纯选重叠最少的就会先选比较长的那两个其中一个 05/07 19:06
5F：→ DLHZ: 别理我上面那图== 05/08 13:41
6F：→ DLHZ: 总之 最中间会先选 使得他上下两个不会出现在解里 但如此出 05/08 13:42
7F：→ DLHZ: 来的结果会有问题 05/08 13:42