[数据结构与算法]【数据结构与算法】贪心算法的介绍和集合覆盖问题程序实现

1. 贪心算法的介绍

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优或者最有利的选择，从而得到导致结果局部最好或者局部最优的算法，但是效率高

2. 集合覆盖问题介绍

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

3. 集合覆盖问题思路分析

1. 先将所有地区添加到一个集合notCoverdAreas
2. 然后遍历所有广播电台，找到一个电台，该电台覆盖地区和notCoverdAreas的相同地区个数最多
3. 遍历完成后，将该电台添加到已找到的电台集合findedBroadcasts，然后将该电台覆盖地区从notCoverdAreas删掉
4. 重复步骤2， 直到notCoverdAreas为空，表示覆盖了所有地区

4. 集合覆盖问题程序实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class GreedyAlgorithm {

    public static void main(String[] args) {
        // key为广播电台, value为该电台覆盖的地区
        HashMap<String, HashSet<String>> broadcastCoveredAreaMap = new HashMap<String, HashSet<String>>();

        //将各个电台放入到broadcasts
        HashSet<String> hashSet1 = new HashSet<String>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");
        broadcastCoveredAreaMap.put("B1", hashSet1);

        HashSet<String> hashSet2 = new HashSet<String>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");
        broadcastCoveredAreaMap.put("B2", hashSet2);

        HashSet<String> hashSet3 = new HashSet<String>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");
        broadcastCoveredAreaMap.put("B3", hashSet3);

        HashSet<String> hashSet4 = new HashSet<String>();
        hashSet4.add("上海");
        hashSet4.add("天津");
        broadcastCoveredAreaMap.put("B4", hashSet4);

        HashSet<String> hashSet5 = new HashSet<String>();
        hashSet5.add("杭州");
        hashSet5.add("大连");
        broadcastCoveredAreaMap.put("B5", hashSet5);

        // 保存还未覆盖的地区
        HashSet<String> notCoverdAreas = new HashSet<String>();
        notCoverdAreas.add("北京");
        notCoverdAreas.add("上海");
        notCoverdAreas.add("天津");
        notCoverdAreas.add("广州");
        notCoverdAreas.add("深圳");
        notCoverdAreas.add("成都");
        notCoverdAreas.add("杭州");
        notCoverdAreas.add("大连");

        // 保存已找到的电台集合
        ArrayList<String> findedBroadcasts = new ArrayList<String>();

        // 定义一个tmpSet，在遍历过程中，保存一个电台覆盖的地区和notCoverdAreas的相同地区
        HashSet<String> tmpSameAreaSet = new HashSet<String>();

        // 在一次遍历过程中，如果一个电台覆盖的地区和notCoverdAreas的相同地区个数最多，则保存该电台
        String tmpMaxSameAreaBroadcast = null;
        // 保存一个电台覆盖的地区和notCoverdAreas的相同地区个数
        int tmpMaxSameAreaNum = 0;

        // 表示还有地区没有被覆盖
        while (notCoverdAreas.size() != 0) {
            // 每找一个电台，需要将tmpMaxSameAreaBroadcast初始化为null
            tmpMaxSameAreaBroadcast = null;
            // 也初始化为0
            tmpMaxSameAreaNum = 0;

            // 遍历进行处理
            for (String broadcast : broadcastCoveredAreaMap.keySet()) {
                // 每一次都需要将tmpSameAreaSet清空
                tmpSameAreaSet.clear();

                // 当前广播覆盖的地区
                HashSet<String> coveredAreas = broadcastCoveredAreaMap.get(broadcast);
                tmpSameAreaSet.addAll(coveredAreas);
                // 得到当前广播覆盖的地区和notCoverdAreas的相同地区，然后清空tmpSameAreaSet并将结果保存到tmpSameAreaSet
                tmpSameAreaSet.retainAll(notCoverdAreas);

                // 如果有该电台还有未覆盖的地区，并且{还未找到目标电台，或该电台未覆盖的地区个数大于上一个临时目标电台的未覆盖地区的个数}
                // 则该电台为临时的目标电台
                if (tmpSameAreaSet.size() > 0 &&
                        (tmpMaxSameAreaBroadcast == null || tmpSameAreaSet.size() > tmpMaxSameAreaNum)) {
                    tmpMaxSameAreaBroadcast = broadcast;
                    tmpMaxSameAreaNum = tmpSameAreaSet.size();
                }
            }

            // 表示已找到一个电台，该电台未覆盖的地区个数最大
            if (tmpMaxSameAreaBroadcast != null) {
                findedBroadcasts.add(tmpMaxSameAreaBroadcast);
                // 将该电台的覆盖地区，从notCoverdAreas删掉
                notCoverdAreas.removeAll(broadcastCoveredAreaMap.get(tmpMaxSameAreaBroadcast));
            }
        }

        // 输出所有电台的信息
        System.out.println(broadcastCoveredAreaMap);
        // 输出选择的电台
        // HashMap输出的顺序和我们插入数据的顺序可能不一样
        System.out.println("选择的电台是：" + findedBroadcasts);

    }

}

运行程序，结果如下：

{B2=[广州, 北京, 深圳], B3=[成都, 上海, 杭州], B4=[上海, 天津], B5=[大连, 杭州], B1=[上海, 天津, 北京]}
选择的电台是：[B2, B3, B4, B5]