Java使用贪心算法解决电台覆盖问题(示例详解)

java使用贪心算法解决电台覆盖问题

代码实现

/**
 * 贪心算法实现集合覆盖
 */
public class Demo {
    public static void main(String[] args) {
        // 创建电台和地区集合
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        // 创建各个电台
        HashSet<String> k1 = new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        HashSet<String> k2 = new HashSet<>();
        k2.add("广州");
        k2.add("北京");
        k2.add("深圳");
        HashSet<String> k3 = new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        HashSet<String> k4 = new HashSet<>();
        k4.add("上海");
        k4.add("天津");
        HashSet<String> k5 = new HashSet<>();
        k5.add("杭州");
        k5.add("大连");

        // 加入各个电台
        broadcasts.put("k1", k1);
        broadcasts.put("k2", k2);
        broadcasts.put("k3", k3);
        broadcasts.put("k4", k4);
        broadcasts.put("k5", k5);
        // 建立各个地区的集合
        HashSet<String> allAreas = new HashSet<>();
        for (Map.Entry<String, HashSet<String>> entry : broadcasts.entrySet()) {
            HashSet<String> value = entry.getValue();
            allAreas.addAll(value);
        }
        // 创建选择的电台的集合
        ArrayList<String> broadSelect = new ArrayList<>();
        // 定义一个临时的集合
        HashSet<String> tempSet = new HashSet<>();
        // 定义一个指针,用于指向当前最优
        String maxKey = null;
        while (allAreas.size() > 0) {
            // 重置置空
            maxKey = null;
            // 遍历
            for (String key : broadcasts.keySet()) {
                // 重置置空
                tempSet.clear();
                HashSet<String> value = broadcasts.get(key);
                tempSet.addAll(value);
                // 求出temp和allAreas的交集
                tempSet.retainAll(allAreas);
                // 如果当前选择有覆盖地区
                if (tempSet.size() > 0 &&
                        // 此时,如果maxKey还没有指向就指向
                        (maxKey == null ||
                                // 如果maxKey已经有指向就比较谁最优解
                                (tempSet.size() > (broadcasts.get(maxKey).size())))) {
                    maxKey = key;
                }
            }
            if (maxKey != null) {
                // 将maxKey加入
                broadSelect.add(maxKey);
                // 并将allAreas去掉maxKey能覆盖的地区
                allAreas.removeAll(broadcasts.get(maxKey));
        // 打印结果
        System.out.println(broadSelect);
    }
}

补充:下面看下贪心算法解决集合覆盖问题

贪心算法:指在对问题求解时,在每一步都选择最好的选择,从而希望得到最好的结果。

解决集合覆盖问题

比如有5个广播台,每个广播台覆盖的区域不一样,怎么选择最少的广播台,让所有区域都覆盖上
如 k1广播台覆盖的区域有:北京、上海、天津
k2广播台覆盖的区域有:北京、山东、深圳
k3广播台覆盖的区域有:成都、上海、杭州
k4广播台覆盖的区域有:上海、天津
k5广播台覆盖的区域有:杭州、武汉

步骤:

1. 遍历所有广播台,找到了个覆盖了最多未覆盖的地区的电台
2. 将这个电台加入到集合中,想办法将该电台覆盖的地区下次比较时去掉
3. 重复第1步,直到覆盖了全部区域

图解

所有区域:{北京、上海、天津、山东、深圳、成都、杭州、武汉};
选择的电台:{}

第一步:遍历所有广播台,找到了个覆盖了最多未覆盖的地区的电台
k1(北京、上海、天津),k2(北京、山东、深圳),k3(成都、上海、杭州)在所有区域({北京、上海、天津、山东、深圳、成都、杭州、武汉})中覆盖的个数为3
k4(上海、天津),k5(杭州、武汉)在在所有区域({北京、上海、天津、山东、深圳、成都、杭州、武汉})中覆盖的个数为2
选择最大覆盖数k1加入到选择的电台{k1},
第二步:将k1(北京、上海、天津)从所覆盖的区域从所有区域中移除,所有区域更新为:{山东、深圳、成都、杭州、武汉};

第三步:重复第一步,遍历所有广播
k1(北京、上海、天津)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为0
k2(北京、山东、深圳)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2
k3(成都、上海、杭州)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2
k4(上海、天津)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为0
k5(杭州、武汉)在所有区域({山东、深圳、成都、杭州、武汉})中覆盖的个数为2
选择最大覆盖数k2加入到选择的电台{k1,k2}
将k2(北京、山东、深圳)从所覆盖的区域从所有区域中移除,所有区域更新为:{成都、杭州、武汉};
k1(北京、上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k2(北京、山东、深圳)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k3(成都、上海、杭州)在所有区域({成都、杭州、武汉})中覆盖的个数为2
k4(上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k5(杭州、武汉)在所有区域({成都、杭州、武汉})中覆盖的个数为2

选择最大覆盖数k3加入到选择的电台{k1,k2,k3}
将k3(成都、上海、杭州)从所覆盖的区域从所有区域中移除,所有区域更新为:{武汉};
k1(北京、上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k2(北京、山东、深圳)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k3(成都、上海、杭州)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k4(上海、天津)在所有区域({成都、杭州、武汉})中覆盖的个数为0
k5(杭州、武汉)在所有区域({成都、杭州、武汉})中覆盖的个数为1

选择最大覆盖数k5加入到选择的电台{k1,k2,k3,k5}
完成

代码实现:

package azhong.greedy_algo;

import java.util.*;
/**
 * 贪心算法
 * 在对问题求解时,在每一步都选择最好的选择,从而希望得到最好的结果。
 */
public class GreedyAlgoDemo {
    public static void main(String[] args) {
        //每个电台覆盖的区域
        Map<String,HashSet<String>> allStations = initRadioStation();
        //需要覆盖的所有区域
        HashSet<String> allAreas = getAllAreas(allStations);
        //存放选择的电台
        List<String> selectedStations = new ArrayList<>();
        while (allAreas.size()>0) {
            //遍历所有广播台,找到了个覆盖了最多未覆盖的地区的电台
            int maxIndex=0;
            String maxK=null;
            HashSet<String> areaInMaxK=null;
            for (Map.Entry<String, HashSet<String>> entry : allStations.entrySet()) {
                final String k = entry.getKey();
                HashSet<String> values = entry.getValue();
                //当前电台在所有区域覆盖的个数
                int c = testIntersectionOfSet(values, allAreas);
                System.out.println(k + " 在所有区域覆盖的个数: " + c);
                if(c>maxIndex){
                    maxIndex=c;
                    maxK=k;
                    areaInMaxK=values;
                }
            }
            if(maxK!=null){
                //选择最大覆盖数k1加入到选择的电台{k1},
                selectedStations.add(maxK);
                //将k1(北京、上海、天津)从所覆盖的区域从所有区域中移除,所有区域更新为:{山东、深圳、成都、杭州、武汉};
                allAreas.removeAll(areaInMaxK);
                //重置,进入下一次循环
                maxIndex=0;
                maxK=null;
                areaInMaxK=null;
                System.out.println("****************************");
        }
        System.out.println(selectedStations);
    }
    /**
     * 测试:求两个集合的交集
     * A{北京、上海、天津}
     * B{北京、上海、天津、山东、深圳、成都、杭州、武汉}
     * A.retainAll(B); 得到A{北京、上海、天津} 个数为3
     */
    private static int testIntersectionOfSet(HashSet A,HashSet B){
        //将存在于集合A中但不存在于集合B中的元素移除。
        A.retainAll(B);
        return A.size();
     * 初始化电台
     * k1广播台覆盖的区域有:北京、上海、天津
     * k2广播台覆盖的区域有:北京、山东、深圳
     * k3广播台覆盖的区域有:成都、上海、杭州
     * k4广播台覆盖的区域有:上海、天津
     * k5广播台覆盖的区域有:杭州、武汉
     * @return Map<String,HashSet<String>>类型电台集合
    private static Map<String,HashSet<String>> initRadioStation(){
        Map<String,HashSet<String>> allStations = new HashMap<String,HashSet<String>>();
        HashSet<String> k1 = new HashSet<>();
        k1.add("北京");
        k1.add("上海");
        k1.add("天津");
        HashSet<String> k2 = new HashSet<>();
        k2.add("北京");
        k2.add("山东");
        k2.add("深圳");
        HashSet<String> k3 = new HashSet<>();
        k3.add("成都");
        k3.add("上海");
        k3.add("杭州");
        HashSet<String> k4 = new HashSet<>();
        k4.add("上海");
        k4.add("天津");
        HashSet<String> k5 = new HashSet<>();
        k5.add("杭州");
        k5.add("武汉");
        allStations.put("k1",k1);
        allStations.put("k2",k2);
        allStations.put("k3",k3);
        allStations.put("k4",k4);
        allStations.put("k5",k5);
        return allStations;
    private static HashSet<String> getAllAreas(Map<String,HashSet<String>> allStations){
        HashSet<String> allAreas = new HashSet<>();
        Collection<HashSet<String>> stations = allStations.values();
        for(HashSet<String> station:stations){
            Iterator<String> areas = station.iterator();
            //操泥玛,写成了if
            while (areas.hasNext()){
                allAreas.add(areas.next());
        return allAreas;
}

运行结果为:

k1 在所有区域覆盖的个数: 3
k2 在所有区域覆盖的个数: 3
k3 在所有区域覆盖的个数: 3
k4 在所有区域覆盖的个数: 2
k5 在所有区域覆盖的个数: 2
****************************
k1 在所有区域覆盖的个数: 0
k2 在所有区域覆盖的个数: 2
k3 在所有区域覆盖的个数: 2
k4 在所有区域覆盖的个数: 0
k5 在所有区域覆盖的个数: 2
****************************
k1 在所有区域覆盖的个数: 0
k2 在所有区域覆盖的个数: 0
k3 在所有区域覆盖的个数: 2
k4 在所有区域覆盖的个数: 0
k5 在所有区域覆盖的个数: 2
****************************
k1 在所有区域覆盖的个数: 0
k2 在所有区域覆盖的个数: 0
k3 在所有区域覆盖的个数: 0
k4 在所有区域覆盖的个数: 0
k5 在所有区域覆盖的个数: 1
****************************
[k1, k2, k3, k5]

到此这篇关于Java使用贪心算法解决电台覆盖问题的文章就介绍到这了,更多相关java贪心算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 贪心算法原理及在Java中的使用

    贪心算法 由于贪心算法本身的特殊性,我们在使用贪心算法之前必须要进行证明,保证算法满足贪心选择性质.具体的证明方法无外乎就是通过数学归纳法来进行证明.但大部分人可能并不喜欢枯燥的公式,因而我这里提供一个使用贪心算法的小技巧.由于贪心算法某种程度上算是动态规划算法的特例,使用条件比较苛刻,因而能够用动态规划解决的问题尽量都是用动态规划来进行先解决,如果在用完动态规划之后,提交时发现问题超时,并且进行状态压缩之后仍然超时,此时我们就可以**考虑使用贪心算法来进行解决.**最后强调一下,我们在使用贪心

  • Java 数据结构与算法系列精讲之贪心算法

    概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 贪心算法 贪心算法 (Greedy Algorithm) 指的是在每一步选择中都采取在当前状态下最好或最优的选择, 从而希望导致结果是最好或最优的算法. 贪心算法锁得到的结果不一定是最优的结果, 但是都是相对近似最优的结果. 贪心算法的优缺点: 优点: 贪心算法的代码十分简单 缺点: 很难确定一个问题是否可以用贪心算法解决 电台覆盖问题 假设存在以下的广播台, 以及广播台可以覆盖的地区: 广播台 覆盖地区 K1 北京

  • java贪心算法初学感悟图解及示例分享

    算法简介 1)贪心算法是指在对问题进行求解时,在每一步选择中都采取最好或者最优(即最有利)的选择,从而希望能够导致是最好或者最优的算法 2)贪心算法所得到的结果不一定是最优的结果(有时候会是最优解),但是都是相对近似(接近)最优解的结果. 应用场景 --> 集合覆盖 public class GreedyAlgorithm { public static void main(String[] args) { // 创建广播电台,放入到Map HashMap<String, HashSet<

  • Java使用贪心算法解决电台覆盖问题(示例详解)

    java使用贪心算法解决电台覆盖问题 代码实现 /** * 贪心算法实现集合覆盖 */ public class Demo { public static void main(String[] args) { // 创建电台和地区集合 HashMap<String, HashSet<String>> broadcasts = new HashMap<>(); // 创建各个电台 HashSet<String> k1 = new HashSet<>

  • java暴力匹配及KMP算法解决字符串匹配问题示例详解

    目录 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 二.KMP算法 算法介绍 一个图例介绍KMP算法   代码实现 要解决的问题? 一.暴力匹配算法 一个图例介绍KMP算法 String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD";     1. S[0]为B,P[0]为A,不匹配,执行第②条指令:"如果失配(即S[i]! = P[j]),令i = i - (j - 1),

  • java 中基本算法之希尔排序的实例详解

    java 中基本算法之希尔排序的实例详解 希尔排序(Shell Sort)是插入排序的一种.也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本.希尔排序是非稳定排序算法.该方法因DL.Shell于1959年提出而得名. 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差

  • Go Java算法最大单词长度乘积示例详解

    目录 最大单词长度乘积 方法一:位运算(java) 方法一:位运算(go) 最大单词长度乘积 给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母.如果不存在这样的两个单词,返回 0 . *示例 1: 输入:words = ["abcw","baz","foo","bar","xtfn","ab

  • Go Java 算法之迷你语法分析器示例详解

    目录 迷你语法分析器 方法一:深度优先遍历(Java) 方法二:栈(Go) 迷你语法分析器 给定一个字符串 s 表示一个整数嵌套列表,实现一个解析它的语法分析器并返回解析的结果 NestedInteger . 列表中的每个元素只可能是整数或整数嵌套列表 示例 1: 输入:s = "324", 输出:324 解释:你应该返回一个 NestedInteger 对象,其中只包含整数值 324. 示例 2: 输入:s = "[123,[456,[789]]]", 输出:[1

  • java中常见的6种线程池示例详解

    之前我们介绍了线程池的四种拒绝策略,了解了线程池参数的含义,那么今天我们来聊聊Java 中常见的几种线程池,以及在jdk7 加入的 ForkJoin 新型线程池 首先我们列出Java 中的六种线程池如下 线程池名称 描述 FixedThreadPool 核心线程数与最大线程数相同 SingleThreadExecutor 一个线程的线程池 CachedThreadPool 核心线程为0,最大线程数为Integer. MAX_VALUE ScheduledThreadPool 指定核心线程数的定时

  • Java实现超简单抖音去水印的示例详解

    目录 一.前言 二.原理与步骤 三.代码实现 四.总结 一.前言 抖音去水印方法很简单,以前一直没有去研究,以为搞个去水印还要用到算法去除,直到动手的时候才发现这么简单,不用编程基础都能做. 二.原理与步骤 其实抖音它是有一个隐藏无水印地址的,只要我们找到那个地址就可以了 1.我们在抖音找一个想要去水印的视频链接 注意:这里一定要是https开头的,不是口令 打开浏览器访问: 访问之后会重定向到这个地址,后面有一串数字,这个就是视频的id,他是根据这个唯一id来找到视频播放的 按F12查看网络请

  • java zxing合成复杂二维码图片示例详解

    目录 说明: 整体思路: 图片合成四部曲 踩过的坑 说明: 最近接到需要将二维码合成复杂图片的需求,要求给二维码上下或者左侧添加相关文字描述,技术没有难点,整理本文主要记录思路和踩过的坑. 整体思路: 引入zxing成熟的二维码生成接口,生成标准二维码文件,通过java图形图像处理API为二维码添加相关文字描述,根据需要,可以为合成后的图片添加相关背景.示例如下图所示: 1.先拿点位图来说,生成二维码图片核心代码如下 /** * 定义二维码的参数 */ HashMap<EncodeHintTyp

  • 后端算法题解LeetCode前缀和示例详解

    目录 面试题 01.09. 字符串轮转 方法一:模拟 思路 题解 方法二:搜索子字符串 思路 题解 1480. 一维数组的动态和 方法一:前缀和 思路 题解 724. 寻找数组的中心下标 方法一:前缀和 思路 解题 面试题 01.09. 字符串轮转 面试题 01.09. 字符串轮转 难度:easy 字符串轮转.给定两个字符串 s1 和 s2,请编写代码检查 s2 是否为 s1 旋转而成(比如,waterbottle 是 erbottlewat 旋转后的字符串). 示例1: 输入:s1 = "wa

  • java中Servlet监听器的工作原理及示例详解

    监听器就是一个实现特定接口的普通java程序,这个程序专门用于监听另一个java对象的方法调用或属性改变,当被监听对象发生上述事件后,监听器某个方法将立即被执行. 监听器原理 监听原理 1.存在事件源 2.提供监听器 3.为事件源注册监听器 4.操作事件源,产生事件对象,将事件对象传递给监听器,并且执行监听器相应监听方法 监听器典型案例:监听window窗口的事件监听器 例如:swing开发首先制造Frame**窗体**,窗体本身也是一个显示空间,对窗体提供监听器,监听窗体方法调用或者属性改变:

随机推荐