Java 資料結構與演算法系列精講之貪婪演演算法

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

public class 貪婪演演算法 {

    // 集合, 存放廣播臺
    static HashMap<String, HashSet<String>> broadcasts = new HashMap<>();

    // 集合, 存放地區
    static HashSet<String> areas = new HashSet<String>();

    // 貪婪演演算法
    public static ArrayList<String> Greedy() {

        // 建立陣列存放結果
        ArrayList<String> selects = new ArrayList<>();

        // 迴圈直至地區都覆蓋
        while (areas.size() != 0) {

            // 存放交集最大的廣播臺
            String maxKey = null;

            // 存放交集最大的值
            int maxKeySize = 0;

            // 遍歷每個剩餘電臺
            for (String key : broadcasts.keySet()) {

                // 取出交集個數
                int currSize = getRetainSize(key);

                // 替換當前最大
                if (currSize > 0 && currSize > maxKeySize) {
                    maxKey = key;
                    maxKeySize = currSize;
                }
            }


            // 新增廣播臺到結果
            selects.add(maxKey);

            // 移除廣播臺
            areas.removeAll(broadcasts.get(maxKey));
        }

        return selects;
    }

    // 剩餘數量
    public static int getRetainSize(String key) {

        // 如果為空返回0
        if (key == null) return 0;

        // 存放key對應的地區集合
        HashSet<String> tempSet = new HashSet<>();

        // 取key對應的地區
        tempSet.addAll(broadcasts.get(key));

        // 取交集
        tempSet.retainAll(areas);

        return tempSet.size();
    }

    public static void main(String[] args) {

//        | K1 | 北京, 上海, 天津 |
//        | K2 | 北京, 廣州, 深圳 |
//        | K3 | 上海, 杭州, 成都 |
//        | K4 | 上海, 天津 |
//        | K5 | 杭州, 大連 |


        // 建立廣播臺
        HashSet<String> K1 = new HashSet<>(Arrays.asList("北京", "上海", "天津"));
        HashSet<String> K2 = new HashSet<>(Arrays.asList("北京", "廣州", "深圳"));
        HashSet<String> K3 = new HashSet<>(Arrays.asList("上海", "杭州", "成都"));
        HashSet<String> K4 = new HashSet<>(Arrays.asList("上海", "天津"));
        HashSet<String> K5 = new HashSet<>(Arrays.asList("杭州", "大連"));

        // 加入map
        broadcasts.put("K1", K1);
        broadcasts.put("K2", K2);
        broadcasts.put("K3", K3);
        broadcasts.put("K4", K4);
        broadcasts.put("K5", K5);

        areas.addAll(K1);
        areas.addAll(K2);
        areas.addAll(K3);
        areas.addAll(K4);
        areas.addAll(K5);

        // 偵錯輸出
        System.out.println(broadcasts);
        System.out.println(areas);

        ArrayList<String> result = Greedy();
        System.out.println(result);
    }
}