贪心算法

贪心算法 
贪心算法：

贪婪算法（贪心算法）是指在对问题进行求解时，在每一步选择中都采取最好或者最优（即最有利）的选择，从而希望能够导致结果是最好或者最有的算法。
贪心算法所得到的结果不一定是最优的结果（有时会是最优解），但是都是相对近似最优解的结果
贪心算法最佳应用—集合覆盖

思路：

我们通过选择每次覆盖最多地区的广播台，然后将其添加到我们记录广播台的ArrayList集合中即selects。
每次添加完广播台，我们需要在记录所有需要覆盖地区的集合allAreas中删除掉该广播台覆盖的地区，然后继续循环，执行1操作
allAreas中的地区全部删除掉，循环结束，此时所有地区已覆盖完毕。
代码：

package com.liu.algorithm;
 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
 
/**
 * @author liuweixin
 * @create 2021-09-23 15:37
 */
//贪心算法—集合覆盖问题
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //先创建对应的广播台集合
        HashMap<String, HashSet<String>> broadcasts = new HashMap();
        //创建对应的广播
        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("大连");
        broadcasts.put("k1", hashSet1);
        broadcasts.put("k2", hashSet2);
        broadcasts.put("k3", hashSet3);
        broadcasts.put("k4", hashSet4);
        broadcasts.put("k5", hashSet5);
        //创建一个集合，记录最终的广播台
        ArrayList<String> selects = new ArrayList<>();
        //创建一个集合，记录要覆盖的地区
        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        //创建一个最大覆盖的指针
        String maxSize;
        HashSet<String> temp = new HashSet<>();//借用一个临时的hashSet变量，用来存储交集
        while (allAreas.size() != 0) {//当要覆盖的区域还不等于0时，说明还没有选择完广播台，继续循环
            maxSize = null;
            for (String key : broadcasts.keySet()) {//遍历广播台的数据
                temp.clear();//将临时的变量置空
                temp.addAll(broadcasts.get(key));//将当前广播台覆盖的地区添加到临时变量中
                temp.retainAll(allAreas);//找到当前变量与总地区重合的地区数
                //这里体现贪心算法，每一步都选取最优的选择
                if (temp.size() > 0 && maxSize == null) {
                    maxSize = key;
                } else if (temp.size() > 0 && maxSize != null) {
                    HashSet<String> max = broadcasts.get(maxSize);//获取最大覆盖指针指向的广播台
                    max.retainAll(allAreas);//获取其与总地区重合的地区数
                    if (temp.size() > max.size()) {
                        //如果当前遍历的广播台的包含数大于指针指向的包含数，则指针指向当前key
                        maxSize = key;
                    }
                }
            }
            if (maxSize != null) {
                //当for循环结束，找到覆盖最多的广播台
                selects.add(maxSize);
                //并且在allAreas中删除maxSize所指向的地区
                allAreas.removeAll(broadcasts.get(maxSize));
            }
 
        }
        System.out.println(selects);
    }
}