洛谷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装箱问题 ————递归+剪枝+回溯
没没没没没没没没没错,又是一道简单的递归,只不过加了剪枝,我已经不想再多说,这道题写了一开始写了普通深搜,然后tle了一个点,后面改成剪枝,就ac了,虽然数据很水,但是不妨…...
C++通讯录管理系统
目录 系统需求 1、 创建项目 2、 菜单功能设计 3、 退出功能设计 4、 添加联系人功能设计 4.1 设计联系人结构体 4.2 设计通讯录结构体 4.3 在main函数中创建通讯录 4.4 封装添加联系人函数 4.5 添加联系人功能测试 5、 显示联系人功能设计 5.1 封装显示…...
Windows安装Python环境(V3.6)
文章目录 一:进入网址:https://www.python.org/downloads/ 二:执行安装包 默认C盘,选择自定义安装目录 记得勾选add python path 下面文件夹最好不要有 . 等特殊符号 可以创建 python36 如果安装失败Option可以选默认的&#x…...
python 如何调用GPT系列的api接口,实现想要的功能
目录 问题描述: 问题解决: 问题描述: 随着各种LLMs (Large Language Models)的出现,如何调用各种LLMs的api成为了经常会遇见的问题。 问题解决: 下面仅以生成给定sentence的复述句为例,说明…...
JS动态参数arguments与剩余参数
arguments是函数内部内置的伪数组变量,它包含了调用函数时传入的所以实参 让我为大家介绍一下arguments吧 平时我们获取实参: function fun(a, b) {console.log(a) //1console.log(b) //2}fun(1, 2)接下来我们来使用一下arguments动态获取实参 function …...
使用ListenableFuture进行异步任务执行并进行线程切换
文章目录 一、前言二、关键代码三、参考链接 一、前言 在程序中会经常需要做一些异步任务,但是由于部分操作其实很简单,仅仅是短暂的进行异步操作,然后在结果成功或失败的时候切换回主线程进行下一步处理,这期间不能阻塞主线程。…...
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:组合式异步编程对多个异步任务进行流水线操作构造同步和异步操作将两个 CompletableFuture 对象整合起来,无论它们是否存在依赖 CompletableFuture:组合式异步编程 对多个异步任务进行流水线操作 构造同…...
云匣子 FastJson反序列化RCE漏洞复现
0x01 产品简介 云匣子是租户连接云资源的安全管理工具,帮助云租户更加安全、精细的管理云上的虚拟机、数据库等资源。 云安宝结合多年的运维和安全实践,将云上的运维和安全有机结合,实现对运维过程的事前规划、事中控制和 事后审计。在此之上…...
全程云OA SQL注入漏洞复现
0x01 产品简介 全程云OA为企业提供日常办公管理、公文管理、工作请示、汇报、档案、知识体系、预算控制等26个功能,超过100多个子模块。为企业内部提供高效、畅通的信息渠道,同时也能大力推动公司信息系统发展,提高企业的办公自动化程度和综合…...
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网站
作业:请给openlab搭建web网站 网站需求: 1.基于域名 www.openlab.com 可以访问网站内容为 welcome to openlab!!! 2.给该公司创建三个子界面分别显示学生信息,教学资料和缴费网站, 1、基于 www.openlab.com/student 网站访问学生信…...
[BJDCTF2020]The mystery of ip1
提示 ssti模板注入head头x-forwarded-for 每一次做题的最开始流程都大致因该是 信息收集找可以操控的地方 查看hint页面的源代码又发现它提示说 ####你知道为什么会知道你的ip吗 查看flag页面 从刚才给我的提示以及他这里显示的我的ip,大概找到了我可操作的可控点 …...
常见树种(贵州省):021冬青、连香树、白辛树、香合欢、云贵鹅耳枥、肥牛树、杜英、格木、黄连木、圆果化香树、南天竹
摘要:本专栏树种介绍图片来源于PPBC中国植物图像库(下附网址),本文整理仅做交流学习使用,同时便于查找,如有侵权请联系删除。 图片网址:PPBC中国植物图像库——最大的植物分类图片库 一、冬青 …...
[论文阅读]CBAM——代码实现和讲解
CBAM 论文网址:CBAM 论文代码:CBAM 本文提出了一种卷积块注意力模块(CBAM),它是卷积神经网络(CNN)的一种轻量级、高效的注意力模块。该模块沿着通道和空间两个独立维度依次推导注意力图&#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的场景还是更多一些,modbus RTU基于串行协议进行收发数据,包括RS232/485等工业总线协议。 与modbus TCP不同的是RTU没有报文头MBAP字段,但是在尾部增加了两个CRC检验字节(CRC…...
Linuxfork,写时拷贝
1.prinf隐藏的缓冲区 1.思考:为什么会有缓冲区的存在? 2.演示及思考? 1).演示缓存区没有存在感 那为什么我们感觉不到缓冲区的存在呢?我们要打印东西直接就打印了呢? 我们用代码演示一下: 比如打开一个main.c,输入内容如下: #include <stdio.h> int main() { …...
Android控件全解手册 - 自定义实现水波进度
Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换
目录 关键点 技术实现1 技术实现2 摘要: 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式(自动驾驶、人工驾驶、远程驾驶、主动安全),并通过实时消息推送更新车…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
