概述

• 贪心算法(Greedy algorithm), 又称贪婪算法. 此算法对问题进行求解时, 在每一步选择中都采取最好或者最优(即最有利)的选择, 从而希望能够导致结果是最好或者最优的算法

贪心算法最佳应用-集合覆盖

• 假设有多个需付费的广播台, 及各个广播台有限制, 只能传递信号到部分区域. 问题: 如何选择最少的广播台, 让所有的地区都可以接收到广播信号

* 贪心算法所得到的结果不一定是最优的结果(如 考虑到成本及其它因素), 但都是相对接近最优的结果

两种方式

1. 穷举算法: 此方式效率较低不推荐使用
2. 贪心算法: 效率较高, 建议使用

• 思路分析:

1. 遍历所有的广播电台, 找到一个覆盖了最多未覆盖地区的电台(此电台可能包含一些已覆盖的地区, 但没关系)
2. 将这个电台加入到一个集合中, 之后下次比较时, 所重复的区域去掉, 依次重复以上步骤, 直到覆盖全部地区

• 代码实现

public class GreedyAlgorithmApp {
    public static void main(String[] args) {
        HashMap<String, HashSet<String>> broadCasts = new HashMap<>();
        HashSet<String> k1 = new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        HashSet<String> k2 = new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");
        HashSet<String> k3 = new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        HashSet<String> k4 = new HashSet<>();
        k4.add("上海");
        k4.add("天津");
        HashSet<String> k5 = new HashSet<>();
        k5.add("杭州");
        k5.add("大连");
        broadCasts.put("K1",k1);
        broadCasts.put("K2",k2);
        broadCasts.put("K3",k3);
        broadCasts.put("K4",k4);
        broadCasts.put("K5",k5);

        HashSet<String> allAreas = new HashSet<>();
        allAreas.add("北京"); allAreas.add("上海"); allAreas.add("天津");
        allAreas.add("广州"); allAreas.add("深圳"); allAreas.add("成都");
        allAreas.add("杭州"); allAreas.add("大连");

        ArrayList<String> selects = new ArrayList<>();
        HashSet<String> tempSet = new HashSet<>();
        String maxkey;
        /** 遍历直到覆盖所有地区*/
        while (allAreas.size() != 0) {
            maxkey = null;
            /** 遍历所有电台*/
            for (String key : broadCasts.keySet()) {
                tempSet.clear();
                /** 取出当前电台所覆盖的地区集合*/
                HashSet<String> areas = broadCasts.get(key);
                tempSet.addAll(areas);
                // 求出 tempSet与 allAreas集合的交集, tempSet集合只留相同地区名称, 它的不同的地区名称会被移除
                tempSet.retainAll(allAreas);
                /**
                 * 如果 tempSet包含(未覆盖的)地区数量比 maxkey指向的地区集合(未覆盖的)地区多，就重置 maxkey*/
                if(tempSet.size() > 0 && (maxkey == null || tempSet.size() > broadCasts.get(maxkey).size())) {
                    maxkey = key;
                }
            }
            if (maxkey != null) {
                selects.add(maxkey);
                allAreas.removeAll(broadCasts.get(maxkey));
            }
        }
        System.out.println("结果为 " + selects);
    }

}

输出:
> 结果为 [K1, K2, K3, K5]

如果您觉得有帮助，欢迎点赞哦 ~ 谢谢!!