內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會偶爾插入自己的注釋和理解，盡量會完成作業(yè)

14.5.1應(yīng)用場景-集合覆蓋問題

假設(shè)存在下面需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區(qū)。如何選擇最少的廣播臺，讓所有的地區(qū)都可以接收到信號

14.5.2貪心算法介紹

1)????? 貪婪算法(貪心算法)是指在對問題進行求解時，在每一步選擇中都采取最好或者最優(yōu)(即最有利)的選擇，從而希望能夠?qū)е陆Y(jié)果是最好或者最優(yōu)的算法

2)????? 貪婪算法所得到的結(jié)果不一定是最優(yōu)的結(jié)果(有時候會是最優(yōu)解)，但是都是相對近似(接近)最優(yōu)解的結(jié)果

14.5.3貪心算法最佳應(yīng)用-集合覆蓋問題

假設(shè)存在下面需要付費的廣播臺，以及廣播臺信號可以覆蓋的地區(qū)。如何選擇最少的廣播臺，讓所有的地區(qū)都可以接收到信號

思路分析:

如何找出覆蓋所有地區(qū)的廣播臺的集合呢，使用窮舉法實現(xiàn),列出每個可能的廣播臺的集合，這被稱為冪集。假設(shè)總的有n個廣播臺，則廣播臺的組合總共有2^n-1個,假設(shè)每秒可以計算10個子集，如圖:

?? 使用貪婪算法，效率高:

目前并沒有算法可以快速計算得到準備的值，使用貪婪算法，則可以得到非常接近的解，并且效率高。選擇策略上，因為需要覆蓋全部地區(qū)的最小集合:

遍歷所有的廣播電臺,找到一個覆蓋了最多未覆蓋的地區(qū)的電臺(此電臺可能包含一些已覆蓋的地區(qū)，但沒有關(guān)系)

將這個電臺加入到一個集合中(比如ArrayList)，想辦法把該電臺覆蓋的地區(qū)在下次比較時去掉。重復第1步直到覆蓋了全部的地區(qū)

分析的圖解：

代碼實現(xiàn)：

14.5.4貪心算法的注意事項和細節(jié)

1)????? 貪婪算法所得到的結(jié)果不一定是最優(yōu)的結(jié)果(有時候會是最優(yōu)解)，但是都是相對近似(接近)最優(yōu)解的結(jié)果

2)????? 比如上題的算法選出的是K1,K2,K3,K5，符合覆蓋了全部的地區(qū)

3)????? 但是我們發(fā)現(xiàn)K2，K3,K4,K5也可以覆蓋全部地區(qū)，如果K2的使用成本低于K1,那么我們上題的K1, K2,K3,K5雖然是滿足條件，但是并不是最優(yōu)的.