「一、是什么？」

首先來看一個「集合覆蓋問題」：

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

也就是說現(xiàn)在地區(qū)總共有8個，即北京、上海、天津、廣州、深圳、成都、杭州、大連，如何訂購最少的廣播臺，可以收聽到這8個地區(qū)的廣播。

這個問題就是經(jīng)典的用貪心算法求解的問題。「貪心算法」是指在每一步選擇中都采取最優(yōu)的策略，從而希望能夠?qū)е陆Y(jié)果是最優(yōu)的一種算法。貪心算法所得到的結(jié)果并不一定是最優(yōu)的解，但都是相對接近最優(yōu)解的結(jié)果。

「二、案例：」

要解決上面的問題，該怎么做呢？常規(guī)的做法如下：

• 列出k1、k2、k3、k4、k5的所有可能組合，總共就有2^5 = 32種組合。怎么來的？就是5個數(shù)不考慮順序進行排列組合嘛。

• 在這32種組合中挑選一種可以覆蓋到8個地區(qū)，并且廣播臺最少的組合，那就是本題的解了。

這樣做顯然很麻煩，要是有100個廣播臺，那不是完犢子了。但是可以使用貪心算法，提高效率。「貪心算法步驟如下：」

• 遍歷所有的廣播臺，找到一個包含了最多當(dāng)前還未覆蓋地區(qū)的廣播臺；

• 將這個廣播臺存起來，想辦法把該廣播臺覆蓋的地區(qū)中下次選擇時，用別的廣播臺代替；

• 重復(fù)上面的步驟直到覆蓋了所有的地區(qū)。

如果用上面的案例來說的話，那么步驟就是：

• 遍歷廣播臺，一開始所有地區(qū)都還沒覆蓋，遍歷后發(fā)現(xiàn)k1、k2、k3都是覆蓋了3個地區(qū)，選擇這三個任何一個都可以，我們按照遍歷順序，選擇k1。將k1用一個ArrayList保存起來；

• 把k1覆蓋的地區(qū)從保存地區(qū)的集合中去掉，那么現(xiàn)在就只剩下5個地區(qū)沒覆蓋了；

• 再次遍歷廣播臺的集合，現(xiàn)在剩下5個地區(qū)未覆蓋，即廣州、深圳、成都、杭州、大連。哪個廣播臺包含最多未覆蓋的地區(qū)，那就選哪個?，F(xiàn)在k2、k3、k5都是包含了兩個還未被覆蓋的地區(qū)。按照遍歷順序，選擇k2；

• 再把k2覆蓋的地區(qū)從保存地區(qū)的集合中去掉，那么現(xiàn)在就剩下成都、杭州、大連三個地方未覆蓋了；

• 遍歷廣播臺集合，發(fā)現(xiàn)k3和k5都可以覆蓋兩個，按照遍歷順序，選擇k3；

• 再把k3覆蓋的地區(qū)從保存地區(qū)的集合中去掉，那么現(xiàn)在就剩下大連未覆蓋了；

• 毫無疑問，最后要選擇k5，因為只有k5能夠覆蓋大連。

所以最終的選擇結(jié)果是k1、k2、k3、k5。

「三、代碼實現(xiàn)：」

將上面的問題用代碼實現(xiàn)出來。

public class GreedyDemo {
 
 public static void main(String[] args) {
  // 廣播電臺及其對應(yīng)覆蓋地區(qū)用map保存
  Map<String, Set<String>> map = new HashMap<>();
  Set<String> areaSet1 = new HashSet<>();
  areaSet1.add("北京");
  areaSet1.add("上海");
  areaSet1.add("天津");
  
  Set<String> areaSet2 = new HashSet<>();
  areaSet2.add("北京");
  areaSet2.add("廣州");
  areaSet2.add("深圳");
  
  Set<String> areaSet3 = new HashSet<>();
  areaSet3.add("上海");
  areaSet3.add("成都");
  areaSet3.add("杭州");
  
  Set<String> areaSet4 = new HashSet<>();
  areaSet4.add("上海");
  areaSet4.add("天津");
  
  Set<String> areaSet5 = new HashSet<>();
  areaSet5.add("杭州");
  areaSet5.add("大連");
  
  map.put("k1", areaSet1);
  map.put("k2", areaSet2);
  map.put("k3", areaSet3);
  map.put("k4", areaSet4);
  map.put("k5", areaSet5);
  
  System.out.println(greedy(map));;
 }
 
 public static List<String> greedy(Map<String, Set<String>> map){
  // 遍歷map，拿到所有地區(qū)，保存起來
  Set<String> allArea = new HashSet<>();
  for(String key : map.keySet()) {
   allArea.addAll(map.get(key));
  }
  // 用來保存所選電臺的集合
  List<String> selected = new ArrayList<>();
  Set<String> temp = new HashSet<>();
  String selectedKey = null;
  while (allArea.size() != 0) {
   for (String key : map.keySet()) {
    temp.clear();
    selectedKey = null;
    Set<String> area = map.get(key);
    temp.addAll(area);
    // 跟allArea求交集
    temp.retainAll(allArea);
    if (temp.size() > 0 && (selectedKey == null || temp.size() > map.get(selectedKey).size())) {
     selectedKey = key;
    }
    // 找到了當(dāng)前這一輪選擇的廣播臺
    if (selectedKey != null) {
     selected.add(selectedKey);
     allArea.removeAll(map.get(selectedKey));
    }
   }
  }
  return selected;
 }
}