[理工] 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