發表新討論
#20791: Greedy


40675023H (Yee)

學校 : 國立臺灣師範大學
編號 : 69370
來源 : [223.140.126.121]
最後登入時間 ：
2023-09-19 16:53:36
c318. rilak的期末考 前傳 | From: [223.136.125.48] | 發表日期 : 2020-03-07 16:03

這題有辦法證明使用greedy會是最佳解嗎？

 
#36769: Re: Greedy


liaoweichen1024@gmail.com (M_SQRT)

學校 : 新北市立新莊高級中學
編號 : 195452
來源 : [210.71.71.103]
最後登入時間 ：
2024-05-06 12:16:25
c318. rilak的期末考 前傳 | From: [118.150.177.13] | 發表日期 : 2023-08-07 22:42

這題有辦法證明使用greedy會是最佳解嗎？


題目提到"每個章節讀一遍要花1單位的時間"
每個選擇的代價都是1
所以這裡只要選價值最高的選擇就好
故使用貪婪策略是可以得到最佳解的

 
ZeroJudge Forum