当前位置: 首页 > 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.配置区域文件 …...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...