logo图片
数据结构与算法

贪心算法

什么是贪心算法

贪婪算法(贪心算法)是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致结果是最好或者最优的算法
算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果
以上面的问题问题,若使用贪心算法求出的结果,有时候不一定是最优的结果,因为有可能成本问题不是最好的,但是它是相对接近最优解的。
假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区。
如何选择最少的广播台,让所有的地区都可以接收到信号
贪心算法1
那么这个问题我们使用什么方式解决呢?答:贪心算法

通过示例认识贪心算法

采用上面的问题,我们还是从穷举法方法开始,选择最少的广播台,让所有的地区都可以接收到信号
假设我们现在有n个广播台,那么我们使用穷举法的方式先列举每个可能的集合
贪心算法2
我们就可以这种穷举法的方法推导出,n个广播台,他的组合集为2^-1,当然也可不必 -1 因为还有一种选择方式是:空集,什么都不选
贪心算法3
假设我们采用这种方式去做,那么所需要的时间就太多太多了,效率非常的低,而且到达100台,就算不下了。 使用贪心算法思路分析
贪心算法4
1.列举需要覆盖的城市:北京、上海、天津、广州、深圳、成都、杭州、大连
2.列举出每个广播电视台的覆盖地区数量
贪心算法5
3.每次找到广播台的覆盖地区数量值最大,取名naxKey
4.下一次比较的时候,去掉上次覆盖地区,重新找到naxKey

算法步骤思路分析

1.列举出所有城市,放入一个集合中
贪心算法6
2.进行第一轮的查找,假设K1 为覆盖地区数量值最大
贪心算法7
3.这时将K1对应的城市从集合中删除,进行下一轮比较
贪心算法8
4.进行下一轮的查找,假设K2 为覆盖地区数量值最大…接着以此类推
贪心算法9
5.一样的思路清除naxKey对应的城市…然后以此类推进行每轮比较

代码实现

按照我们的思路,我们先进行创建key 与对应的地区城市-
HashSet
   
     hashSet1 = new HashSet
    
     (); hashSet1.add("北京"); hashSet1.add("上海"); hashSet1.add("天津"); HashSet
     
       hashSet2 = new HashSet
      
       (); hashSet2.add("广州"); hashSet2.add("北京"); hashSet2.add("深圳"); HashSet
       
         hashSet3 = new HashSet
        
         (); hashSet3.add("成都"); hashSet3.add("上海"); hashSet3.add("杭州"); HashSet
         
           hashSet4 = new HashSet
          
           (); hashSet4.add("上海"); hashSet4.add("天津"); HashSet
           
             hashSet5 = new HashSet
            
             (); hashSet5.add("杭州"); hashSet5.add("大连"); //加入到map //创建广播电台,放入到Map HashMap
             
              > broadcasts = new HashMap
              
               >(); broadcasts.put("K1", hashSet1); broadcasts.put("K2", hashSet2); broadcasts.put("K3", hashSet3); broadcasts.put("K4", hashSet4); broadcasts.put("K5", hashSet5);
              
             
            
           
          
         
        
       
      
     
    
   
接下来我们将这些key的城市放入一个集合中存放
//allAreas 存放所有的地区
HashSet
   
     allAreas = new HashSet
    
     (); allAreas.add("北京"); allAreas.add("上海"); allAreas.add("天津"); allAreas.add("广州"); allAreas.add("深圳"); allAreas.add("成都"); allAreas.add("杭州"); allAreas.add("大连");
    
   
每一轮我们都能找到maxKey,我们需要存储这些maxKey,将他放入集合中
//创建ArrayList, 存放选择的电台集合
ArrayList
   
     selects = new ArrayList
    
     ();
    
   
当我们的K1、K2… 所负责的城市与allAreas 产生的交集,也需要记录下来
//定义一个临时的集合, 在遍历的过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
HashSet
   
     tempSet = new HashSet
    
     ();
    
   
同时,我们需要每次将对应的Kn放入tempSet里,与allAreas进行比较交集,若有则选择出来
//定义给maxKey , 保存在一次遍历过程中,能够覆盖最大未覆盖的地区对应的电台的key
//如果maxKey 不为null , 则会加入到 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
   
     areas = broadcasts.get(key);
        tempSet.addAll(areas);
        //求出tempSet 和   allAreas 集合的交集, 交集会赋给 tempSet
        tempSet.retainAll(allAreas);
        //如果当前这个集合包含的未覆盖地区的数量,比maxKey指向的集合地区还多
        //就需要重置maxKey
        // tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
        if(tempSet.size() > 0 &&
                (maxKey == null || 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));
    }
}

   

图解代码逻辑思路

1.初始化,将数据放入集合中
贪心算法10
2.找出当前K1、K2、K3、K4、K5中的maxKey,将它对应的城市放入tempSet
贪心算法11
3.将tempSet与allAreas 找出交集的数据
贪心算法12
4.将maxKey对应的城市从allAreas 删除,同时将maxKey添加进selects
贪心算法13
5.将maxKey 清空与tempSet 清空,进行新的maxKey寻找
贪心算法14
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4