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

洛谷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;
}

相关文章:

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

没没没没没没没没没错&#xff0c;又是一道简单的递归&#xff0c;只不过加了剪枝&#xff0c;我已经不想再多说&#xff0c;这道题写了一开始写了普通深搜&#xff0c;然后tle了一个点&#xff0c;后面改成剪枝&#xff0c;就ac了&#xff0c;虽然数据很水&#xff0c;但是不妨…...

C++通讯录管理系统

目录 系统需求 1、 创建项目 2、 菜单功能设计 3、 退出功能设计 4、 添加联系人功能设计 4.1 设计联系人结构体 4.2 设计通讯录结构体 4.3 在main函数中创建通讯录 4.4 封装添加联系人函数 4.5 添加联系人功能测试 5、 显示联系人功能设计 5.1 封装显示…...

Windows安装Python环境(V3.6)

文章目录 一&#xff1a;进入网址&#xff1a;https://www.python.org/downloads/ 二&#xff1a;执行安装包 默认C盘&#xff0c;选择自定义安装目录 记得勾选add python path 下面文件夹最好不要有 . 等特殊符号 可以创建 python36 如果安装失败Option可以选默认的&#x…...

python 如何调用GPT系列的api接口,实现想要的功能

目录 问题描述&#xff1a; 问题解决&#xff1a; 问题描述&#xff1a; 随着各种LLMs (Large Language Models&#xff09;的出现&#xff0c;如何调用各种LLMs的api成为了经常会遇见的问题。 问题解决&#xff1a; 下面仅以生成给定sentence的复述句为例&#xff0c;说明…...

JS动态参数arguments与剩余参数

arguments是函数内部内置的伪数组变量&#xff0c;它包含了调用函数时传入的所以实参 让我为大家介绍一下arguments吧 平时我们获取实参&#xff1a; function fun(a, b) {console.log(a) //1console.log(b) //2}fun(1, 2)接下来我们来使用一下arguments动态获取实参 function …...

使用ListenableFuture进行异步任务执行并进行线程切换

文章目录 一、前言二、关键代码三、参考链接 一、前言 在程序中会经常需要做一些异步任务&#xff0c;但是由于部分操作其实很简单&#xff0c;仅仅是短暂的进行异步操作&#xff0c;然后在结果成功或失败的时候切换回主线程进行下一步处理&#xff0c;这期间不能阻塞主线程。…...

C#,数值计算——插值和外推,RBF_fn 与 RBF_gauss 的计算方法与源程序

1 文本格式 using System; namespace Legalsoft.Truffer { public interface RBF_fn { double rbf(double r); } } ---------------------------------------------- using System; namespace Legalsoft.Truffer { public class RBF_gauss : RBF…...

Java8实战-总结49

Java8实战-总结49 CompletableFuture&#xff1a;组合式异步编程对多个异步任务进行流水线操作构造同步和异步操作将两个 CompletableFuture 对象整合起来&#xff0c;无论它们是否存在依赖 CompletableFuture&#xff1a;组合式异步编程 对多个异步任务进行流水线操作 构造同…...

云匣子 FastJson反序列化RCE漏洞复现

0x01 产品简介 云匣子是租户连接云资源的安全管理工具&#xff0c;帮助云租户更加安全、精细的管理云上的虚拟机、数据库等资源。 云安宝结合多年的运维和安全实践&#xff0c;将云上的运维和安全有机结合&#xff0c;实现对运维过程的事前规划、事中控制和 事后审计。在此之上…...

全程云OA SQL注入漏洞复现

0x01 产品简介 全程云OA为企业提供日常办公管理、公文管理、工作请示、汇报、档案、知识体系、预算控制等26个功能&#xff0c;超过100多个子模块。为企业内部提供高效、畅通的信息渠道&#xff0c;同时也能大力推动公司信息系统发展&#xff0c;提高企业的办公自动化程度和综合…...

IDEA DeBug

文章目录 01_Debug简介和意义02_IDEA中的Debug步骤03_跳转到当前代码执行的行04_步过调试的使用05_步入调试的使用06_强制步入调试的使用07_步出调试的使用08_回退断点调试的使用09_运行到光标处10_计算表达式11_条件断点12_多线程调试 01_Debug简介和意义 什么是程序DeBug&am…...

本地部署 ComfyUI

本地部署 ComfyUI ComfyUI 介绍ComfyUI Github 地址部署 ComfyUI配置模型地址 or 下载模型启动 ComfyUI访问 ComfyUI使用技巧页面底部显示图片预览改变连接线的格式配置 prompt 自动补全 安装 ComfyUI-Manager安装 AIGODLIKE-COMFYUI-TRANSLATION安装 ComfyUI-Custom-Scripts安…...

RHCE---给openlab搭建web网站

作业&#xff1a;请给openlab搭建web网站 网站需求&#xff1a; 1.基于域名 www.openlab.com 可以访问网站内容为 welcome to openlab!!! 2.给该公司创建三个子界面分别显示学生信息&#xff0c;教学资料和缴费网站&#xff0c; 1、基于 www.openlab.com/student 网站访问学生信…...

[BJDCTF2020]The mystery of ip1

提示 ssti模板注入head头x-forwarded-for 每一次做题的最开始流程都大致因该是 信息收集找可以操控的地方 查看hint页面的源代码又发现它提示说 ####你知道为什么会知道你的ip吗 查看flag页面 从刚才给我的提示以及他这里显示的我的ip&#xff0c;大概找到了我可操作的可控点 …...

常见树种(贵州省):021冬青、连香树、白辛树、香合欢、云贵鹅耳枥、肥牛树、杜英、格木、黄连木、圆果化香树、南天竹

摘要&#xff1a;本专栏树种介绍图片来源于PPBC中国植物图像库&#xff08;下附网址&#xff09;&#xff0c;本文整理仅做交流学习使用&#xff0c;同时便于查找&#xff0c;如有侵权请联系删除。 图片网址&#xff1a;PPBC中国植物图像库——最大的植物分类图片库 一、冬青 …...

[论文阅读]CBAM——代码实现和讲解

CBAM 论文网址&#xff1a;CBAM 论文代码&#xff1a;CBAM 本文提出了一种卷积块注意力模块&#xff08;CBAM&#xff09;&#xff0c;它是卷积神经网络&#xff08;CNN&#xff09;的一种轻量级、高效的注意力模块。该模块沿着通道和空间两个独立维度依次推导注意力图&#x…...

蓝桥杯第2119题 特殊时间 C++ 思维暴力

题目 思路和解题方法 1110 代表 1110年11月10号11点10分1110 4*4*4 有0111 1011 1101 1110 可以符合年 月日 时分秒的都有4种例如 1113有1113 1131 1311 3111 年份符合月日只有11 13 时分秒 只有11 13 11 31 13 11 无31 11 c 代码 #include <bits/stdc.h> using…...

Modbus RTU协议及modbus库函数使用

一、与Modbus TCP的区别 在一般工业场景使用modbus RTU的场景还是更多一些&#xff0c;modbus RTU基于串行协议进行收发数据&#xff0c;包括RS232/485等工业总线协议。 与modbus TCP不同的是RTU没有报文头MBAP字段&#xff0c;但是在尾部增加了两个CRC检验字节&#xff08;CRC…...

Linuxfork,写时拷贝

1.prinf隐藏的缓冲区 1.思考:为什么会有缓冲区的存在? 2.演示及思考? 1).演示缓存区没有存在感 那为什么我们感觉不到缓冲区的存在呢?我们要打印东西直接就打印了呢? 我们用代码演示一下: 比如打开一个main.c,输入内容如下: #include <stdio.h> int main() { …...

Android控件全解手册 - 自定义实现水波进度

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...