您好,登录后才能下订单哦!
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
这篇“Java贪心算法实例分析”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“Java贪心算法实例分析”文章吧。
贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果.
贪心算法的优缺点:
优点: 贪心算法的代码十分简单
缺点: 很难确定一个问题是否可以用贪心算法解决
假设存在以下的广播台, 以及广播台可以覆盖的地区:
广播台 | 覆盖地区 |
---|---|
K1 | 北京, 上海, 天津 |
K2 | 北京, 广州, 深圳 |
K3 | 上海, 杭州, 成都 |
K4 | 上海, 天津 |
K5 | 杭州, 大连 |
贪心算法的核心思想:
把所有需要覆盖的地区取集合
从电台中取覆盖集合中地区最多的一个
集合中去除已覆盖地区, 继续匹配
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贪心算法实例分析”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。