[DFS深度优先搜索]集合里的乘法
集合里的乘法
题目描述
给定一个目标数T和一个整数集合S,判断是否存在S的一个非空子集,子集中的数相乘的积为T。
关于输入
输入为两行。
第一行为目标数T,和S中的元素个数N,以空格隔开。
第二行为S中的N个元素,以空格隔开。
其中 N <= 16。
关于输出
如果可以,则输出YES,否则输出NO。
例子输入
12 5 1 2 3 4 5
例子输出
YES
解题分析
这个算法的核心思想是使用深度优先搜索(DFS)遍历所有可能的子集,并计算它们的乘积。如果找到一个子集的乘积等于目标数,就返回YES,否则返回NO。
以下是该算法的详细步骤:
1. 首先,我们读取目标数T和集合S的元素。集合S的元素被存储在一个数组中,数组的索引从0开始。
2. 然后,我们调用深度优先搜索函数`dfs`,开始时的索引为0,乘积为1。这意味着我们从集合的第一个元素开始搜索,初始的乘积是1(因为任何数乘以1都等于它自己)。
3. 在`dfs`函数中,我们首先检查是否已经找到了解决方案(`flag`是否为1)或者当前乘积是否已经超过了目标数T。如果是的话,我们就直接返回,不再继续搜索。这是一种剪枝策略,可以避免无效的搜索,提高算法的效率。
4. 然后,我们检查当前的乘积是否等于目标数,如果是的话,我们就设置`flag`为1并返回。这表示我们已经找到了一个满足条件的子集。
5. 如果当前的索引已经达到了集合的大小,这意味着我们已经遍历了所有的元素,但还没有找到满足条件的子集,所以我们就返回。
6. 否则,我们对当前索引的元素有两种选择:一是选择它(将它乘入当前的乘积),二是不选择它(保持当前的乘积不变)。我们对这两种选择都进行搜索。这是深度优先搜索的核心步骤,通过递归调用`dfs`函数,我们可以遍历所有可能的子集。
7. 在主函数中,如果`flag`为1,说明我们找到了一个解决方案,输出YES。否则,输出NO。
这个算法的时间复杂度是O(2^n),其中n是集合的大小。因为对于集合中的每一个元素,我们都有两种选择:选择它或者不选择它。所以总共有2^n种可能的子集。由于题目中给出集合的大小不超过16,所以这个算法在时间上是可行的。
代码实现
#include <stdio.h>int N;
long long T, S[16];
char flag;void dfs(int index, long long product) {if (flag || product > T) return;if (product == T) {flag = 1;return;}if (index == N) return;dfs(index + 1, product * S[index]);dfs(index + 1, product);
}int main() {scanf("%lld %d", &T, &N);for (int i = 0; i < N; i++) {scanf("%lld", &S[i]);}dfs(0, 1);if (flag) {printf("YES\n");} else {printf("NO\n");}return 0;
}
相关文章:
[DFS深度优先搜索]集合里的乘法
集合里的乘法 题目描述 给定一个目标数T和一个整数集合S,判断是否存在S的一个非空子集,子集中的数相乘的积为T。 关于输入 输入为两行。 第一行为目标数T,和S中的元素个数N,以空格隔开。 第二行为S中的N个元素,以空…...
K8s 中 Pod OOMKilled 原因
目录 Exit Code 137 解决方案 JVM 感知 cgroup 限制 使用 JDK9 的容器感知机制尝试 问题分析 容器内部感知 CGroup 资源限制 在 Java10 中,改进了容器集成 JVM 参数 MaxDirectMemorySize -XX:MaxDirectMemorySize 的默认值是什么? 其他获取 ma…...
为什么程序员最应该学习的是运营与销售,而不是技术?
大概几个月前,我加入了某副业交流群。这里人才很多,不光是传统意义上的程序员,也有公司老板、偏门大佬、产品经理等。 群里的聊天主题就是搞钱俩字,大家讨论着如何搞钱,分享每日收益情况,以及自己做的产品等…...
MySql数据库常用指令(五)多表连接
MySql数据库常用指令(五)多表连接 一、内连接,或等值连接二、左连接三、右连接 实际应用中,我们常常要连接几个不同的MySQL表,因此在 SELECT, UPDATE 和 DELETE 语句中使用 Mysql 的 JOIN 来联合多表查询 INNER JOIN(内…...
Centos7使用rpm安装mysql 5.7.43
Centos7使用rpm安装mysql 5.7.43 1、下载rpm包 wget https://downloads.mysql.com/archives/get/p/23/file/mysql-5.7.43-1.el7.x86_64.rpm-bundle.tar2、解压并安装 tar xf mysql-5.7.43-1.el7.x86_64.rpm-bundle.tar yum -y install mysql-*3、按需修改mysql配置 #注意&a…...
补充:如何提高selenium的运行速度?
已经通读该专栏文章的同学,或许对UI自动化测试有了一定的掌握,细心的同学肯定会发现一个问题,当用例量达到一定程度时,对于整体用例的执行速度肯定不会很满意。除了应用多线程运行用例的方式加快速度,有没有其他的方法呢? 今天告诉大家,方法是有的!也是本人新学的。即…...
使用Python+Redis实现文章投票网站后端功能
1.实现投票功能,2.创建文章数据,3.对文章进行排序。 实现投票功能 实现投票功能,要注重文章的时效性与投票的公平性,所以需要给投票功能加上一些约束条件: 文章发布满一个星期后&…...
SpringBoot 环境使用 Redis + AOP + 自定义注解实现接口幂等性
目录 一、前言二、主流实现方案介绍2.1、前端按钮做加载状态限制(必备)2.2、客户端使用唯一标识符2.3、服务端通过检测请求参数进行幂等校验(本文使用) 三、代码实现3.1、POM3.2、application.yml3.3、Redis配置类3.4、自定义注解…...
Leetcode—18.四数之和【中等】
2023每日刷题(四十一) Leetcode—18.四数之和 实现代码 class Solution { public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ans;sort(nums.begin(), nums.end());int n …...
springsecurity6配置二
一、springsecurity6自定义认证异常处理器 1.1 AuthenticationEntryPointImpl.java package com.school.information.core.security.handler;import com.alibaba.fastjson.JSON; import com.school.information.enums.result.ResultStatusEnum; import com.school.informatio…...
php如何对比浮点数大小(bccomp函数)
第一部分,常规例子: 例1:左边比右边小,结果:-1 //示例,左边比右边小返回值:-1 $price1 2.14; $price2 3.14; $result bccomp($price1, $price2, 2); echo 对比结果:.$result;//…...
服务号和订阅号哪个好
服务号和订阅号有什么区别?服务号转为订阅号有哪些作用?在推送频率上来看,服务号每月能推送四条消息,而订阅号可以每天(24小时)推送一条消息。如果企业开通公众号的目的是提供服务,例如售前资讯…...
面试问题--智能指针
什么是智能指针? 当你在编写程序时,可能需要在运行时动态分配内存来存储数据。在传统的C中,你可能会使用 new 和 delete 操作符来手动管理内存。但是这样容易出现一些问题,比如忘记释放内存导致内存泄漏,或者释放了之…...
向量机SVM原理理解和实战
目录 概念场景导入 点到超平面的距离公式 最大间隔的优化模型 硬间隔、软间隔和非线性 SVM 用 SVM 如何解决多分类问题 1. 一对多法 2. 一对一法 SVM主要原理和特点 原理 优点 缺点 支持向量机模型分类 SVM实战如何进行乳腺癌检测 数据集 字段含义 代码实现 参…...
什么是 Node.js?
在 Node.js 出现之前,最常见的 JavaScript 运行时环境是浏览器,也叫做 JavaScript 的宿主环境。浏览器为 JavaScript 提供了 DOM API,能够让 JavaScript 操作浏览器环境(JS 环境)。 2009 年初 Node.js 出现了…...
系列九、声明式事务(xml方式)
一、概述 声明式事务(declarative transaction management)是Spring提供的对程序事务管理的一种方式,Spring的声明式事务顾名思义就是采用声明的方式来处理事务。这里所说的声明,是指在配置文件中声明,用在Spring配置文件中声明式的处理事务来…...
c盘清理——常用方法和工具整理
背景 最近c盘满了,只剩下1-2G,周末有空清理一下。对这块不太熟悉,下面只是把今天网上看到的比较好用的工具整理一下。 使用工具 磁盘大小查看工具——TreeSize(收费) 之前都是右键一个个看每个文件的大小࿰…...
【React】打包体积分析 source-map-explorer
通过分析打包体积,才能知道项目中的哪部分内容体积过大,方便知道哪些包需要进一步优化。 使用步骤 安装分析打包体积的包:npm i source-map-explorer在 package.json 中的 scripts 标签中,添加分析打包体积的命令对项目打包&…...
Zookeeper(一):在WSL单机搭建Zookeeper伪集群
目录 Zookeeper1 启动单个Zookeeper实例1.1 下载Zookeeper安装包并解压1.2 添加环境变量1.3 修改默认配置1.4 新建数据存储目录和日志目录1.5 启动Zookeeper1.6 停止Zookeeper 2 搭建Zookeeper集群2.1 新建集群目录2.2 配置环境变量2.3 创建节点目录2.4 修改配置2.5 创建节点ID…...
Go语法的特殊之处
上文我们讲了GO模块引入指令Go Mod,本文讲述Go语法的特殊之处 : 单变量 : hello:“hello” Go 语言中新增了一个特殊的运算符:,这个运算符可以使变量在不声明的情况下直接被赋值使用。其使用方法和带值声明变量类似,只是少了var关键字&…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...
Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...
