java贪心算法初学感悟图解及示例分享
算法简介
1)贪心算法是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致是最好或者最优的算法
2)贪心算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果。
应用场景 --> 集合覆盖
public class GreedyAlgorithm { public static void main(String[] args) { // 创建广播电台,放入到Map HashMap<String, HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>(); // 将各个电台放入到broadcasts 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 broadcasts.put("K1", hashSet1); broadcasts.put("K2", hashSet2); broadcasts.put("K3", hashSet3); broadcasts.put("K4", hashSet4); broadcasts.put("K5", hashSet5); // allAreas,存放所有的地区 HashSet<String> allAreas = new HashSet<String>(); allAreas.add("北京"); allAreas.add("上海"); allAreas.add("天津"); allAreas.add("广州"); allAreas.add("深圳"); allAreas.add("成都"); allAreas.add("杭州"); allAreas.add("大连"); // 创建ArrayList,存放选择的电台集合 ArrayList<String> selects = new ArrayList<String>(); // 定义一个临时的集合,在遍历的过程中,存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集 HashSet<String> tempSet = new HashSet<String>(); // 定义一个maxKey,保存在一次遍历过程中,能够覆盖最多未覆盖的地区对应的电台的key // 如果maxKey不为null,则会加入到selects String maxKey = null; while (allAreas.size() != 0) {// 如果allAreas不为0,则表示还没有覆盖到所有的地区 // 每进行一次while,需要将maxKey置空 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);// retainAll方法的作用就是求交集 // 如果当前这个集合包含的未覆盖地区的数量,比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)); } } System.out.println("得到的选择结果是" + selects); } }
以上就是java贪心算法初学感悟图解及示例分享的详细内容,更多关于java贪心算法的资料请关注我们其它相关文章!
赞 (0)