总目录：地址如下看总纲

https://www.jianshu.com/p/929ca9e209e8

1、应用场景-集合覆盖问题

假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号

image.png

2、贪心算法介绍

（1）贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法

（2）贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
（如果价格，考虑的话，那么可能对于价格，做不到最优；只有方案配对最优【毕竟不是综合考虑的】）

3、解决方案（举例两类：穷举法，贪心算法）

（1）穷举法：
如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现,列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有�2ⁿ -1 个,假设每秒可以计算10个子集， 如图:

image.png

（2）贪心算法最佳应用-集合覆盖的思路分析：

目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合，具体步骤如下：

<1>遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）--- 此集合大多时候是一个 或者 多个组合的 集合 ，这里的 "个" 指的是广播台 K1,K2....

<2>将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉

<3>重复第1步直到覆盖了全部的地区

4、贪心算法图解：

说明：
allAreas 为需要覆盖所有广播台内的地区，
selects = ArrayList () 为最终集合（将需要被覆盖的广播台集合汇总）
maxKey 指向当前 包含 地区最多的广播台，若大小一样依照顺序（用于剔除 allAreas 中的地区，符合就剔除）
key 用于指向每一个广播台，依次移动 查询 和 allAreas 中的覆盖地区个数

步骤：
（1）刚开始 selects 没有任何广播台 ，allAreas 列出所有（暂时未被剔除），k1 到 k5 覆盖地区个数分别为
3，3，3，2，2

image.png

（2）当 maxKey 指向 k1 后，K1 装入 selcts 集合 ，K1 中的地区 剔除匹配到 allAreas 中的地区

image.png

（3）此时个数最大的是 k2,k3,k5 ，按照顺序优先指向 K2 。然后开始如上操作， maxKey 指向 K2,K2装入 selects集合， K2 中的地区 剔除 匹配到 allAreas 中的地区

image.png

（4）此时地区个数最大的广播台是 k3 , k5 按照顺序 优先 k3。同上 ，maxKey 指向 k3, k3 装入 selects 集合， k3 中的地区匹配到 allAreas 中的地区 并剔除

image.png

（5）此时最大地区个数只有 k5 ，同，maxKey 指向 k5 ，k5 装入 selects 集合，k5 中的地区匹配到 allAreas中的地区并 剔除，此时所有都已经覆盖到， selects 为最终

image.png

5、贪心算法代码实现

/*
 * @Description:    贪心算法 -- 实现广播问题
 * @Author:         阿K
 * @CreateDate:     2021/2/7 16:30
 * @Param:          
 * @Return:          
**/
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);

        //allAreas 存放所有的地区
        HashSet<String> allAreas = obtainAllAreas (broadcasts);

        //创建ArrayList, 存放选择的电台集合(最终答案)
        ArrayList<String> selects = new ArrayList<> ( );

        //定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
        HashSet<String> tempSet = new HashSet<> ( );// 可以理解为不断变动的 allAreas

        // 定义maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
        // 若 maxKey 不为null ,则会加入到 selects
        String maxKey = null;

        while (allAreas.size ( ) != 0) {// 若 allAreas 不为 0，则表示还没有覆盖到所有地区（既没有全部剔除完）

            // maxKey 每次重新指向，都需要重置一次
            maxKey = null;

            // 遍历 broadcasts, 取出对应key
            for (String key : broadcasts.keySet ( )) {
                // 每次操作前 清空一次辅助集合
                tempSet.clear ( );
                // 当前 key(广播台)，所能覆盖的地区
                HashSet<String> areas = broadcasts.get (key);
                // 拷贝到 辅助集合
                tempSet.addAll (areas);
                // 求出 tempSet 和 allAreas 的交集，并赋值于 tempSet
                tempSet.retainAll (allAreas);
                // 若当前这个集合（广播台），包含的未覆盖地区的数量，比maxKey指向的集合地区还要多
                // 则需要重置 maxKey
                // tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
                if (tempSet.size ( ) > 0 && (maxKey == null || tempSet.size ( ) > broadcasts.get (maxKey).size ( ))) {
                    maxKey = key;
                }
            }

            // maxKey != null, 就应该将maxKey 加入selects
            if (maxKey != null) {
                selects.add (maxKey);
                // 将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉(剔除)
                allAreas.removeAll (broadcasts.get (maxKey));
            }
        }

        System.out.println ("得到的选择结果是" + selects);//[K1,K2,K3,K5]
    }

    // 获取所有广播电台地区
    private static HashSet<String> obtainAllAreas(HashMap<String, HashSet<String>> broadcasts) {
        if (broadcasts != null && broadcasts.size ( ) > 0) {

            HashSet<String> allAreas = new HashSet<> ( );
            Set<String> keys = broadcasts.keySet ( );
            for (String key : keys) {
                HashSet<String> all = broadcasts.get (key);
                for (String region : all) {
                    // 因 HashSet 会覆盖，所以无需判断
                    allAreas.add (region);
                }
            }
            return allAreas;
        }
        return null;
    }
}

6、贪心算法注意事项和细节

（1）贪心算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
（2）比如上题的算法选出的是K1, K2, K3, K5，符合覆盖了全部的地区
（3）但是我们发现 K2, K3,K4,K5 也可以覆盖全部地区，如果K2 的使用成本低于K1,那么我们上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的

7、仓库坐标

image.png