【数据结构和算法】贪心算法

算法之贪心算法的介绍以及案例实现

---

1 贪心算法

1.1 介绍

贪心算法（贪婪算法）：是指在对问题进行求解时，在每一步选择中都采用最好/最优的选择，从而希望能够导致结果是最后或者最优的算法

贪心算法所得的结果不一定是最优的结果，但是都是相对近似最优解的结果

---

2 集合覆盖问题

2.1 问题

2.2 思路

• （1）求出需要覆盖的所有数据的集合

• （2）计算每个集合未覆盖的数据个数，记录个数最多的集合，此为局部最优集合，也是贪心算法的思想，每一步挑选最优的

• （3）更新需要覆盖的数据的集合，循环上述操作，直到需要覆盖的数据集合大小为0

2.3 代码

• （1）集合覆盖问题类

  /**
   * 集合覆盖问题
   * @author letere
   * @create 2021-06-08 17:14
   */
  public class CoverSet<T> {
      //集合
      private final Map<String, List<T>> set;
  
      //构造器
      public CoverSet(Map<String, List<T>> set) {
          this.set = set;
      }
  
      /**
       * 贪心算法（解决集合覆盖）
       */
      public void greedyAlgorithm() {
          //未覆盖集合
          Set<T> unCoverSet = getUnCoverSet();
          //选择策略
          List<String> strategy = new ArrayList<>();
  
          while (unCoverSet.size() > 0) {
              //局部最优集合名
              String bestSet = "";
              //最大未覆盖数
              int max = 0;
              //缓存变量
              int temp;
  
              for (Map.Entry<String, List<T>> entry : set.entrySet()) {
                  temp = calUnCoverCount(entry.getValue(), unCoverSet);
                  //对比比较出最大未覆盖数，从而得出局部最优集合
                  if (max < temp) {
                      bestSet = entry.getKey();
                      max = temp;
                  }
              }
              //添加进选择策略
              strategy.add(bestSet);
              //移除已覆盖数据
              removeSet(unCoverSet, set.get(bestSet));
          }
          
          System.out.println("选择策略为：" + strategy);
      }
  
  
      /**
       * 获取未覆盖集合
       * @return Set
       */
      private Set<T> getUnCoverSet() {
          //Set集合自动去重
          Set<T> unCoverSet = new HashSet<>();
  
          //遍历添加到set中
          for (List<T> value : set.values()) {
              unCoverSet.addAll(value);
          }
  
          return unCoverSet;
      }
  
  
      /**
       * 计算未覆盖个数
       * @param list 集合
       * @param unCoverSet 未覆盖集合
       * @return int
       */
      private int calUnCoverCount(List<T> list, Set<T> unCoverSet) {
          int count = 0;
          for (T item : list) {
              if (unCoverSet.contains(item)) {
                  count ++;
              }
          }
          return count;
      }
  
  
      /**
       * 移除已覆盖数据
       * @param unCoverSet 未覆盖集合
       * @param list 集合
       */
      private void removeSet(Set<T> unCoverSet, List<T> list) {
          for (T item : list) {
              unCoverSet.remove(item);
          }
      }
  }

• （2）测试

  @Test
  public void coverSet() {
  	//获取集合数据
  	Map<String, List<String>> set = getSetData();
  
  	//创建集合覆盖问题类
  	CoverSet<String> coverSet = new CoverSet<>(set);
  
  	coverSet.greedyAlgorithm(); //答案为：[K1, K2, K3, K5]
  }
  
  
  public Map<String, List<String>> getSetData() {
  	Map<String, List<String>> set = new HashMap<>();
  
  	String[] temp = new String[]{"北京", "上海", "天津"};
  	set.put("K1", Arrays.asList(temp));
  
  	temp = new String[]{"广州", "北京", "深圳"};
  	set.put("K2", Arrays.asList(temp));
  
  	temp = new String[]{"成都", "上海", "杭州"};
  	set.put("K3", Arrays.asList(temp));
  
  	temp = new String[]{"上海", "天津"};
  	set.put("K4", Arrays.asList(temp));
  
  	temp = new String[]{"杭州", "大连"};
  	set.put("K5", Arrays.asList(temp));
  
  	return set;
  }