算法 - 贪心算法(集合覆盖问题求解)

痛定思痛。 2023-07-03 12:03 148阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]  
1.穷举法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]  
2.贪心算法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 4]

# 遍历集合的key，用当前key的value和allAreas去取交集），然后和（maxKey和allAreas的交集）比较大小，如果当前key的结合size大就把当前key赋给maxkey，循环5次后退出循环，并把maxkey加入到selects，且把maxkey覆盖的地区从allAreas中移除。直到allAreas集合为空退出while循环，得到的select就是所需要的。 #

package Algorithm.greedy;
    
    import java.util.*;
    
    public class GreedyAlogrithm { 
        public static void main(String[] args) { 
            //创建广播电台，放入map
            HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
            //将各个电台放入
            HashSet<String> set1 = new HashSet<>();
            set1.add("北京");
            set1.add("上海");
            set1.add("天津");
            HashSet<String> set2 = new HashSet<>();
            set2.add("广州");
            set2.add("北京");
            set2.add("深圳");
            HashSet<String> set3 = new HashSet<>();
            set3.add("成都");
            set3.add("上海");
            set3.add("杭州");
            HashSet<String> set4 = new HashSet<>();
            set4.add("上海");
            set4.add("天津");
            HashSet<String> set5 = new HashSet<>();
            set5.add("杭州");
            set5.add("大连");
    
            //加入到map
            broadcasts.put("k1",set1);
            broadcasts.put("k2",set2);
            broadcasts.put("k3",set3);
            broadcasts.put("k4",set4);
            broadcasts.put("k5",set5);
    
            //创建一个存放所有城市的集合，就遍历集合就行
            HashSet<String> allAreas = new HashSet<>();
            for(Map.Entry<String, HashSet<String>> entry: broadcasts.entrySet())
            { 
                HashSet<String> value = entry.getValue();
                Iterator<String> iterator1 = value.iterator();
                while (iterator1.hasNext()){ 
                    allAreas.add(iterator1.next());
                }
            }
    
            //System.out.println(allAreas);
    
            //创建一个ArrayList存放选择后的 电台的集合
            ArrayList<String> selects = new ArrayList<>();
            //保存每次 当前覆盖的地区和未覆盖到的地区的交集，用retainAll()方法
            HashSet<String> tempSet = new HashSet<>();
            HashSet<String> value = new HashSet<>();
            //创建一个指针maxKey,存放交集最大的key
            String maxKey = null;
    
            while (allAreas.size() != 0){  //allAreas 不为空就表示没覆盖到所有地区
                maxKey = null;
    
                for (String key : broadcasts.keySet()) { 
                    tempSet.clear();
                    value.clear();
                    //存放Key覆盖的地区
                    value.addAll(broadcasts.get(key));
                    //tempSet.addAll(value);
                    //求当前key覆盖的地区和allAreas的交集
                    value.retainAll(allAreas);
                    //下面两步是取出maxKey覆盖地区和allAreas的交集
                    if (maxKey != null) { 
                        tempSet.addAll(broadcasts.get(maxKey));
                        tempSet.retainAll(allAreas);
                    }
    
                    if (value.size() > 0 && (maxKey == null || (value.size() > tempSet.size()))){ 
                        maxKey = key;
                    }
                }
                if (maxKey != null) { 
                    selects.add(maxKey);
                        allAreas.removeAll(broadcasts.get(maxKey));
                }
            }
    
            System.out.println(selects);
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200206111221672.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200206113433858.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200206113629788.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200206113948833.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200206132317355.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNjA4NA==,size_16,color_FFFFFF,t_70