算法——贪心算法（集合覆盖 -- Java代码实现）

朱雀 2023-02-13 11:37 211阅读 0赞

**贪心算法介绍**

1.  贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。
2.  贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。

问题：使用最少的广播台覆盖全部的地区；

思路分析:  
➢ 如何找出覆盖所有地区的广播台的集合呢，使用穷举法实现，列出每个可能的广播台的集合，这被称为幂集。假设总的有n个广播台，则广播台的组合总共有2^n - 1个，

➢使用贪婪算法，效率高:  
目前并没有算法可以快速计算得到准备的值，使用贪婪算法，则可以得到非常接近的解，并且效率高。选择策略上，因为需要覆盖全部地区的最小集合：

1.  遍历所有的广播电台，找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系)
2.  将这个电台加入到一-个集合中(比如ArrayList)，想办法把该电台覆盖的地区在下次比较时去掉。
3.  重复第1步直到覆盖了全部的地区

代码实现：可以直接发现上述问题的解决的是要选择ABCE四个广播台：

package greedy;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.HashSet;
    
    public class GreedyAlgorithm { 
    	public static void main(String[] args) { 
    		// 创建广播台
    		HashMap<String, HashSet<String>> broadcast = new HashMap<String, HashSet<String>>();
    		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("大连");
    
    		broadcast.put("A", hashset1);
    		broadcast.put("B", hashset2);
    		broadcast.put("C", hashset3);
    		broadcast.put("D", hashset4);
    		broadcast.put("E", hashset5);
    
    		// 创建一个所有地区的
    		HashSet<String> allAreas = new HashSet<String>();
    		allAreas.add("北京");
    		allAreas.add("上海");
    		allAreas.add("天津");
    		allAreas.add("广州");
    		allAreas.add("深圳");
    		allAreas.add("成都");
    		allAreas.add("杭州");
    		allAreas.add("大连");
    
    		// 使用一个电台集合
    		ArrayList<String> selects = new ArrayList<String>();
    
    		// 临时变量,覆盖的地区和未覆盖地区的交集
    		HashSet<String> temp = new HashSet<String>();
    
    		// 定义一个在一次遍历过程中覆盖最多地区的广播台
    		String maxKey = null;
    		while (allAreas.size() != 0) { 
    			// 遍历广播台
    			for (String key : broadcast.keySet()) { 
    				temp.clear();
    				HashSet<String> areas = broadcast.get(key);
    				temp.addAll(areas);
    				// 取交集,之后交集再赋给temp
    				temp.retainAll(allAreas);
    				if (temp.size() > 0 && (maxKey == null || temp.size() > broadcast.get(maxKey).size())) { 
    					maxKey = key;
    				}
    			}
    			if (maxKey != null) { 
    				selects.add(maxKey);
    				allAreas.removeAll(broadcast.get(maxKey));
    			}
    			maxKey = null;
    		}
    		System.out.println("结果：" + selects);
    	}
    }

查看结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]

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