【Java】我所知道的十大常用算法之贪心算法
前言需求
假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。
如何选择最少的广播台，让所有的地区都可以接收到信号
那么这个问题我们使用什么方式解决呢？答：算法" title="贪心算法">贪心算法
一、什么是贪心算法
贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
以上面的问题问题，若使用贪心算法求出的结果，有时候不一定是最优的结果，因为有可能成本问题不是最好的，但是它是相对接近最优解的
二、通过示例认识贪心算法
采用上面的问题，我们还是从最笨的方法开始，选择最少的广播台，让所有的地区都可以接收到信号
假设我们现在有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寻找
参考文献
- 尚硅谷：数据结构与算法（韩顺平老师）：贪心算法
以上是 【Java】我所知道的十大常用算法之贪心算法 的全部内容， 来源链接： utcz.com/a/89185.html
