算法-贪心算法

1.算法介绍
贪心算法是指对问题进行求解时，在每一步选择中都采取最好或者最优的选择，从而希望能够导致结果是最好的或者最优的算法。
所得结果不一定是最优结果（有时是最优解），但是都是相对近似的最优解。

2.应用分析

思路分析：

• 1.覆盖问题使用穷举法 排列组合 n个电台 有2^n - 1中组合方式， 幂集型数量太大 不适合处理

• 2.贪心算法：策略，需要覆盖全部地区的最小集合：
  首先将所有地区存放到allList中;
  遍历所有的电台，找到一个覆盖最多未覆盖的地区的电台;
  将这个电台加入集合中list中,并且将allList中当前电台覆盖的地区删除掉;
  重复第二步，直到覆盖了全部地区;

  

3.代码实现

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("大连");

        broadcasts.put("K1",hashSet1);
        broadcasts.put("K2",hashSet2);
        broadcasts.put("K3",hashSet3);
        broadcasts.put("K4",hashSet4);
        broadcasts.put("K5",hashSet5);

        //存放所有地区
        HashSet<String> allAreas = new HashSet<>();
        Collection<HashSet<String>> values = broadcasts.values();
        for(HashSet<String> va : values){
            allAreas.addAll(va);
        }

        //创建arrayList 存放选择的电台集合
        List<String> selects = new ArrayList<>();

        //定义临时集合 保存在遍历过程中的交集
        HashSet<String> tempSet = new HashSet<>();

        //定义一个maxKey 保存在一次遍历过程中能够覆盖的最多的未覆盖地区的电台的key
        String maxKey = null;

        while (allAreas.size() != 0){ // != 0 证明还需要继续遍历
            maxKey = null;
            for(String key:broadcasts.keySet()){
                //每次循环 都要清空List
                tempSet.clear();
                HashSet<String> areas = broadcasts.get(key);
                tempSet.addAll(areas);
                //求交集 复制到tempSet
                tempSet.retainAll(allAreas);
                //如果当前这个集合包含的未覆盖的地区数量 比maxKey指向的集合地区多 则重置maxKey
                if(tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size()) ){
                    maxKey = key;
                }
            }
            if(maxKey != null){
                selects.add(maxKey);
                //将maxKey指向的地区 在allAreas中去掉
                allAreas.removeAll(broadcasts.get(maxKey));
            }
        }

        System.out.println("电台集合："+ selects);
    }