算法_贪心_假设存在若干需要付费的广播台，已知广播台信号可以覆盖的地区，如何选择最少的广播台，让所有的地区都可以接收到信号

傷城~ 2023-07-12 11:41 37阅读 0赞

### 文章目录 ###

*  集合覆盖问题
 *  思路分析
 *  代码实现
 *  注意

# 集合覆盖问题 #

假设存在如下表的需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg_size_16_color_FFFFFF_t_70]

# 思路分析 #

1.  遍历所有的广播电台, 找到一个覆盖了**最多未覆盖**的地区的电台
2.  将这个电台加入到一个集合中, 把该电台覆盖的地区在下次比较时去掉
3.  重复第1步直到覆盖了全部的地区

# 代码实现 #

public class GreedyAlgorithm {
        
    
    	public static void main(String[] args) {
        
    		//创建广播电台,放入到Map
    		HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
    		//将各个电台放入到broadcasts
    		HashSet<String> hashSet1 = new HashSet<String>();
    		hashSet1.add("北京");
    		hashSet1.add("上海");
    		hashSet1.add("天津");
    
    		HashSet<String> hashSet2 = new HashSet<String>();
    		hashSet2.add("广州");
    		hashSet2.add("北京");
    		hashSet2.add("深圳");
    
    		HashSet<String> hashSet3 = new HashSet<String>();
    		hashSet3.add("成都");
    		hashSet3.add("上海");
    		hashSet3.add("杭州");
    
    		HashSet<String> hashSet4 = new HashSet<String>();
    		hashSet4.add("上海");
    		hashSet4.add("天津");
    
    		HashSet<String> hashSet5 = new HashSet<String>();
    		hashSet5.add("杭州");
    		hashSet5.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<String>();
    		// 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
    		while (allAreas.size() != 0) {
         
    		//maxKey 能够覆盖最大未覆盖的地区对应的电台的key
    		//如果maxKey 不为null , 则会加入到 selects
    			String maxKey = null;
    			//遍历 broadcasts, 取出对应key
    			for (String key : broadcasts.keySet()) {
        
    				//每进行一次for
    				tempSet.clear();
    				//当前这个key能够覆盖的地区
    				HashSet<String> areas = broadcasts.get(key);
    				tempSet.addAll(areas);
    				//求出tempSet 和   allAreas 集合的交集, 交集会赋给 tempSet
    				tempSet.retainAll(allAreas);
    				//如果当前这个集合包含的未覆盖地区的数量，
    				//比maxKey指向的集合地区还多
    				//就需要重置maxKey
    				//体现出贪心算法的特点,每次都选择最优的
    				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));
    				broadcasts.remove(maxKey);
    			}
    		}
    		System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]
    	}
    }

# 注意 #

*  贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
 *  K2, K3,K4,K5 也可以覆盖全部地区，如果K2 的使用成本低于K1,那么上题的 K1, K2, K3, K5 虽然是满足条件，但是并不是最优的

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030813474294.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NoaWxsX0x5bg==,size_16,color_FFFFFF,t_70