作者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/m.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