常用算法练习---贪心算法

package commonlyalgorithm.greedalgorithm;

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

/**
 * 贪心算法
 *
 * 可以用来求解最少元素覆盖最大面积之类的问题
 * 再次举例计算选用最少的电台达到要求覆盖的城市全部覆盖的目标
 */
public class GreedAlgorithm {

    public static void main(String[] args) {

        //用来保存电台信息的map
        Map<String , HashSet<String>> radioStation = new HashMap<>();

        HashSet<String> nameSet1 = new HashSet<>();
        nameSet1.add("北京");
        nameSet1.add("上海");
        nameSet1.add("天津");

        HashSet<String> nameSet2 = new HashSet<>();
        nameSet2.add("广州");
        nameSet2.add("北京");
        nameSet2.add("深圳");

        HashSet<String> nameSet3 = new HashSet<>();
        nameSet3.add("成都");
        nameSet3.add("上海");
        nameSet3.add("杭州");

        HashSet<String> nameSet4 = new HashSet<>();
        nameSet4.add("上海");
        nameSet4.add("天津");

        HashSet<String> nameSet5 = new HashSet<>();
        nameSet5.add("杭州");
        nameSet5.add("大连");

        radioStation.put("K1" , nameSet1);
        radioStation.put("K2" , nameSet2);
        radioStation.put("K3" , nameSet3);
        radioStation.put("K4" , nameSet4);
        radioStation.put("K5" , nameSet5);

        //创建保存所有地区信息的集合
        HashSet<String> allArea = new HashSet<>();
        allArea.add("北京");
        allArea.add("上海");
        allArea.add("天津");
        allArea.add("广州");
        allArea.add("深圳");
        allArea.add("成都");
        allArea.add("杭州");
        allArea.add("大连");

        //创建保存结果的list
        ArrayList<String> selectedList = new ArrayList<>();

        //声明一个临时的hash集合用来保存   遍历过程中的回结果
        HashSet<String> tempSet = new HashSet<>();

        //声明一个空串用来储存临时的最大值
        String maxKey = null;

        //循环求解  每当找到匹配的电台后就把地名从集合中删除，直到集合为空，循环结束
        while (allArea.size() != 0){
            //每次大循环前都需要将maxKey置为空
            maxKey = null;
            //循环遍历每一个电台  并将值付给临时的set集合
            for (String key : radioStation.keySet()) {
                //每次小循环开始前需要将tempSet清空
                tempSet.clear();
                HashSet areas = radioStation.get(key);
                tempSet.addAll(areas);
                //找出临时集合与全部地区集合的交集
                tempSet.retainAll(allArea);
                //判断条件并给maxKey赋值，经过多次循环后找到符合条件的最大值  此处体现贪心算法的核心思想
                //当符合条件的地区集合不为空且maxKry并未被赋值或者当前电台符合条件的值大于上一个符合条件的电台的值时 将其交换
                if(tempSet.size() > 0 && (maxKey == null || tempSet.size() > radioStation.get(maxKey).size())){
                    maxKey =  key;
                }
            }
            //如果maxKey不为空，则将maxKey加入结果集，并将地域集合中maxKey所代表的区域删除
            if(maxKey != null){
                selectedList.add(maxKey);
                allArea.removeAll(radioStation.get(maxKey));
            }
        }

        //循环结束显示结果   其结果并议定为最优结果，可能为最优结果中的一种
        System.out.println("结果为： " + selectedList);

    }

}