关于java:我所知道的十大常用算法之贪心算法

前言需要

假如存在上面须要付费的广播台，以及广播台信号能够笼罩的地区。

如何抉择起码的广播台，让 所有的地区都能够接管到信号

那么这个问题咱们应用什么形式解决呢？答：贪婪算法

一、什么是贪婪算法

贪心算法 (贪婪算法) 是指在 对问题进行求解时，在每一步抉择中都采取最好或者最优 (即最无利) 的抉择，从而心愿可能导致后果是最好或者最优的算法

算法所失去的后果不肯定是 最优的后果 (有时候会是最优解)，然而都是 绝对近似 (靠近) 最优解 的后果

以下面的问题问题，若应用贪婪算法求出的后果，有时候不肯定是最优的后果，因为有可能老本问题不是最好的，然而它是绝对靠近最优解的

二、通过示例意识贪婪算法

采纳下面的问题，咱们还是从最笨的办法开始，抉择起码的广播台，让 所有的地区都能够接管到信号

假如咱们当初有 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 寻找

参考文献

• 尚硅谷：数据结构与算法（韩顺平老师）：贪婪算法