技术标签： 算法 java 集合覆盖问题 贪心算法 算法与数据结构
贪心算法的核心思想可以总结为：贪心算法总是做出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解，如单源最短路经问题，最小生成树问题等。虽然在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似。
假设你办了个广播节目，要让国内的 8 个重要城市的听众都收听得到。为此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。
| 广播台 | 覆盖地区 |
|---|---|
| K1 | 北京、上海、天津 |
| K2 | 广州、北京、深圳 |
| K3 | 成都、上海、杭州 |
| K4 | 上海、天津 |
| K5 | 杭州、大连 |
如何选择最少的广播台，让所有的城市都可以接收到信号？
每个广播台都覆盖特定的区域，不通过的广播覆盖的区域可能是重叠的。如何找出覆盖 8 个城市的最小广播台集合呢？
首先我们最容易想到的办法就是穷举法：
上面这个方法确实可以求得最终结果，但是问题在于 n 个广播台可能的集合有 2ⁿ 个，因此运行时间为 O(2ⁿ)。如果广播台不多，比如只有 5~10 个，这个方法倒还可行。但是一旦问题的规模变大，广播台的数量增多，需要的时间将激增。假设每秒可以计算出 10 个集合，那么所需的时间如下表所示：
| 广播台数量 | 需要的时间 |
|---|---|
| 5 | 3.2 秒 |
| 10 | 102.4 秒 |
| 32 | 13.6 年 |
| 100 | 4 x 10²¹ 年 |
显然，使用穷举所有集合的方法不是一个明智的选择。
针对这类集合覆盖问题，贪心算法是一个比较合适的算法，虽然贪心算法不一定能够得到最优解，但是它可以得到非常接近的解。
对于本题，贪心算法的基本思想如下：
可以看到，使用贪心算法解决集合覆盖问题的思路贯彻着 “选择当下看来最好的选择” 这样的思想。简单来说就是走好每一步路，最终得到的结果必定不会太差。
贪心算法不仅简单，而且运行速度也很快。对于本题，贪心算法的运行时间为 O(n²)，其中 n 为广播台的数量。
首先来说一下代码实现的思路：
cities，存放所有的城市；broadcast，广播站作为键，对应的城市作为值；selectedList，用于存放已选择的广播站；selectedList中；cities 中移除，同时将广播站从散列表中移除；完整的代码实现如下 ：
public static void main(String[] args) {
HashMap<String, Set> broadcast = new HashMap<>(); // 用于存放广播和覆盖的城市
HashMap<String, Set> selectedList = new HashMap<>(<文章浏览阅读1.2k次。背景因为目前在做一个ns3上搭建网络的实验，需要安装特定版本的qt。中间遇到了很多问题，来记录一下。问题描述ubuntu 16.04自带qt4，但我需要的是qt5（qt5.7+)。如果采用命令行安装qt5-default（很容易搜到的方法）：1.apt-get安装qtsudo apt-get install cmake qt5-default qtcreator安装的并不是指定版本..._qt5.7.1 ubuntu离线安装
文章浏览阅读229次。spring boot整合cxf发布webservice服务和cxf客户端调用本案例使用maven方式核显文件清单服务端1.pom.xml<?xml version="1.0" encoding="UTF-8"?><project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation="htt_webservice cxf客户端调用
文章浏览阅读1.9k次。 在开发SpringBoot的项目过程中，我们有时候为了区分和application.properties配置文件提供的默认配置，我们需要提供自己定义的配置文件如applicationDynamic.properties。在这里我介绍下如何读取自定义的配置文件，SpringBoot版本使用的是1.5.6.RELEASE。 1.定义自定义的配置文件applicationDyn..._springboot可以识别除了application之外的配置文件吗
文章浏览阅读276次，点赞11次，收藏3次。需要注意的是，实践是提高技能的关键，因此在每个阶段都应注重动手实践和项目经验的积累。研究前沿技术：关注计算机视觉领域的最新研究成果，如深度学习的新模型、新算法等。方法：项目实践：选择一些计算机视觉的项目进行实践，如人脸识别、车牌识别等。目标：深入理解计算机视觉的核心概念，如特征提取、图像分割、目标识别等。掌握基础算法：学习图像处理的基本算法，如图像增强、滤波、边缘检测等。目标：在掌握基础知识和实践经验的基础上，进行更深层次的研究和创新。目标：了解计算机视觉的基本概念和原理，掌握图像处理的基础知识。
文章浏览阅读445次。SA_INTERRUPT当置位了, 这表示一个"快速"中断处理. 快速处理在当前处理器上禁止中断来执行 (这个主题在"快速和慢速处理"一节涉及).SA_SHIRQ这个位表示中断可以在设备间共享. 共享的概念在"中断共享"一节中略述.SA_SAMPLE_RANDOM这个位表示产生的中断能够有贡献给/dev/random 和 /dev/urandom 使用的加密 池. 这些设备在读取时返回真正的随机数..._linux如何中断安装
文章浏览阅读3.7w次，点赞410次，收藏2.9k次。所用教材：《数据库系统概论(第5版)》王珊 萨师煊 编著 理论与实践相结合的好书本文大部分写自同学，本作者稍加详解。感谢该同学，这些题目做透能拿高分！一、简答题（来自第一章 绪论 课后题P34）10’1. 试述数据、数据库、数据库管理系统、数据库系统的概念。 数据：描述事物的符号记录。 数据库：长期储存在计算机内、有组织的、可共享的大量数据的集合。..._数据库系统概论第五版期末试题
文章浏览阅读5.3k次，点赞3次，收藏11次。你可以把它理解为形状，一个对象需要有什么样的属性，函数需要什么参数或返回什么样的值，数组应该是什么样子的，一个类和继承类需要符合什么样的描述等等。需要注意的是类 Interface 只会检查实例的属性，静态属性是需要额外定义一个 Interface；接口就是用来定义一个类结构，定义一个类中应该包含哪些属性和方法，同时接口也可以当成类型声明去使用。混合类型的接口就是使用同一个 Interface 来描述函数或者对象的属性或方法。接口可以约束对象,函数,类的结构和类型,是一种代码协作必须遵守的契约。_ts interface
文章浏览阅读1.6k次。微服务的优点是服务模块化，高内聚，低耦合。随着服务数量的增多，服务的监控也变得异常困难。springcloud引入提供了admin组件，人性化UI管理界面可以对所有服务的运行状态进行监控，并提供告警等功能。一.springboot-admin简介显示健康状况显示详细信息，例如JVM和内存指标数据源指标缓存指标关注并下载日志文件查看jvm系统和环境属性查看Spring Boot配置..._spring cloud admin
文章浏览阅读6.5w次，点赞5次，收藏52次。某些时候当Linux系统下划分了新的分区后，需要将这些分区设置为开机自动挂载，否则，Linux是无法使用新建的分区的。 /etc/fstab 文件负责配置Linux开机时自动挂载的分区。Windows的文件结构是多个并列的树状结构，最顶部的是不同的磁盘（分区），如：C，D，E，F等。Linux的文件结构是单个的树状结构。最顶部的为根目录，即/。在根目录下，分为多个子目录，包括/bi_fstab defaults
文章浏览阅读2.8k次。前言：好久没有写CSDN的blog了，刚刚写blog的时候，我还是一个hello world的水平。真可谓“条条大路通CS”，花了一年时间，从EE专业自学到了CS了。也当是小有所成。希望，一起在路上的朋友，我们一起加油！问题背景在使用QT开发window应用程序的时候，需要使用到OpenGL的库来绘制3D地球。问题详细使用QT creator这个IDE，在build项目的时候，报下面的错误LNK1_vs2022 错误lnk1104无法打开文件“glut32.lib
文章浏览阅读4.1k次，点赞4次，收藏18次。正则 RegExp：由相关元字符和修饰符组成的一个规则，匹配 验证和捕获（只用来处理字符串）可以理解为两个斜杠中间包含一些内容就是正则元字符：/元字符/ 两个斜杠之间包起来的内容正则：它就是用来处理字符串的一个规则；●正则匹配：编写一个规则，验证某个字符串是否符合这个规则，正则匹配使用的是test方法●正则捕获：编写一个规则，在一个字符串中把复合规则的内容都获取到 正则捕获使用的方法 正则的exec方法、字符串中的split、replace、match等方法都支持正则正则创建● 字面_正则
文章浏览阅读3.5k次。 SPS: sequence parameter sets它指的是码流对应的profile. 1.1 基线profile(Baseline profile)遵循基线profile的码流应该遵循以下的约束: a) 只有I和P切片存在b) NAL单元流不应该有范围在2到4的nal_unit_type值,包括2和4.c) 序列参数集(sps)的frame_mbs__h.264 sequence parameter set 各个字节的含义