/**
 * 貪心算法實現集合覆蓋
 */
public class Demo {
    public static void main(String[] args) {
        // 創(chuàng)建電臺和地區(qū)集合
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        // 創(chuàng)建各個電臺
        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);
        // 建立各個地區(qū)的集合
        HashSet<String> allAreas = new HashSet<>();
        for (Map.Entry<String, HashSet<String>> entry : broadcasts.entrySet()) {
            HashSet<String> value = entry.getValue();
            allAreas.addAll(value);
        }
        // 創(chuàng)建選擇的電臺的集合
        ArrayList<String> broadSelect = new ArrayList<>();
        // 定義一個臨時的集合
        HashSet<String> tempSet = new HashSet<>();
        // 定義一個指針，用于指向當前最優(yōu)
        String maxKey = null;
        while (allAreas.size() > 0) {
            // 重置置空
            maxKey = null;
            // 遍歷
            for (String key : broadcasts.keySet()) {
                // 重置置空
                tempSet.clear();
                HashSet<String> value = broadcasts.get(key);
                tempSet.addAll(value);
                // 求出temp和allAreas的交集
                tempSet.retainAll(allAreas);
                // 如果當前選擇有覆蓋地區(qū)
                if (tempSet.size() > 0 &&
                        // 此時，如果maxKey還沒有指向就指向
                        (maxKey == null ||
                                // 如果maxKey已經有指向就比較誰最優(yōu)解
                                (tempSet.size() > (broadcasts.get(maxKey).size())))) {
                    maxKey = key;
                }
            }
            if (maxKey != null) {
                // 將maxKey加入
                broadSelect.add(maxKey);
                // 并將allAreas去掉maxKey能覆蓋的地區(qū)
                allAreas.removeAll(broadcasts.get(maxKey));
        // 打印結果
        System.out.println(broadSelect);
    }
}

package azhong.greedy_algo;

import java.util.*;
/**
 * 貪心算法
 * 在對問題求解時，在每一步都選擇最好的選擇，從而希望得到最好的結果。
 */
public class GreedyAlgoDemo {
    public static void main(String[] args) {
        //每個電臺覆蓋的區(qū)域
        Map<String,HashSet<String>> allStations = initRadioStation();
        //需要覆蓋的所有區(qū)域
        HashSet<String> allAreas = getAllAreas(allStations);
        //存放選擇的電臺
        List<String> selectedStations = new ArrayList<>();
        while (allAreas.size()>0) {
            //遍歷所有廣播臺，找到了個覆蓋了最多未覆蓋的地區(qū)的電臺
            int maxIndex=0;
            String maxK=null;
            HashSet<String> areaInMaxK=null;
            for (Map.Entry<String, HashSet<String>> entry : allStations.entrySet()) {
                final String k = entry.getKey();
                HashSet<String> values = entry.getValue();
                //當前電臺在所有區(qū)域覆蓋的個數
                int c = testIntersectionOfSet(values, allAreas);
                System.out.println(k + " 在所有區(qū)域覆蓋的個數: " + c);
                if(c>maxIndex){
                    maxIndex=c;
                    maxK=k;
                    areaInMaxK=values;
                }
            }
            if(maxK!=null){
                //選擇最大覆蓋數k1加入到選擇的電臺{k1}，
                selectedStations.add(maxK);
                //將k1（北京、上海、天津）從所覆蓋的區(qū)域從所有區(qū)域中移除，所有區(qū)域更新為：{山東、深圳、成都、杭州、武漢};
                allAreas.removeAll(areaInMaxK);
                //重置，進入下一次循環(huán)
                maxIndex=0;
                maxK=null;
                areaInMaxK=null;
                System.out.println("****************************");
        }
        System.out.println(selectedStations);
    }
    /**
     * 測試：求兩個集合的交集
     * A{北京、上海、天津}
     * B{北京、上海、天津、山東、深圳、成都、杭州、武漢}
     * A.retainAll(B); 得到A{北京、上海、天津} 個數為3
     */
    private static int testIntersectionOfSet(HashSet A,HashSet B){
        //將存在于集合A中但不存在于集合B中的元素移除。
        A.retainAll(B);
        return A.size();
     * 初始化電臺
     * k1廣播臺覆蓋的區(qū)域有：北京、上海、天津
     * k2廣播臺覆蓋的區(qū)域有：北京、山東、深圳
     * k3廣播臺覆蓋的區(qū)域有：成都、上海、杭州
     * k4廣播臺覆蓋的區(qū)域有：上海、天津
     * k5廣播臺覆蓋的區(qū)域有：杭州、武漢
     * @return Map<String,HashSet<String>>類型電臺集合
    private static Map<String,HashSet<String>> initRadioStation(){
        Map<String,HashSet<String>> allStations = new HashMap<String,HashSet<String>>();
        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("武漢");
        allStations.put("k1",k1);
        allStations.put("k2",k2);
        allStations.put("k3",k3);
        allStations.put("k4",k4);
        allStations.put("k5",k5);
        return allStations;
    private static HashSet<String> getAllAreas(Map<String,HashSet<String>> allStations){
        HashSet<String> allAreas = new HashSet<>();
        Collection<HashSet<String>> stations = allStations.values();
        for(HashSet<String> station:stations){
            Iterator<String> areas = station.iterator();
            //操泥瑪，寫成了if
            while (areas.hasNext()){
                allAreas.add(areas.next());
        return allAreas;
}