前言需要
假如存在上面须要付费的广播台，以及广播台信号能够笼罩的地区。
如何抉择起码的广播台，让所有的地区都能够接管到信号
那么这个问题咱们应用什么形式解决呢？答：贪婪算法
一、什么是贪婪算法
贪心算法(贪婪算法)是指在对问题进行求解时，在每一步抉择中都采取最好或者最优(即最无利)的抉择，从而心愿可能导致后果是最好或者最优的算法
算法所失去的后果不肯定是最优的后果(有时候会是最优解)，然而都是绝对近似(靠近)最优解的后果
以下面的问题问题，若应用贪婪算法求出的后果，有时候不肯定是最优的后果，因为有可能老本问题不是最好的，然而它是绝对靠近最优解的
二、通过示例意识贪婪算法
采纳下面的问题，咱们还是从最笨的办法开始，抉择起码的广播台，让所有的地区都能够接管到信号
假如咱们当初有n个广播台，那么咱们应用最笨的形式先列举每个可能的汇合
咱们就能够这种最笨的办法推导出，n个广播台，他的组合集为2^-1，当然也可不用 -1 因为还有一种抉择形式是：空集，什么都不选
假如咱们采纳这种形式去做，那么所须要的工夫就太多太多了，效率十分的低，而且达到100台，就算不下了。
应用贪婪算法思路剖析
1.列举须要笼罩的城市：北京、上海、天津、广州、深圳、成都、杭州、大连
2.列举出每个播送电视台的笼罩地区数量
3.每次找到广播台的笼罩地区数量值最大，取名naxKey
4.下一次比拟的时候，去掉上次笼罩地区，从新找到naxKey
算法步骤思路剖析
1.列举出所有城市，放入一个汇合中
2.进行第一轮的查找，假如K1 为笼罩地区数量值最大
3.这时将K1对应的城市从汇合中删除，进行下一轮比拟
4.进行下一轮的查找，假如K2 为笼罩地区数量值最大..接着以此类推
5.一样的思路革除naxKey对应的城市…而后以此类推进行每轮比拟
代码实现
依照咱们的思路，咱们先进行创立key 与对应的地区城市
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
//创立广播电台,放入到Map
HashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
broadcasts.put("K1", hashSet1);
broadcasts.put("K2", hashSet2);
broadcasts.put("K3", hashSet3);
broadcasts.put("K4", hashSet4);
broadcasts.put("K5", hashSet5);接下来咱们将这些key的城市放入一个汇合中寄存
//allAreas 寄存所有的地区
HashSet<String> allAreas = new HashSet<String>();
allAreas.add("北京");
allAreas.add("上海");
allAreas.add("天津");
allAreas.add("广州");
allAreas.add("深圳");
allAreas.add("成都");
allAreas.add("杭州");
allAreas.add("大连");每一轮咱们都能找到maxKey，咱们须要存储这些maxKey，将他放入汇合中
//创立ArrayList, 寄存抉择的电台汇合
ArrayList<String> selects = new ArrayList<String>();当咱们的K1、K2… 所负责的城市与allAreas 产生的交加，也须要记录下来
//定义一个长期的汇合， 在遍历的过程中，寄存遍历过程中的电台笼罩的地区和以后还没有笼罩的地区的交加
HashSet<String> tempSet = new HashSet<String>();同时，咱们须要每次将对应的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<String> 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.初始化，将数据放入汇合中
2.找出以后K1、K2、K3、K4、K5中的maxKey，将它对应的城市放入tempSet
3.将tempSet与allAreas 找出交加的数据
4.将maxKey对应的城市从allAreas 删除，同时将maxKey增加进selects
5.将maxKey 清空与tempSet 清空，进行新的maxKey寻找
参考文献
- 尚硅谷：数据结构与算法（韩顺平老师）：贪婪算法
发表回复