Java贪心算法实例分析

这篇“Java贪心算法实例分析”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“Java贪心算法实例分析”文章吧。

贪心算法

贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果.

贪心算法的优缺点:

• 优点: 贪心算法的代码十分简单

• 缺点: 很难确定一个问题是否可以用贪心算法解决

电台覆盖问题

假设存在以下的广播台, 以及广播台可以覆盖的地区:

贪心算法的核心思想:

• 把所有需要覆盖的地区取集合

• 从电台中取覆盖集合中地区最多的一个

• 集合中去除已覆盖地区, 继续匹配

代码实现

import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; public class 贪心算法 {     // 集合, 存放广播台     static HashMap<String, HashSet<String>> broadcasts = new HashMap<>();     // 集合, 存放地区     static HashSet<String> areas = new HashSet<String>();     // 贪心算法     public static ArrayList<String> Greedy() {         // 创建数组存放结果         ArrayList<String> selects = new ArrayList<>();         // 循环直至地区都覆盖         while (areas.size() != 0) {             // 存放交集最大的广播台             String maxKey = null;             // 存放交集最大的值             int maxKeySize = 0;             // 遍历每个剩余电台             for (String key : broadcasts.keySet()) {                 // 取出交集个数                 int currSize = getRetainSize(key);                 // 替换当前最大                 if (currSize > 0 && currSize > maxKeySize) {                     maxKey = key;                     maxKeySize = currSize;                 }             }             // 添加广播台到结果             selects.add(maxKey);             // 移除广播台             areas.removeAll(broadcasts.get(maxKey));         }         return selects;     }     // 剩余数量     public static int getRetainSize(String key) {         // 如果为空返回0         if (key == null) return 0;         // 存放key对应的地区集合         HashSet<String> tempSet = new HashSet<>();         // 取key对应的地区         tempSet.addAll(broadcasts.get(key));         // 取交集         tempSet.retainAll(areas);         return tempSet.size();     }     public static void main(String[] args) { //        | K1 | 北京, 上海, 天津 | //        | K2 | 北京, 广州, 深圳 | //        | K3 | 上海, 杭州, 成都 | //        | K4 | 上海, 天津 | //        | K5 | 杭州, 大连 |         // 创建广播台         HashSet<String> K1 = new HashSet<>(Arrays.asList("北京", "上海", "天津"));         HashSet<String> K2 = new HashSet<>(Arrays.asList("北京", "广州", "深圳"));         HashSet<String> K3 = new HashSet<>(Arrays.asList("上海", "杭州", "成都"));         HashSet<String> K4 = new HashSet<>(Arrays.asList("上海", "天津"));         HashSet<String> K5 = new HashSet<>(Arrays.asList("杭州", "大连"));         // 加入map         broadcasts.put("K1", K1);         broadcasts.put("K2", K2);         broadcasts.put("K3", K3);         broadcasts.put("K4", K4);         broadcasts.put("K5", K5);         areas.addAll(K1);         areas.addAll(K2);         areas.addAll(K3);         areas.addAll(K4);         areas.addAll(K5);         // 调试输出         System.out.println(broadcasts);         System.out.println(areas);         ArrayList<String> result = Greedy();         System.out.println(result);     } }

以上就是关于“Java贪心算法实例分析”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注亿速云行业资讯频道。