Day 16 贪心算法

贪心算法 指在对问题求解时 每一步都采用最优选择 从而希望导致结果是最优的（贪婪算法的结果不一定是最优的 但都是近似于最优的）

例子 电台覆盖问题

package 贪心;

import java.security.KeyStore;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;

public class Greed {
    //贪心算法
    public static void main(String[] args) {
        //电台覆盖问题
        HashMap> diantai = new HashMap>();//电脑 键是电台名 值是电台覆盖地区的集合
        HashSet fg1 = new HashSet();//电台k1覆盖的地区
        fg1.add("北京");
        fg1.add("上海");
        fg1.add("天津");
        diantai.put("k1",fg1);
        HashSet fg2 = new HashSet();//电台k2覆盖的地区
        fg2.add("广州");
        fg2.add("北京");
        fg2.add("深圳");
        diantai.put("k2",fg2);
        HashSet fg3 = new HashSet();//电台k3覆盖的地区
        fg3.add("成都");
        fg3.add("上海");
        fg3.add("杭州");
        diantai.put("k3",fg3);
        HashSet fg4 = new HashSet();//电台k4覆盖的地区
        fg4.add("上海");
        fg4.add("天津");
        diantai.put("k4",fg4);
        HashSet fg5 = new HashSet();//电台k5覆盖的地区
        fg5.add("杭州");
        fg5.add("大连");
        diantai.put("k5",fg5);
        //获取所有地区
        HashSet diqu = new HashSet();
        for (Map.Entry d:diantai.entrySet()){
//            HashSet temp = (HashSet) d.getValue();
//            System.out.println(temp);
//            Iterator t = temp.iterator();
//            while (t.hasNext()){
//                System.out.println(t.next());
//            }
            diqu.addAll((HashSet) d.getValue());
        }
        //这个集合用来记录挑选了那些电台
        HashSet jl = new HashSet();
        //这个集合用来暂存当前电台覆盖地区 以便比较
        HashSet zc = new HashSet();

        while (diqu.size()!=0){//当 未覆盖地区不为空时
            String max = null;
            zc.clear();
            int maxSize = 0;//用来记录当前max保存的集合的未覆盖地区的数量
            for (String dq : diantai.keySet()){//轮流取出所有电台覆盖地区
                System.out.println(dq);
                zc.addAll(diantai.get(dq));
                zc.retainAll(diqu);//使用zc集合 与 diqu集合比对筛重 比对过后会返回他们重复的部分
                System.out.println(zc);

                if (zc.size()>0 &&(max == null || zc.size()>maxSize)){

                    max = dq;
                    maxSize = zc.size();
                }
            }
            //如果记录的max不为null 证明里面判断到了
//            System.out.println(max);
            if (max!=null){
//                System.out.println(max);
                jl.add(max);
                diqu.removeAll(diantai.get(max));
            }
//            System.out.println(diqu);
        }
        System.out.println(jl);
    }
}