贪心算法

应用场景-集合覆盖问题

假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号

贪心算法介绍

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法

（福利推荐：阿里云、腾讯云、华为云服务器最新限时优惠活动，云服务器1核2G仅88元/年、2核4G仅698元/3年，点击这里立即抢购>>>）

贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果

代码示例

package com.wxit.greedy;  import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet;  /**  * @Author wj  * 贪心算法  **/ public class GreedyAlgorithm {      public static void main(String[] args) {         //创建广播电台，放入到Map中         HashMap<String, HashSet<String>> broadcasts = new HashMap<>();         //将各个电台放入到broadcasts         HashSet<String> hashSet1 = new HashSet<>();         hashSet1.add("北京");         hashSet1.add("上海");         hashSet1.add("天津");          HashSet<String> hashSet2 = new HashSet<>();         hashSet2.add("广州");         hashSet2.add("北京");         hashSet2.add("深圳");          HashSet<String> hashSet3 = new HashSet<>();         hashSet3.add("成都");         hashSet3.add("上海");         hashSet3.add("杭州");          HashSet<String> hashSet4 = new HashSet<>();         hashSet4.add("上海");         hashSet4.add("天津");          HashSet<String> hashSet5 = new HashSet<>();         hashSet4.add("杭州");         hashSet4.add("大连");          //加入到map         broadcasts.put("k1",hashSet1);         broadcasts.put("k2",hashSet2);         broadcasts.put("k3",hashSet3);         broadcasts.put("k4",hashSet4);         broadcasts.put("k5",hashSet5);          //allAreas,存放所有的地区         HashSet<String> allAreas = new HashSet<String>();         allAreas.add("北京");         allAreas.add("上海");         allAreas.add("天津");         allAreas.add("广州");         allAreas.add("深圳");         allAreas.add("成都");         allAreas.add("杭州");         allAreas.add("大连");          //创建ArrayList，存放选择的集合         ArrayList<String> selects = new ArrayList<String>();          //定义一个临时的集合,在遍历的过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集         HashSet<String> tempSet = new HashSet<>();          //定义给maxKey，保存在一次遍历过程中，能够覆盖最大未覆盖的地区的电台key，如果key不为空，则会加入到selects         String maxKey = null;         while (allAreas.size() != 0){ //如果allAreas不为0，则表示还没有覆盖到所有的地区             //每进行一次while，需要             maxKey = null;             //遍历broadcasts，取出对应的key             for (String key : broadcasts.keySet()) {                 //每进行一次for                 tempSet.clear();;                 //当前这个key能够覆盖的地区                 HashSet<String> areas = broadcasts.get(key);                 tempSet.addAll(areas);                 //求出temSet和allAreas集合的交集,交集会赋给temSet                 tempSet.retainAll(allAreas);                 //如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多，就需要重置maxKey                 if (tempSet.size() > 0 && (tempSet.size() > broadcasts.get(maxKey).size())){                     maxKey = key;                 }             }             //maxKey != null,就应该将maxKey加入selects             if (maxKey != null){                 selects.add(maxKey);                 //将maxKey指向的广播电台的地区从allAreas去掉                 allAreas.removeAll(broadcasts.get(maxKey));             }         }         System.out.println("得到的选择结果为:" + selects);     } } 

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)