洛谷P1049装箱问题 ————递归+剪枝+回溯

没没没没没没没没没错,又是一道简单的递归,只不过加了剪枝,我已经不想再多说,这道题写了一开始写了普通深搜,然后tle了一个点,后面改成剪枝,就ac了,虽然数据很水,但是不妨碍我们练习搜索。

先画个草图:

从1开始找,找下一层最左边的2,判断箱子里是否能装下这个物体,如果能,装进去。(现在箱子里装了(1,2) 体积是(8+3=11)

然后继续下一层继续判断,能否装下。(找最左边的3,现在箱子里装了(1,2,3) 体积是(8+3+12=23)

再找下一个,4,发现23+7>24,就是箱子装不下了,那就跳过4,往下搜。

当搜完了,我们就返回上一层重复这个步骤即可。

上代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
const int N = 30+7;
const int V = 2e4 + 7;
int a[N];
int flag[N];
int n, v, ans=0x7fffffff;
void dfs(int x, int v) {
		ans = min(ans, v);
	for (int i = x; i < n; i++) {
		if (flag[i] == 0) {
			if (v - a[i] >= 0) {
				flag[i] = 1;
				dfs(i + 1, v - a[i]);
				flag[i] = 0;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> v >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	dfs(0, v);
	cout << ans;
}

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

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

相关文章

第96步 深度学习图像目标检测:FCOS建模

基于WIN10的64位系统演示 一、写在前面 本期开始&#xff0c;我们继续学习深度学习图像目标检测系列&#xff0c;FCOS&#xff08;Fully Convolutional One-Stage Object Detection&#xff09;模型。 二、FCOS简介 FCOS&#xff08;Fully Convolutional One-Stage Object D…

iOS强引用引起的内存泄漏

项目中遇到一个问题&#xff1a; 1.在A页面的ViewDidLoad 方法里写了一个接收通知的方法&#xff0c;如下图&#xff1a; 然后在B页面发送通知 &#xff08;注&#xff1a;下图的NOTI 是 [NSNotificationCenter defaultCenter] 的宏&#xff0c; 考虑一下可能有小白看这篇文章…

物联网中基于信任的安全性调查研究:挑战与问题

A survey study on trust-based security in Internet of Things: Challenges and issues 文章目录 a b s t r a c t1. Introduction2. Related work3. IoT security from the one-stop dimension3.1. Output data related security3.1.1. Confidentiality3.1.2. Authenticity …

【vue_2】创建一个弹出权限不足的提示框

定义了一个名为 getUserRole 的 JavaScript 函数&#xff0c;该函数接受一个参数 authorityId&#xff0c;根据这个参数的不同值返回相应的用户角色字符串。这段代码的目的是根据传入的 authorityId 值判断用户的角色&#xff0c;然后返回相应的角色名称。 如果 authorityId 的…

Visual Studio 中文注释乱码解决方案

在公司多人开发项目中经常遇到拉到最新代码&#xff0c;发现中文注释都是乱码&#xff0c;很是emjoy..... 这是由于编码格式不匹配造成的&#xff0c;如果你的注释是 UTF-8 编码&#xff0c;而文件编码是 GBK 或者其他编码&#xff0c;那么就会出现乱码现象。一般的解决办法是…

STM32-使用固件库新建工程

参考链接: 【入门篇】11-新建工程—固件库版本&#xff08;初学者必须认认真真看&#xff09;_哔哩哔哩_bilibili 使用的MCU是STM32F103ZET6 。 这篇参考的是野火的资料&#xff0c;可以在“野火大学堂”或者它的论坛上下载。&#xff08;我通常是野火和正点原子的资料混着看的…

【AI认证笔记】NO.2人工智能的发展

目录 一、人工智能的发展里程碑 二、当前人工智能的发展特点 1.人工智能进入高速发展阶段 2.人工智能元年 三、人工智能高速发展的三大引擎 1.算法突破 2.算力飞跃 3.数据井喷 四、AI的机遇 五、AI人才的缺口 六、行业AI 人工智能算法&#xff0c;万物互联&#xff…

基于mediapipe的人手21点姿态检测模型—CPU上检测速度惊人

前期的文章,我们介绍了MediaPipe对象检测与对象分类任务,也分享了MediaPipe的人手手势识别。在进行人手手势识别前,MediaPipe首先需要进行人手的检测与人手坐标点的检测,经过以上的检测后,才能把人手的坐标点与手势结合起来,进行相关的手势识别。 MediaPipe人手坐标点检测…

案例022:基于微信小程序的行政复议在线预约系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…

将 Hexo 部署到阿里云轻量服务器(保姆级教程)

将 Hexo 部署到阿里云轻量服务器(保姆级教程) 顺哥轻创 1 前言 作为有梦想的,有追求的程序员,有一个自己的个人博客简直就是必须品。你可以选择 wordpress 这种平台,直接使用,在任何地方只要有网络就能写博客。还可以选择 hexo 这种静态博客,但是发文章就没有那么随心…

CentOS7安装Docker运行环境

1 引言 Docker 是一个用于开发&#xff0c;交付和运行应用程序的开放平台。Docker 使您能够将应用程序与基础架构分开&#xff0c;从而可以快速交付软件。借助 Docker&#xff0c;您可以与管理应用程序相同的方式来管理基础架构。通过利用 Docker 的方法来快速交付&#xff0c;…

爬虫项目实战:利用基于selenium框架的爬虫模板爬取豆瓣电影Top250

&#x1f44b; Hi, I’m 货又星&#x1f440; I’m interested in …&#x1f331; I’m currently learning …&#x1f49e; I’m looking to collaborate on …&#x1f4eb; How to reach me … README 目录&#xff08;持续更新中&#xff09; 各种错误处理、爬虫实战及模…

VRRP的交换机VRRP主备配置例子

拓朴如下&#xff1a; 主要配置如下&#xff1a; [S1] vlan batch 10 20 # interface Vlanif10ip address 10.1.1.1 255.255.255.0vrrp vrid 1 virtual-ip 10.1.1.254vrrp vrid 1 priority 200vrrp vrid 1 preempt-mode timer delay 20 # interface Vlanif20ip address 13.1.1…

死磕Nacos系列:Nacos在我的SpringCloud项目中做了什么?

Nacos服务注册 我们一个SpringCloud项目中集成了Nacos&#xff0c;当项目启动成功后&#xff0c;就可以在Nacos管理界面上看到我们项目的注册信息&#xff0c;还可以看到项目的健康状态等等信息&#xff1a; 那Nacos是什么时候进行了哪些操作的呢&#xff1f;今天我们来一探究…

【从浅识到熟知Linux】基本指定之find、grep、head和tail

&#x1f388;归属专栏&#xff1a;从浅学到熟知Linux &#x1f697;个人主页&#xff1a;Jammingpro &#x1f41f;每日一句&#xff1a;一篇又一篇&#xff0c;学写越上头。 文章前言&#xff1a;本文介绍find、grep、head和tail指令用法并给出示例和截图。 文章目录 find基本…

Jquery ajax 进行网络请求,同步阻塞引起的UI线程阻塞 (loading图片不显示 )

jax重新获取数据刷新页面功能&#xff0c;因为ajax属于耗时操作&#xff0c;想在获取数据且加载页面时显示加载遮罩层&#xff0c;结果发现了ajax的好多坑。 ajax 执行http网络请示时时&#xff0c;让遮罩层显示&#xff0c;ajax加载完毕后遮罩层消失。 因为我想让loadChart()…

mysql 更改密码

由于两台设备的mysql数据库的密码不一样&#xff0c;开发时每次连接数据库都需要更改配置文件&#xff0c;所以想修改一下mysql数据库的密码。 mysql 修改密码千万不要直接修改&#xff0c;直接修改的话会出现两种情况&#xff1a; 1&#xff0c;修改成功&#xff0c;无法登录。…

elasticsearch 索引库操作和文档操作

文章目录 索引库操作mapping映射属性索引库的CRUD&#xff08;创建&#xff0c;读取&#xff0c;更新&#xff0c;删除&#xff09;创建索引库和映射基本语法&#xff1a;示例&#xff1a; 查询索引库修改索引库删除索引库 文档操作新增文档查询文档删除文档修改文档全量修改增…

通过互联网代理部署Docker+Kubernetes 1.28.1

一、背景 在公司环境中&#xff0c;我们往往都是无法直接连接外网的&#xff0c;之前写过一篇文章&#xff0c;是通过外网自建的中转机器下载需要的离线包&#xff0c;并在内网搭建一个harbor&#xff0c;通过harbor的方式搭建了一个kubernetes&#xff0c;但是这种方式还是有…

蓝牙运动耳机哪个好?蓝牙运动耳机排行榜前十名

​在运动中&#xff0c;音乐可以激发你的热情和动力&#xff0c;而一款好的运动耳机则可以让你更好地享受音乐。然而&#xff0c;市面上的运动耳机品牌和型号众多&#xff0c;质量参差不齐。所以&#xff0c;今天精选了5款市面上比较优秀的运动耳机给大家参考&#xff0c;是你运…