贪心算法之集合覆盖问题

贪心算法

• 贪心算法介绍
  • 贪心算法是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最优的算法
  • 贪婪算法所得到的结果不一定是最优的结果（有时候会是最优解），但是都是相对近似（接近）最优解的结果
• 应用场景-集合覆盖问题
  • 假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。如何选择最少的广播台，让所有的地区都可以接收到信息。
    
  • 思路分析
    • 遍历所有的广播电台，找到一个覆盖了最多未覆盖地区的电台（此电台可能包含一些已覆盖的地区，但没有关系）
    • 将这个电台加入到一个集合中(比如ArrayList)，想办法把该电台覆盖的地区在下次比较时去掉
    • 重复之前步骤，直到覆盖了全部地区
  • 图解
    
  • 代码

  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.HashSet;
  
  public class GreedyAlgorithm {
      public static void main(String[] args) {
          // 创建广播电台，放入map中
          HashMap<String,HashSet<String>> broadcasts = new HashMap<>();
          // 将各个电台放入到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);
  
          // 存放所有的地区集合
          HashSet<String> allAreas = new HashSet<>();
          allAreas.addAll(hashSet1);
          allAreas.addAll(hashSet2);
          allAreas.addAll(hashSet3);
          allAreas.addAll(hashSet4);
          allAreas.addAll(hashSet5);
  
          // 创建一个集合，存放选择的电台集合
          ArrayList<String> selects = new ArrayList<>();
          // 保存每一次遍历的过程中，能够覆盖最大未覆盖的地区对应的电台Key
          String maxKey = null;
          // 定义一个临时的集合，在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
          HashSet<String> tempSet = new HashSet<>();
          // 当集合不为空时，表示还有未被覆盖的地区
          while(allAreas.size() > 0) {
              maxKey = null;
              for (String key : broadcasts.keySet()) {
                  tempSet.clear();
                  // 当前这个key能够覆盖的地区
                  HashSet<String> areas = broadcasts.get(key);
                  tempSet.addAll( areas);
                  // 求出tempSet和allAreas的交集，交集保存在tempSet中
                  tempSet.retainAll(allAreas);
                  // 如果tempSet中有未被覆盖的元素，则比较maxKey,看哪一个集合中未被覆盖的元素多，将多的一方重新赋值给maxKey
                  if(tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                      maxKey = key;
                  }
              }
              if (maxKey != null) {
                  selects.add(maxKey);
                  // 将maxKey指向的广播电台覆盖的地区，从allAreas中移除
                  allAreas.removeAll(broadcasts.get(maxKey));
              }
          }
  
          System.out.println("得到的选择是：" + selects);
      }
  }