当前位置: 首页 > news >正文

子集和问题(回溯法)

目录

​​​​

前言

一、算法思路

二、分析过程

三、代码实现

伪代码:

C++:

总结


前言

问题描述】考虑定义如下的PARTITION问题中的一个变型。给定一个n个整数的集合X={x1,x2,…,xn}和整数y,找出和等于y的X的子集Y。

一、算法思路

 基本思想:确定了解空间的组织结构后,回溯法从开始结点(根结点)出发,以深度优先方式搜索整个解空间。这个开始结点成为活结点,同时也成为当前的扩展结点。在当前的扩展结点处,搜索向纵深方向移至一个新结点。这个新结点就成为新的活结点,并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至最近的一个活结点处,并使这个活结点成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。

二、分析过程

重要❗❗❗

解的n元组:

解是一个包含0和1的n元组,其中每个元素对应集合X中对应位置的元素是否包含在子集Y中。

x的取值范围:
x为集合X中的每个元素,取值为正整数。

约束条件:
子集Y中元素之和等于给定整数y。

目标函数:
找出和等于y的X的子集Y。

三、代码实现

伪代码:

代码如下(示例):这个代码很重要!!!

INPUT:X集合(数组),  整数y
OUTPUT:X集合对应的n元布尔向量,使得对应的元素为1的xi之和为y。1. 初始化n元布尔向量c[n],值为-1;s=02. flag ←false3. k ←1 4. while k≥ 15.     while c[k]≤06.          c[k] ← c[k] +17.          if c[k]=1 then s=s+X[k]   8.            if s=y then set flag ←true, c[k+1]~c[n]←0且从两个while循环退出9.           else if s<y  then k k+110.     end while  11.     s=s-X[k]                12.     c[k] ←-113.      k ←k-114.  end while15.  if flag then output c16.  else output “no solution”

C++:

#include <iostream>
#include <vector>void subsetSumUtil(std::vector<int>& X, std::vector<int>& currSubset, std::vector<int>& result, int target, int currSum, int index) {if (currSum == target) {result = currSubset;return;}if (currSum > target || index >= X.size()) {return;}// Include the current elementcurrSubset.push_back(X[index]);subsetSumUtil(X, currSubset, result, target, currSum + X[index], index + 1);currSubset.pop_back();// Exclude the current elementsubsetSumUtil(X, currSubset, result, target, currSum, index + 1);
}std::vector<int> findSubsetSum(std::vector<int>& X, int y) {std::vector<int> result;std::vector<int> currSubset;subsetSumUtil(X, currSubset, result, y, 0, 0);return result;
}int main() {std::vector<int> X = {3, 34, 4, 12, 5, 2};int y = 9;std::vector<int> subset = findSubsetSum(X, y);if (!subset.empty()) {std::cout << "Subset with sum " << y << " exists: ";for (int num : subset) {std::cout << num << " ";}std::cout << std::endl;} else {std::cout << "No subset with sum " << y << " exists." << std::endl;}return 0;
}

结果:


总结

在考虑PARTITION问题的变种,即找出和等于给定整数y的X的子集Y时,可以使用回溯法来解决。算法的思路是通过搜索所有可能的子集组合,尝试包含或排除每个元素,直到找到合适的子集使得和等于给定整数y。算法的时间复杂度可能为指数级的O(2^n),因为需要搜索所有可能的子集。需要注意的是,回溯法的时间复杂度通常较高,特别是在面对大规模输入时。因此,在实际应用中需要考虑性能问题,并且可能需要对算法进行优化或者考虑其他更高效的解决方案。
 

相关文章:

子集和问题(回溯法)

目录 ​​​​ 前言 一、算法思路 二、分析过程 三、代码实现 伪代码&#xff1a; C&#xff1a; 总结 前言 【问题描述】考虑定义如下的PARTITION问题中的一个变型。给定一个n个整数的集合X{x1,x2,…,xn}和整数y&#xff0c;找出和等于y的X的子集Y。 一、算法思路 基本思想&am…...

【NumPy】全面解析arange函数:高效创建数值范围数组

&#x1f9d1; 博主简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…...

[ C++ ] 深入理解模板( 初 阶 )

函数模板 函数模板格式 template <typename T1, typename T2,......,typename Tn> 返回值类型 函数名(参数列表){} 注意&#xff1a; typename是用来定义模板参数关键字&#xff0c;也可以使用class(切记&#xff1a;不能使用struct代替class) 函数模板的实例化 模板参数…...

UI自动化测试最佳设计模式POM

当使用Selenium进行UI自动化测试时&#xff0c;Page Object Model&#xff08;POM&#xff09;是一种最佳实践的设计模式。POM的核心思想是通过将页面封装成对象&#xff0c;使得测试代码更加清晰、可维护和可重用。 POM的主要组成部分包括页面对象类、元素定位方式和操作方法…...

朋友圈定时发送设置

人日常中不可缺少的一件事&#xff0c;同时也是企业用来触达客户的重要渠道&#xff0c;下面一起来了解下微信朋友圈怎么定时发送呢&#xff1f;...

Spark SQL 中DataFrame DSL的使用

在上一篇文章中已经大致说明了DataFrame APi,下面我们具体介绍DataFrame DSL的使用。DataFrame DSL是一种命令式编写Spark SQL的方式&#xff0c;使用的是一种类sql的风格语法。 文章链接&#xff1a; 一、单词统计案例引入 import org.apache.spark.sql.{DataFrame, SaveMod…...

qt 布局学习笔记

目录 qt下载地址&#xff1a; widget 宽高 管理信息列表源码 c版&#xff1a; pro文件&#xff1a; qt 设置水平布局&#xff0c;里面有两个按钮&#xff0c;每个按钮就变的很宽&#xff0c;怎么设置按钮的精确位置 设置固定大小&#xff1a; 使用弹性空间&#xff08;…...

设计模式复习

一、模式所采用的关系&#xff08;e.g.继承…&#xff09; UML图例 二、各模式的特点、优缺点 1.创建型&#xff08;5种创建型口诀: 抽象工厂 按照 工厂方法&#xff0c;建造 单例 原型&#xff09; 将对象的使用和创建分离&#xff0c;使用对象时无需知道对象的创建细节&a…...

前后端开发入门全攻略:零基础学起

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、前后端开发概览 二、后端开发基础&#xff1a;Flask框架入门 代码案例&#xff1a;Hel…...

Android Studio无法改变Button背景颜色解决办法

大家好&#xff0c;我是咕噜铁蛋&#xff01;今天我来和大家探讨一个在Android开发中常见但可能让初学者感到困惑的问题——如何在Android Studio中改变Button的背景颜色。这个问题看似简单&#xff0c;但实际操作中可能会遇到一些意想不到的挑战。接下来&#xff0c;我将从多个…...

元宇宙三维互动展厅让体验者进入一个充满奇幻与创意的数字世界

元宇宙数字产品展厅搭建编辑器凭借强大的三维可视化互动功能&#xff0c;为用户带来前所未有的沉浸式数字展览体验。 在元宇宙数字产品展厅搭建编辑器中&#xff0c;用户可以轻松打造逼真的三维展览环境&#xff0c;通过VR虚拟现实技术&#xff0c;仿佛置身于一个充满奇幻与创意…...

java高级——Collection集合之List探索(包含ArrayList、LinkedList、Vector底层实现及区别,非常详细哦)

java高级——Collection集合之List探索 前情提要文章介绍提前了解的知识点1. 数组2. 单向链表3. 双向链表4. 为什么单向链表使用的较多5. 线程安全和线程不安全的概念 ArrayList介绍1. 继承结构解析1.1 三个标志性接口1.2 AbstractList和AbstractCollection 2. ArrayList底层代…...

JAVA-->方法的使用详解

JAVA–>方法的使用详解 1.方法的概念及使用 1.1 什么是方法 : 方法就是一个代码片段. 类似于 C 语言中的 “函数”。 1.2 方法定义 / 方法定义 修饰符 返回值类型 方法名称([参数类型 形参 ...]){方法体代码;[return 返回值]; }判断是否为闰年 public class Method{ //…...

基于 vLLM 搭建 DeepSeek-V2 Chat 服务

直奔主题。 安装vLLM 官方实现的代码还没有 merge 到 vLLM 主分支&#xff0c;所以直接 git clone DeepSeek 的分支。 git clone https://github.com/zwd003/vllm.git cd vllm pip install -e .源码安装大概耗时 10 分钟。 OpenAI 接口规范启动 官方 Github 放的是单条推理…...

Kafka 安装教程和基本操作

一、简介 Kafka 是最初由 Linkedin 公司开发&#xff0c;是一个分布式、分区的、多副本的、多订阅者&#xff0c;基于 zookeeper 协调的分布式日志系统&#xff08;也可以当做 MQ 系统&#xff09;&#xff0c;常见可以用于 web/nginx 日志、访问日志&#xff0c;消息服务等等…...

Java 五种内部类演示及底层原理详解

内部类 什么是内部类 在A类的内部定义B类&#xff0c;B类就被称为内部类 发动机类单独存在没有意义 发动机为独立个体 可以在外部其他类里创建内部类的对象去调用方法 类的五大成员 属性 方法 构造方法 代码块 内部类 内部类的访问特点 内部类可以直接访问外部类的成员&a…...

【UnityShader入门精要学习笔记】第十五章 使用噪声

本系列为作者学习UnityShader入门精要而作的笔记&#xff0c;内容将包括&#xff1a; 书本中句子照抄 个人批注项目源码一堆新手会犯的错误潜在的太监断更&#xff0c;有始无终 我的GitHub仓库 总之适用于同样开始学习Shader的同学们进行有取舍的参考。 文章目录 使用噪声上…...

C++ ─── string的完整模拟实现

本博客实现了string的常见接口实现 下面是用到的一些函数&#xff0c;供大家回顾复习 string.h #define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include<iostream> #include<assert.h> using namespace std;namespace bit {class string{public:typedef char*…...

安卓中的图片压缩

安卓中如何进行图片压缩&#xff1f; 在安卓中进行图片压缩通常有以下几种方法&#xff1a; 质量压缩: 通过降低图片的质量来减小文件大小。这可以通过Bitmap的compress()方法实现&#xff0c;其中可以设置压缩质量&#xff08;0-100&#xff09;。 ByteArrayOutputStream baos…...

centOS7.9 DNS配置

1.DNS规划 dns.sohu.com192.168.110.111Awww.sohucom192.168.110.112Aoa.sohu.com 192.168.110.113A 2.安装 bind yum install -y bind bind-utils 3. 编辑主配置文件 vim /etc/named.conflisten- on port 53 { any; }; allow- query { any; }; 4.配置区域文件 …...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...