【算法】贪心算法

应用场景——集合覆盖问题

假设存在下面需要付费的广播台,以及广播台信号可以覆盖的地区。如何选择最少的广播台,让所有的地区都可以接收到信号

贪心算法介绍

1.贪心算法是指在对问题进行求解时,在每一步选择中都采取最好或者最优的选择

2.贪心算法得到的结果不一定是最优的结果,但是都是相对近似最优解的结果

思路分析

使用贪心算法的效率非常高,选择策略上,由于需要覆盖全部小区的所有集合:

1.遍历所有的广播电台,找到一个覆盖了最多未覆盖地区的电台(此电台可能包含一些已覆盖的地区,但没有关系)

2.将这个电台加入到一个集合中(比如 ArrayList),想办法把该电台覆盖的地区在下次比较时去掉

3.重复第 1 步直到覆盖了全部的地区

用代码实现集合覆盖问题
public class GreedyAlgorithm {public static void main(String[] args) {//创建广播电台,放入到 MapHashMap<String, HashSet<String>> broadcasts = new HashMap<>();//将各个电台放入到 broadcastsHashSet<String> hashSet1 = new HashSet<>();hashSet1.add("北京");hashSet1.add("上海");hashSet1.add("天津");HashSet<String> hashSet2 = new HashSet<>();hashSet2.add("广州");hashSet2.add("北京");hashSet2.add("深圳");HashSet<String> hashSet3 = new HashSet<>();hashSet3.add("成都");hashSet3.add("上海");hashSet3.add("杭州");HashSet<String> hashSet4 = new HashSet<>();hashSet4.add("上海");hashSet4.add("天津");HashSet<String> hashSet5 = new HashSet<>();hashSet5.add("杭州");hashSet5.add("大连");//加入到 Mapbroadcasts.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<>();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");allAreas.add("大连");//创建 ArrayList,存放选择的电台集合ArrayList<String> selects = new ArrayList<>();//定义一个临时的集合,在遍历过程中,存放遍历过程中电台覆盖的地区和当前还没有覆盖的地区的交集HashSet<String> tempSet = new HashSet<>();/*定义一个 maxKey,保存在一次遍历过程中,能够覆盖最大未覆盖地区的电台的 key如果 maxKey 不为 null,则会加入到 selects*/String maxKey = null;while (allAreas.size() != 0) {  //如果 allAreas 不为 0,则表示还没有覆盖到所有的地区//每进行一次 while,需要maxKey = null;//遍历 broadcasts,取出对应 keyfor (String  key : broadcasts.keySet()) {//每进行一次 fortempSet.clear();//当前这个 key 能够覆盖的地区HashSet<String> areas = broadcasts.get(key);tempSet.addAll(areas);//求出 tempSet 和 allAreas 集合的交集,交集会赋给 tempSettempSet.retainAll(allAreas);//如果当前这个集合包含的未覆盖地区的数量,比 maxKey 指向的集合地区还多//就需要重置 maxKey// (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size()) 体现出贪心的特点if (tempSet.size() > 0 &&(maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {maxKey = key;}}//maxKey != null,就应该将 maxKey 加入 selectsif (maxKey != null) {selects.add(maxKey);//将 maxKey 指向的广播电台覆盖的地区,从 allAreas 去掉allAreas.removeAll(broadcasts.get(maxKey));}}System.out.println("得到的选择结果是" + selects);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/393188.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

智观察 | 行业赛道里的AI大模型

‍ “AI改变世界”被炒得热火朝天&#xff0c;结果就换来AI聊天&#xff1f; 实际上&#xff0c;在日常娱乐之下&#xff0c;AI正在暗暗“憋大招”&#xff0c;深入各行各业&#xff0c;发挥更专业的作用。 自动驾驶 最近“萝卜快跑”霸榜热搜长达一周&#xff0c;让无人驾…

手机在网状态接口如何对接?(二)

一、什么是手机在网状态&#xff1f; 传入手机号码&#xff0c;查询该手机号的在网状态&#xff0c;返回内容有正常使用、停机、在网但不可用、不在网&#xff08;销号/未启用/异常&#xff09;、预销户等多种状态。 二、手机在网状态使用场景&#xff1f; 1.用户验证与联系…

【问题解决方案】npm install报错问题:npm ERR! - 多种解决方案,总有一种可以解决

文章目录 1.问题重述2.解决方案方案1.确认根目录正确方案2.确认文件名正确方案3. 确认node.js安装完成&#xff08;注意这个环境变量配置没有写完&#xff09;方案4 改用yarn安装&#xff08;亲测可用&#xff09; 3.延申问题解决方案问题1&#xff1a;需要低版本的node.js 写在…

企业图纸防泄密怎么做?最好的八款图纸加密软件推荐

保护企业图纸不被泄露是现代企业信息安全管理中的重要任务。随着信息技术的发展&#xff0c;企业需要采取多种措施来确保图纸的安全性。以下是一些常用的图纸防泄密方法和八款推荐的图纸加密软件&#xff1a; 图纸防泄密方法 1. 数据备份&#xff1a;定期备份图纸数据&#xf…

Jboss 漏洞

一.CVE-2015-7501 访问/invoker/JMXInvokerServlet 开启下载存在漏洞 二.CVE-2017-7504 三CVE-2017-12149 启动vulhub环境&#xff0c;访问/invoker/readonly出现如下界面&#xff0c;说明存在漏洞 使用工具连接 四.Administration Console弱⼝令 访问/admin-console/login…

数据库的管理

1、官网下载或者wget tar -xvf mysql-8.0.33-1.el7.x86_64.rpm-bundle.tar 2、确定mysql-community-server正常安装之后就可以开始配置 3、初始化mysqld 服务 mysqld initeialize 4、启动服务 systemctl start mysqld 5、添加开机启动列表 systecmctrl enable mysqld在/var…

git——Git提交本地项目代码到远程Github仓库步骤图解

目录 一、Git提交本地项目代码到远程Github仓库步骤 一、Git提交本地项目代码到远程Github仓库步骤 1、在Github创建一个空仓库&#xff0c;例如名称为jetcache-demo 2、打开【Git Bash Here】 3、进入本地项目文件夹 cd d:/ cd D:/project1/本地服务/jetcache-demo4、初始…

Golang面试题三(map)

1.map底层实现 由图看出&#xff0c;其实map的底层结构体是hmap&#xff0c;同时hmap里面维护着若干个bucket数组&#xff08;即桶数组&#xff09;。bucket数组中每个元素都是bmap结构的&#xff0c;bmap中存储着8个key-value的键值对&#xff0c;如果是满了的话&#xff0c;当…

用OpenCV与MFC写一个简单易用的图像处理程序

工厂里做SOP及测试报告以及员工资格鉴定等常需用到简单的图像处理&#xff0c;PS等软件正版费用不菲&#xff0c;学习起来成本也高。Windows自带的图像处理软件&#xff0c;用起来也不是那么得心应手。因此我用OpenCV与MFC写了一个简单易用的图像处理程序。 程序界面 基于简单…

从传统监控到智能化升级:EasyCVR视频汇聚平台的一站式解决方案

随着科技的飞速发展和社会的不断进步&#xff0c;视频监控已经成为现代社会治安防控、企业管理等场景安全管理中不可或缺的一部分。而在视频监控领域&#xff0c;EasyCVR视频汇聚平台凭借其强大的多协议接入能力&#xff0c;在复杂多变的网络环境中展现出了卓越的性能和广泛的应…

【第15章】Spring Cloud之Gateway网关过滤器(URL黑名单)

文章目录 前言一、常用网关过滤器1. 常用过滤器2. 示例3. Default Filters 二、定义接口服务1. 定义接口 三、自定义过滤器1. 过滤器类2. 应用配置 四、单元测试1. 正常2. 黑名单 总结 前言 上一章我们通过&#xff0c;路由断言根据请求IP地址的黑名单功能&#xff0c;作用范围…

【C#语音文字互转】C#语音转文字(方法一)

Whisper.NET开源项目&#xff1a;https://github.com/sandrohanea/whisper.net/tree/main 一. 环境准备 在VS中安装 Whisper.net&#xff0c;在NuGet包管理器控制台中运行以下命令&#xff1a; Install-Package Whisper.net Install-Package Whisper.net.Runtime其中运行时包…

STL-queue容器适配器

目录 一、queue 1.1 使用 1.2 模拟实现 二、priority_queue 2.1 使用 2.2 仿函数 2.2.1 概念 2.2.2 使用 2.3 模拟实现 一、queue 1.1 使用 具体解释详见官方文档&#xff1a;queue - C Reference (cplusplus.com) queue就是数据结构中的队列&#xff1a;数据结构之…

深度学习中降维的几种方法

笔者在搞网络的时候碰到个问题&#xff0c;就是将特征维度从1024降维到268&#xff0c;那么可以通过哪些深度学习方法来实现呢&#xff1f; 文章目录 1. 卷积层降维2. 全连接层降维3. 使用注意力机制4. 使用自编码器 1. 卷积层降维 可以使用1x1卷积层&#xff08;也叫pointwis…

《大道平渊》· 拾柒 —— 个人的心理定位决定市场

《大道平渊》 拾柒 个人的心理定位决定市场。 对于个人定位来说&#xff0c;个人的心理定位影响你的行为。 比如我的心理定位是经营者&#xff0c;那我的行为则是满足市场需求和解决问题。 因为心理定位的不同&#xff0c;会影响你思考问题的角度。 . 以上皆为个人思考&am…

【为什么不要买运营商的机顶盒?解锁智能电视新体验,从一台刷机机顶盒开始】

【置顶:机顶盒刷机步骤请跳转此链接】 在这个数字化飞速发展的时代&#xff0c;电视早已不再是单一的播放工具&#xff0c;它正逐步演变成为家庭娱乐与信息获取的综合中心。然而&#xff0c;许多家庭在选择机顶盒时&#xff0c;往往会因为惯性或便利而直接选择运营商提供的机顶…

常见中间件漏洞(三、Jboss合集)

目录 三、Jboss Jboss介绍 3.1 CVE-2015-7501 漏洞介绍 影响范围 环境搭建 漏洞复现 3.2 CVE-2017-7504 漏洞介绍 影响范围 环境搭建 漏洞复现 3.3 CVE-2017-12149 漏洞简述 漏洞范围 漏洞复现 3.4 Administration Console弱囗令 漏洞描述 影响版本 环境搭建…

【多线程-从零开始-伍】volatile关键字和内存可见性问题

volatile 关键字 import java.util.Scanner; public class Demo2 { private static int n 0; public static void main(String[] args) { Thread t1 new Thread(() -> { while(n 0){ //啥都不写 } System.out.println("t1 线程结束循环"); }, "…

C++类和对象——中

1. 类的默认成员函数 默认成员函数就是⽤⼾没有显式实现&#xff0c;编译器会⾃动⽣成的成员函数称为默认成员函数。⼀个类&#xff0c;我们不写的情况下编译器会默认⽣成以下6个默认成员函数&#xff0c;需要注意的是这6个中最重要的是前4个&#xff0c;最后两个取地址重载不…

差分专题的练习

神经&#xff0c;树状数组做多了一开始还想着用树状数组来查询差分数组&#xff0c;但是我们要进行所有元素的查询&#xff0c;直接过一遍就好啦 class Solution { public:int numberOfPoints(vector<vector<int>>& nums) {vector<int> c(105, 0);for (i…