07-贪心算法

public class TanXin {

    public static void main(String[] args) {
        // 电台集合
        HashMap> hashMap = new HashMap<>();
        HashSet k1 = new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        HashSet k2 = new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");
        HashSet k3 = new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        HashSet k4 = new HashSet<>();
        k4.add("上海");
        k4.add("天津");
        HashSet k5 = new HashSet<>();
        k5.add("杭州");
        k5.add("大连");

        hashMap.put("k1", k1);
        hashMap.put("k2", k2);
        hashMap.put("k3", k3);
        hashMap.put("k4", k4);
        hashMap.put("k5", k5);

        // 所有需要获得的城市
        HashSet allCity = new HashSet<>();
        for (String key : hashMap.keySet()) {
            HashSet strings = hashMap.get(key);
            allCity.addAll(strings);
        }

        // 选择的电台
        HashSet select = new HashSet<>();
        // 最优选择的key
        String maxSizeKey = null;
        int maxSizeLen = 0;

        while (allCity.size() != 0) {
            maxSizeLen = 0;
            maxSizeKey = null;


            for (String key : hashMap.keySet()) {
                HashSet citys = hashMap.get(key);
                int includeSize = includeSize(allCity, citys);
                if (includeSize > maxSizeLen) {
                    maxSizeLen = includeSize;
                    maxSizeKey = key;
                }
            }

            if (maxSizeKey != null && maxSizeLen != 0) {
                select.add(maxSizeKey);
                allCity.removeAll(hashMap.get(maxSizeKey));
            }
        }


        System.out.println(select);
    }

    
    public static int includeSize(HashSet allCity, HashSet citys) {
        int count = 0;
        for (String city : citys) {
            if (allCity.contains(city)) {
                count++;
            }
        }
        return count;
    }
}