关于java:常用十大算法五-贪心算法

罕用十大算法（五）— 贪婪算法

<!-- more -->

博客阐明

文章所波及的材料来自互联网整顿和集体总结，意在于集体学习和教训汇总，如有什么中央侵权，请分割自己删除，谢谢！

介绍

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

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

汇合笼罩问题

假如存在如下表的须要付费的广播台，以及广播台信号能够笼罩的地区。 如何抉择起码的广播台，让所有的地区都能够接管到信号

思路

• 遍历所有的广播电台, 找到一个笼罩了最多未笼罩的地区的电台(此电台可能蕴含一些已笼罩的地区，但没有关系）
• 将这个电台退出到一个汇合中(比方ArrayList), 想方法把该电台笼罩的地区在下次比拟时去掉。
• 反复第1步直到笼罩了全副的地区

代码实现

package com.atguigu.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>> broadcasts = 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("大连");            broadcasts.put("K1", hashSet1);        broadcasts.put("K2", hashSet2);        broadcasts.put("K3", hashSet3);        broadcasts.put("K4", hashSet4);        broadcasts.put("K5", 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> tempSet = new HashSet<String>();                String maxKey = null;        while(allAreas.size() != 0) {             maxKey = null;            for(String key : broadcasts.keySet()) {                tempSet.clear();                HashSet<String> areas = broadcasts.get(key);                tempSet.addAll(areas);                tempSet.retainAll(allAreas);                if(tempSet.size() > 0 &&                         (maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){                    maxKey = key;                }            }            if(maxKey != null) {                selects.add(maxKey);                allAreas.removeAll(broadcasts.get(maxKey));            }        }        System.out.println("贪婪算法失去汇合：" + selects);    }}

感激

尚硅谷

以及勤奋的本人，集体博客，GitHub