總目錄：地址如下看總綱
1详炬、應(yīng)用場(chǎng)景-集合覆蓋問(wèn)題
假設(shè)存在下面需要付費(fèi)的廣播臺(tái)，以及廣播臺(tái)信號(hào)可以覆蓋的地區(qū)旅择。 如何選擇最少的廣播臺(tái)峻厚，讓所有的地區(qū)都可以接收到信號(hào)
2废境、貪心算法介紹
（1）貪婪算法(貪心算法)是指在對(duì)問(wèn)題進(jìn)行求解時(shí)，在每一步選擇中都采取最好或者最優(yōu)(即最有利)的選擇靖诗，從而希望能夠?qū)е陆Y(jié)果是最好或者最優(yōu)的算法
（2）貪婪算法所得到的結(jié)果不一定是最優(yōu)的結(jié)果(有時(shí)候會(huì)是最優(yōu)解)芦拿，但是都是相對(duì)近似(接近)最優(yōu)解的結(jié)果
（如果價(jià)格，考慮的話悔耘，那么可能對(duì)于價(jià)格讲岁，做不到最優(yōu)；只有方案配對(duì)最優(yōu)【畢竟不是綜合考慮的】）
3衬以、解決方案（舉例兩類：窮舉法缓艳，貪心算法）
（1）窮舉法：
如何找出覆蓋所有地區(qū)的廣播臺(tái)的集合呢，使用窮舉法實(shí)現(xiàn),列出每個(gè)可能的廣播臺(tái)的集合看峻，這被稱為冪集阶淘。假設(shè)總的有n個(gè)廣播臺(tái)，則廣播臺(tái)的組合總共有?2? -1 個(gè),假設(shè)每秒可以計(jì)算10個(gè)子集互妓， 如圖:
（2）貪心算法最佳應(yīng)用-集合覆蓋的思路分析：
目前并沒(méi)有算法可以快速計(jì)算得到準(zhǔn)備的值溪窒， 使用貪婪算法，則可以得到非常接近的解冯勉，并且效率高澈蚌。選擇策略上，因?yàn)樾枰采w全部地區(qū)的最小集合灼狰，具體步驟如下：
<1>遍歷所有的廣播電臺(tái), 找到一個(gè)覆蓋了最多未覆蓋的地區(qū)的電臺(tái)(此電臺(tái)可能包含一些已覆蓋的地區(qū)宛瞄，但沒(méi)有關(guān)系）--- 此集合大多時(shí)候是一個(gè) 或者 多個(gè)組合的 集合 ，這里的 "個(gè)" 指的是廣播臺(tái) K1,K2....
<2>將這個(gè)電臺(tái)加入到一個(gè)集合中(比如ArrayList), 想辦法把該電臺(tái)覆蓋的地區(qū)在下次比較時(shí)去掉
<3>重復(fù)第1步直到覆蓋了全部的地區(qū)
4交胚、貪心算法圖解：
說(shuō)明：
allAreas 為需要覆蓋所有廣播臺(tái)內(nèi)的地區(qū)份汗，
selects = ArrayList () 為最終集合（將需要被覆蓋的廣播臺(tái)集合匯總）
maxKey 指向當(dāng)前 包含 地區(qū)最多的廣播臺(tái)，若大小一樣依照順序（用于剔除 allAreas 中的地區(qū)蝴簇，符合就剔除）
key 用于指向每一個(gè)廣播臺(tái)裸影，依次移動(dòng) 查詢 和 allAreas 中的覆蓋地區(qū)個(gè)數(shù)
步驟：
（1）剛開(kāi)始 selects 沒(méi)有任何廣播臺(tái) ，allAreas 列出所有（暫時(shí)未被剔除）军熏，k1 到 k5 覆蓋地區(qū)個(gè)數(shù)分別為
3，3卷扮，3荡澎，2，2
（2）當(dāng) maxKey 指向 k1 后晤锹，K1 裝入 selcts 集合 摩幔，K1 中的地區(qū) 剔除匹配到 allAreas 中的地區(qū)
（3）此時(shí)個(gè)數(shù)最大的是 k2,k3,k5 ，按照順序優(yōu)先指向 K2 鞭铆。然后開(kāi)始如上操作或衡， maxKey 指向 K2,K2裝入 selects集合焦影， K2 中的地區(qū) 剔除 匹配到 allAreas 中的地區(qū)
（4）此時(shí)地區(qū)個(gè)數(shù)最大的廣播臺(tái)是 k3 , k5 按照順序 優(yōu)先 k3。同上 封断，maxKey 指向 k3, k3 裝入 selects 集合斯辰， k3 中的地區(qū)匹配到 allAreas 中的地區(qū) 并剔除
（5）此時(shí)最大地區(qū)個(gè)數(shù)只有 k5 ，同坡疼，maxKey 指向 k5 彬呻，k5 裝入 selects 集合，k5 中的地區(qū)匹配到 allAreas中的地區(qū)并 剔除柄瑰，此時(shí)所有都已經(jīng)覆蓋到闸氮， selects 為最終
5、貪心算法代碼實(shí)現(xiàn)
/*
* @Description: 貪心算法 -- 實(shí)現(xiàn)廣播問(wèn)題
* @Author: 阿K
* @CreateDate: 2021/2/7 16:30
* @Param:
* @Return:
**/
public class GreedyAlgorithm {
public static void main(String[] args) {
// 創(chuàng)建用于存放所有廣播電臺(tái)的 map
HashMap<String, HashSet<String>> broadcasts = new HashMap<> ( );
//將各個(gè)電臺(tái)放入到broadcasts
HashSet<String> hashSet1 = new HashSet<> ( );
hashSet1.add ("北京");
hashSet1.add ("上海");
hashSet1.add ("天津");
HashSet<String> hashSet2 = new HashSet<> ( );
hashSet2.add ("廣州");
hashSet2.add ("北京");
hashSet2.add ("深圳");
HashSet<String> hashSet3 = new HashSet<> ( );
hashSet3.add ("成都");
hashSet3.add ("上海");
hashSet3.add ("杭州");
HashSet<String> hashSet4 = new HashSet<> ( );
hashSet4.add ("上海");
hashSet4.add ("天津");
HashSet<String> hashSet5 = new HashSet<> ( );
hashSet5.add ("杭州");
hashSet5.add ("大連");
//加入到map
broadcasts.put ("K1", hashSet1);
broadcasts.put ("K2", hashSet2);
broadcasts.put ("K3", hashSet3);
broadcasts.put ("K4", hashSet4);
broadcasts.put ("K5", hashSet5);
//allAreas 存放所有的地區(qū)
HashSet<String> allAreas = obtainAllAreas (broadcasts);
//創(chuàng)建ArrayList, 存放選擇的電臺(tái)集合(最終答案)
ArrayList<String> selects = new ArrayList<> ( );
//定義一個(gè)臨時(shí)的集合教沾， 在遍歷的過(guò)程中蒲跨，存放遍歷過(guò)程中的電臺(tái)覆蓋的地區(qū)和當(dāng)前還沒(méi)有覆蓋的地區(qū)的交集
HashSet<String> tempSet = new HashSet<> ( );// 可以理解為不斷變動(dòng)的 allAreas
// 定義maxKey ， 保存在一次遍歷過(guò)程中授翻，能夠覆蓋最大未覆蓋的地區(qū)對(duì)應(yīng)的電臺(tái)的key
// 若 maxKey 不為null ,則會(huì)加入到 selects
String maxKey = null;
while (allAreas.size ( ) != 0) {// 若 allAreas 不為 0或悲，則表示還沒(méi)有覆蓋到所有地區(qū)（既沒(méi)有全部剔除完）
// maxKey 每次重新指向，都需要重置一次
maxKey = null;
// 遍歷 broadcasts, 取出對(duì)應(yīng)key
for (String key : broadcasts.keySet ( )) {
// 每次操作前 清空一次輔助集合
tempSet.clear ( );
// 當(dāng)前 key(廣播臺(tái))藏姐，所能覆蓋的地區(qū)
HashSet<String> areas = broadcasts.get (key);
// 拷貝到 輔助集合
tempSet.addAll (areas);
// 求出 tempSet 和 allAreas 的交集隆箩，并賦值于 tempSet
tempSet.retainAll (allAreas);
// 若當(dāng)前這個(gè)集合（廣播臺(tái)），包含的未覆蓋地區(qū)的數(shù)量羔杨，比maxKey指向的集合地區(qū)還要多
// 則需要重置 maxKey
// tempSet.size() >broadcasts.get(maxKey).size()) 體現(xiàn)出貪心算法的特點(diǎn),每次都選擇最優(yōu)的
if (tempSet.size ( ) > 0 && (maxKey == null || tempSet.size ( ) > broadcasts.get (maxKey).size ( ))) {
maxKey = key;
}
}
// maxKey != null, 就應(yīng)該將maxKey 加入selects
if (maxKey != null) {
selects.add (maxKey);
// 將maxKey指向的廣播電臺(tái)覆蓋的地區(qū)捌臊，從 allAreas 去掉(剔除)
allAreas.removeAll (broadcasts.get (maxKey));
}
}
System.out.println ("得到的選擇結(jié)果是" + selects);//[K1,K2,K3,K5]
}
// 獲取所有廣播電臺(tái)地區(qū)
private static HashSet<String> obtainAllAreas(HashMap<String, HashSet<String>> broadcasts) {
if (broadcasts != null && broadcasts.size ( ) > 0) {
HashSet<String> allAreas = new HashSet<> ( );
Set<String> keys = broadcasts.keySet ( );
for (String key : keys) {
HashSet<String> all = broadcasts.get (key);
for (String region : all) {
// 因 HashSet 會(huì)覆蓋，所以無(wú)需判斷
allAreas.add (region);
}
}
return allAreas;
}
return null;
}
}
6兜材、貪心算法注意事項(xiàng)和細(xì)節(jié)
（1）貪心算法所得到的結(jié)果不一定是最優(yōu)的結(jié)果(有時(shí)候會(huì)是最優(yōu)解)理澎，但是都是相對(duì)近似(接近)最優(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)的
7、倉(cāng)庫(kù)坐標(biāo)
