0 集合覆盖问题

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

2. 思路分析①:穷举法,列出每个可能的广播台的集合，假设总的有 n 个广播台，则广播台的组合总共有2ⁿ -1 个,假设每秒可以计算 10 个子集， 如图:

3. 思路分析②:贪心算法,见下一章

1 贪心算法

1. 目标:选择策略上,尽量选择最少的电台,并覆盖全部地区
2. 首先:集合allAreas收录全部的8个地区,遍历所有电台并最终选择能覆盖最多地区的电台k(贪心)
3. 删除allAreas中k所能覆盖的电台
4. 在剩余的4个电台中重复第2步和第3步的操作
5. 直到allAreas的大小为0,表示选择的电台已经覆盖全地区
6. 即得到所选的电台集合

说明:整个过程中,其实重难点在第2步中如何选择能覆盖最多地区的电台,并不是选择最大的电台,而是k电台与allAreas的交集如果最大,说明k就是本轮我们选择的结果,allAreas其实应该理解为目前未被电台覆盖的地区

举例:当K1电台已经被选择后,在第二轮的选择情况如下(结果选K2电台):

ps:该算法的解并不一定是最优解,只是相对接近最优,因为当多个电台都能覆盖3个地区时,我们选择了第一个,这考虑的过于简单,比如第一个电台如果包月太贵那么是否应该考虑选第2个呢

2 代码实现

//贪心算法
public class GreedyAlgorithm {public static void main(String[] args) {//创建广播电台,放入到 MapHashMap> broadcasts = new HashMap>();//将各个电台放入到 broadcastsHashSet 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("大连");//加入到 mapbroadcasts.put("K1", hashSet1);broadcasts.put("K2", hashSet2);broadcasts.put("K3", hashSet3);broadcasts.put("K4", hashSet4);broadcasts.put("K5", hashSet5);//allAreas 存放所有的地区HashSet allAreas = new HashSet();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大连");//选择结果List selects = new ArrayList();//存放最大结果集(即本轮选择的电台和其新覆盖的地区)String bigKey = "";HashSet bigSet =null;//存放遍历的结果与全地区的交集(即能覆盖的新地区)HashSet tempSet =null;//只要全地区还有元素,说明仍有地区未覆盖while (allAreas.size() > 0) {//遍历广播电台的同时,获取与全地区的交集,贪心:暂存本轮交集最大的电台for (String key : broadcasts.keySet()) {tempSet = broadcasts.get(key);tempSet.retainAll(allAreas);if (bigSet==null||broadcasts.get(key).size() > bigSet.size()) {bigSet= tempSet;bigKey = key;}}//收集本轮的电台选择结果并删除全地区中该电台覆盖的地区selects.add(bigKey);allAreas.removeAll(bigSet);}System.out.println(selects);}
}