贪心算法

1. 每次选择组好的方案

public class GreedyAlgorithm {

    public static void main(String[] args) {
        GreedyAlgorithm ga = new GreedyAlgorithm();
        Map<String, Set<String>> m = new HashMap<>();
        Set<String> s1 = new HashSet<>();
        s1.add("北京");
        s1.add("上海");
        s1.add("天津");
        Set<String> s2 = new HashSet<>();
        s2.add("广州");
        s2.add("北京");
        s2.add("深圳");
        Set<String> s3 = new HashSet<>();
        s3.add("成都");
        s3.add("上海");
        s3.add("杭州");
        Set<String> s4 = new HashSet<>();
        s4.add("上海");
        s4.add("天津");
        Set<String> s5 = new HashSet<>();
        s5.add("杭州");
        s5.add("大连");
        m.put("K1", s1);
        m.put("K2", s2);
        m.put("K3", s3);
        m.put("K4", s4);
        m.put("K5", s5);
        Set<String> all = new HashSet<>();
        all.add("北京");
        all.add("上海");
        all.add("天津");
        all.add("广州");
        all.add("成都");
        all.add("杭州");
        all.add("大连");
        all.add("深圳");
        List<String> greedy = ga.greedy(m, all);
        System.out.println(greedy);
    }


    public List<String> greedy(Map<String, Set<String>> m, Set<String> s) {
        List<String> newS = new ArrayList<>();
        Set<String> temp = new HashSet<>();
        String max = null;
        while (s.size() != 0) {
            for (String key : m.keySet()) {
                temp.clear();
                Set<String> value = m.get(key);
                temp.addAll(value);
                temp.retainAll(s);
                if (temp.size() > 0 && (max == null || m.get(max).size() < temp.size())) {
                    max = key;
                }
            }
            if (max != null) {
                newS.add(max);
                s.removeAll(m.get(max));
                max = null;
            }
        }
        return newS;
    }
}