1. package com.atguigu.greedy;
    3. import org.junit.Test;
    5. import java.util.ArrayList;
    6. import java.util.HashMap;
    7. import java.util.HashSet;
    9. /**
    10. * 贪心算法 -- 集合覆盖问题
    11. *
    12. * @author Dxkstart
    13. * @create 2022-04-13-16:05
    14. */
    15. public class GreedyDemo {
    18.     public static void main(String[] args) {
    20.         // 创建广播电台，放入到Map
    21.         HashMap<String, HashSet<String>> broadCasts = new HashMap<>();
    23.         // 向broadCasts中存入电台数据
    24.         HashSet<String> set1 = new HashSet<>();
    25.         set1.add("北京");
    26.         set1.add("上海");
    27.         set1.add("天津");
    29.         HashSet<String> set2 = new HashSet<>();
    30.         set2.add("广州");
    31.         set2.add("北京");
    32.         set2.add("深圳");
    34.         HashSet<String> set3 = new HashSet<>();
    35.         set3.add("成都");
    36.         set3.add("上海");
    37.         set3.add("杭州");
    39.         HashSet<String> set4 = new HashSet<>();
    40.         set4.add("上海");
    41.         set4.add("天津");
    43.         HashSet<String> set5 = new HashSet<>();
    44.         set5.add("杭州");
    45.         set5.add("大连");
    47.         broadCasts.put("k1",set1);
    48.         broadCasts.put("k2",set2);
    49.         broadCasts.put("k3",set3);
    50.         broadCasts.put("k4",set4);
    51.         broadCasts.put("k5",set5);
    54.         // 存放所有的地区
    55.         HashSet<String> allAreas = new HashSet<>();
    56.         allAreas.add("北京");
    57.         allAreas.add("上海");
    58.         allAreas.add("天津");
    59.         allAreas.add("广州");
    60.         allAreas.add("深圳");
    61.         allAreas.add("成都");
    62.         allAreas.add("杭州");
    63.         allAreas.add("大连");
    65.         // 存放选择的电台
    66.         ArrayList<String> selects = new ArrayList<>();
    68.         // 定义一个临时的集合，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
    69.         HashSet<String> tempSet = new HashSet<>();
    71.         // 定义maxKey，保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
    72.         // 如果maxKey不为null，则会加入到selects中
    73.         // allAreas.size()等于0时，说明此时电台已经覆盖完全了
    74.         String maxKey = null;
    75.         while (allAreas.size() != 0) {
    77.             // 遍历broadCasts，取出对应的key
    78.             for (String key : broadCasts.keySet()) {
    79.                 // 当前这个key能够覆盖的地区
    80.                 HashSet<String> areas = broadCasts.get(key);
    81.                 tempSet.addAll(areas);
    82.                 // 求出tempSet与allAreas的交集，交集会赋给tempSet
    83.                 tempSet.retainAll(allAreas);
    84.                 // 如果当前这个集合包含的未覆盖地区的数据，比maxKey指向的集合地区还多
    85.                 // 就需要重置maxKey
    86.                 // tempSet.size() > broadCasts.get(maxKey).size() 体现了贪心算法中的贪心 -> 每次都选择最好的
    87.                 if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadCasts.get(maxKey).size())) {
    88.                     maxKey = key;
    89.                 }
    90.                 // 清空交集
    91.                 tempSet.clear();
    92.             }
    93.             // 一轮循环结束
    94.             if (maxKey != null) {
    95.                 selects.add(maxKey);
    96.                 // 将此次加入的电台覆盖的城市从allAreas中删除
    97.                 allAreas.removeAll(broadCasts.get(maxKey));
    98.                 maxKey = null;
    99.             }
    100.         }
    102.         // 输出结果
    103.         System.out.println("得到的结果：" + selects); // [k1, k2, k3, k5]
    104.     }
    106. }

    image.png