买瓜(dfs+剪枝)

news/2024/4/16 16:01:49/文章来源:https://blog.csdn.net/m0_74015873/article/details/136566318

题目描述

小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜,每个瓜的重量为 Ai 。

小蓝刀功了得,他可以把任何瓜劈成完全等重的两份,不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为 m 。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜,请输出 −1 。

输入格式

输入的第一行包含两个整数 n, m,用一个空格分隔,分别表示瓜的个数和小蓝想买到的瓜的总重量。

第二行包含 n 个整数 Ai,相邻整数之间使用一个空格分隔,分别表示每个瓜的重量。

输出格式

输出一行包含一个整数表示答案。

样例输入

3 10
1 3 13

样例输出

2

提示

对于 20% 的评测用例,∑n≤10;

对于 60% 的评测用例,∑n≤20;

对于所有评测用例,1 ≤n≤30,1≤ Ai ≤ 10^9 ,1 ≤ m ≤ 10^9

思路:

使用深度优先搜索解决, 对每个瓜的三种选择进行搜索, 解空间树是一颗完全三叉树, 时间复杂度为O(3^n), 肯定会超时, 故需要进行剪枝。

买半个瓜时需要将重量除2,会产生小数,故可以将重量数组都乘2,最大重量也乘2。

搜索时需要记录三个状态,当前层数pos,当前总重量sum,当前劈瓜的次数cnt,以下情况需要剪枝:
1)当前劈瓜次数大于已求得的最小次数,即cnt>ans
2)当前重量之和大于要求的重量,即sum>m

但是这样仍然会超时,还可以将重量数组降序排列,使得更快剪枝。还可以创建一个重量数组的后缀数组suf,这样在搜索时可以利用其剪枝:若当前重量加上剩余的所有瓜重量之和小于要求的重量,剪枝。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=33;
double a[N];
double s[N]; 
bool st[N];
int n;
double m;
int cnt=1e9;
//三种状态 整个 一半 不要
//dfs+剪枝 
//参数 当前层数 当前的西瓜的总重量 当前切了多少次 
void dfs(int pos,double sum,int num)
{//当sum==m时 取最小的 返回上一层 if(sum==m){cnt=min(cnt,num);return ;}//剪枝 sum+s[n]-s[pos-1] 是求当前sum加上之后所有的数均不能组成时 剪枝一下 if(sum>m||pos>n||cnt<=num||sum+s[n]-s[pos-1]<m) return ;dfs(pos+1,sum+a[pos],num);//整个要 dfs(pos+1,sum+(a[pos]/2),num+1);//半个 dfs(pos+1,sum,num);//都不要 
}
//从大到小排 尽量减少切一半的次数 
double cmp(double x,double y)
{return x>y;} 
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) {cin>>a[i];}//排序 从大到小排 sort(a+1,a+1+n,cmp);//求前缀和 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];dfs(1,0,0);if(cnt==1e9) cout<<"-1"<<endl;else cout<<cnt<<endl; return 0;
}

 

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

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

相关文章

垃圾收集器底层算法

垃圾收集器底层算法 三色标记 在并发标记的过程中&#xff0c;因为标记期间应用线程还在继续跑&#xff0c;对象间的引用可能发生变化&#xff0c;多标和漏标的情况就有可能发生&#xff0c;这里我们引入“三色标记”来给大家解释下把Gcroots可达性分析遍历对象过程中遇到对象…

灯塔:CSS笔记(2)

一 选择器进阶 后代选择器&#xff1a;空格 作用&#xff1a;根据HTML标签的嵌套关系&#xff0c;&#xff0c;选择父元素 后代中满足条件的元素 选择器语法&#xff1a;选择器1 选择器2{ css } 结果&#xff1a; *在选择器1所找到标签的后代&#xff08;儿子 孙子 重孙子…

opencv dnn模块 示例(24) 目标检测 object_detection 之 yolov8-pose 和 yolov8-obb

前面博文【opencv dnn模块 示例(23) 目标检测 object_detection 之 yolov8】 已经已经详细介绍了yolov8网络和测试。本文继续说明使用yolov8 进行 人体姿态估计 pose 和 旋转目标检测 OBB 。 文章目录 1、Yolov8-pose 简单使用2、Yolov8-OBB2.1、python 命令行测试2.2、opencv…

iOS-系统弹窗调用

代码&#xff1a; UIAlertController *alertViewController [UIAlertController alertControllerWithTitle:"请选择方式" message:nil preferredStyle:UIAlertControllerStyleActionSheet];// style 为 sheet UIAlertAction *cancle [UIAlertAction actionWithTit…

Unity性能优化篇(七) UI优化注意事项以及使用Sprite Atlas打包精灵图集

UI优化注意事项 1.尽量避免使用IMGUI(OnGUI)来做游戏时的UI&#xff0c;因为IMGUI的开销比较大。 2.如果一个UGUI的控件不需要进行射线检测&#xff0c;则可以取消勾选Raycast Target 3.尽量避免使用完全透明的图片和UI控件。因为即使完全透明&#xff0c;我们看不见它&#xf…

C#,老鼠迷宫问题的回溯法求解(Rat in a Maze)算法与源代码

1 老鼠迷宫问题 迷宫中的老鼠&#xff0c;作为另一个可以使用回溯解决的示例问题。 迷宫以块的NN二进制矩阵给出&#xff0c;其中源块是最左上方的块&#xff0c;即迷宫[0][0]&#xff0c;目标块是最右下方的块&#xff0c;即迷宫[N-1][N-1]。老鼠从源头开始&#xff0c;必须…

Docker安装主从数据库

我自己的主数据库名字 user_muster 密码是123456 从数据库 就是slave1 名字是root 密码是123456 首先开启docker后直接执行命令 docker run -d \ -p 3307:3306 \ -v /xk857/mysql/master/conf:/etc/mysql/conf.d \ -v /xk857/mysql/master/data:/var/lib/mysql \ -e MYSQL_R…

JavaWeb笔记 --- 一JDBC

一、JDBC JDBC就是Java操作关系型数据库的一种API DriverManager 注册驱动可以不写 Class.forName("com.mysql.jdbc.Driver"); Connection Statement ResultSet PrepareStatement 密码输入一个SQL脚本&#xff0c;直接登录 预编译开启在url中 数据库连接池

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:ImageAnimator)

提供帧动画组件来实现逐帧播放图片的能力&#xff0c;可以配置需要播放的图片列表&#xff0c;每张图片可以配置时长。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 子组件 无 接口 ImageAni…

GO语言接入支付宝

GO语言接入支付宝 今天就go语言接入支付宝写一个教程 使用如下库&#xff0c;各种接口较为齐全 "github.com/smartwalle/alipay/v3"先简单介绍下加密&#xff1a; 试想&#xff0c;当用户向支付宝付款时&#xff0c;若不进行任何加密&#xff0c;那么黑客就可以任…

C++:模版进阶 | Priority_queue的模拟实现

创作不易&#xff0c;感谢三连支持 一、非类型模版参数 模板参数分类为类型形参与非类型形参。 类型形参即&#xff1a;出现在模板参数列表中&#xff0c;跟在class或者typename之类的参数类型名称。 非类型形参&#xff0c;就是用一个常量作为类(函数)模板的一个参数&…

智能音箱技术解析

目录 前言智能音箱执行步骤解析1.1 探测唤醒词或触发词1.2 语音识别1.3 意图识别1.4 执行指令 2 典型的智能音箱2.1 百度小度音响2.2 小米小爱同学2.3 苹果 HomePod 3 功能应用举例3.1 设置计时器3.2 播放音乐 结语 前言 智能音箱已经成为日常生活中不可或缺的一部分&#xff…

解决方案|珈和科技推出农业特色产业数字化服务平台

今年中央一号文件提出&#xff0c;鼓励各地因地制宜大力发展特色产业&#xff0c;支持打造乡土特色品牌。 然而&#xff0c;农业特色产业的生产、加工和销售仍然面临诸多挑战。产品优质不能优价&#xff0c;优质不能优用的现象屡见不鲜&#xff0c;产业化程度低、生产附加值不…

【SpringMVC】快速体验 SpringMVC接收数据 第一期

文章目录 一、SpringMVC 介绍1.1 主要作用1.2 核心组件和调用流程理解 二、快速体验三、SpringMVC接收数据3.1 访问路径设置3.1.1 精准路径匹配3.1.2 模糊路径匹配3.1.3 类和方法级别区别3.1.4 附带请求方式限制3.1.5 进阶注解 与 常见配置问题 3.2 接收参数&#xff08;重点&a…

mxxWechatBot微信机器人说明

大家伙&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号&#xff1a;雄雄的小课堂。 免责声明&#xff1a;该工具仅供学习使用&#xff0c;禁止使用该工具从事违法活动&#xff0c;否则永久拉黑封禁账号&#xff01;&#xff01;&#xff01;本人不对任何工具的使用负责&am…

粘包与拆包

优质博文&#xff1a;IT-BLOG-CN 一、粘包出现的原因 服务端与客户端没有约定好要使用的数据结构。Socket Client实际是将数据包发送到一个缓存buffer中&#xff0c;通过buffer刷到数据链路层。因服务端接收数据包时&#xff0c;不能断定数据包1何时结束&#xff0c;就有可能出…

吴恩达deeplearning.ai:机器学习的开发过程与优化方法

以下内容有任何不理解可以翻看我之前的博客哦&#xff1a;吴恩达deeplearning.ai专栏 我想在接下来分析下开发机器学习系统的过程&#xff0c;这样当你自己动手时&#xff0c;能够做出更加正确的判断。 机器学习开发的迭代 Iterative loop of ML development 决定模型架构 第…

酷开科技以酷开系统为媒介,打造欢乐生活场景

家人相聚在一起的时光总是那么美好&#xff0c;在欢聚的日子里&#xff0c;我们也总是希望能够让时间变得慢一点&#xff0c;再慢一点&#xff0c;但是随着春节假期的结束&#xff0c;很多人已经开始了新一年的忙碌&#xff0c;大家纷纷回到工作、学习岗位&#xff0c;回归之前…

GBU1510-ASEMI逆变器整流桥GBU1510

编辑&#xff1a;ll GBU1510-ASEMI逆变器整流桥GBU1510 型号&#xff1a;GBU1510 品牌&#xff1a;ASEMI 封装&#xff1a;GBU-4 最大重复峰值反向电压&#xff1a;1000V 最大正向平均整流电流(Vdss)&#xff1a;15A 功率(Pd)&#xff1a;大功率 芯片个数&#xff1a;4…

Java后端核心——Servlet

目录 一.概述 二.基础实现 1.导入坐标 2.定义实现类 3.注解 4.访问Servlet 三.执行流程 四.生命周期 1.加载和实例化 2.初始化 3.请求处理 4.服务终止 五.方法 1.init 2.service 3.destroy 4.getServletInfo 5.getServletConfig 六.体系结构 七.urlPatter…