P1049 [NOIP2001 普及组] 装箱问题
题目描述
有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积。
现在从 n 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。
输入格式
第一行共一个整数 V,表示箱子容量。
第二行共一个整数 n,表示物品总数。
接下来 n 行,每行有一个正整数,表示第 i 个物品的体积。
输出格式
共一行一个整数,表示箱子最小剩余空间。
输入输出样例
输入
24 6 8 3 12 7 9 7
输出
0
说明/提示
对于 100%数据,满足 0<n≤30,1≤V≤20000。
一,代码实现(搜索)
#include<iostream>
using namespace std;
int n,m,ans;
int a[35];void dfs(int u,int mid){if(mid>ans)ans=mid; //更新结果for(int j=u+1;j<=n;j++){if(mid+a[j]<=m)dfs(j,mid+a[j]); //可以装的话递归到下一层继续装}
}int main(){cin>>m>>n;for(int i=1;i<=n;i++)cin>>a[i];dfs(0,0);cout<<m-ans<<endl;return 0;
}
二,代码实现(二维dp)
#include<iostream>
using namespace std;
const int N=35;
int v[N],h[N];
int f[N][20010];int main(){int n,m;cin>>m>>n;for(int i=1;i<=n;i++)cin>>v[i];for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+v[i]);}} cout<<m-f[n][m]<<endl;return 0;
}
三,代码实现(一维dp)
#include<iostream>
using namespace std;
const int N=35;
int v[N],h[N];
int f[20010];int main(){int n,m;cin>>m>>n;for(int i=1;i<=n;i++)cin>>v[i];for(int i=1;i<=n;i++){for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+v[i]);} cout<<m-f[m]<<endl;return 0;
}
相关文章:
P1049 [NOIP2001 普及组] 装箱问题
题目描述 有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积。 现在从 n 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。 输入格式 第一行共一个整数 V&#…...
QCustomPlot获取选点坐标
QCustomPlot版本:Version: 2.1.1 设置点选择模式 customPlot->setInteractions(QCP::iSelectPlottables);2.绑定点击事件 connect(customPlot, &QCustomPlot::plottableClick, this, &CCustomPlot::onPlotClick);3.读取点位置 void CustomPlot::onP…...
Qt配置Android开发
1.使用Qt5.14.2 2.安装java和SDK,NDK 具体参考该博客【原创】基于Qt5.14的一站式安卓开发环境搭建_qt安卓开发环境搭建_Jamie.T的博客-CSDN博客 3.后续可能会遇到的问题: ①SDK配置问题: 若出现以下编译错误,是build-tools 2…...

花费7元训练自己的GPT 2模型
在上一篇博客中,我介绍了用Tensorflow来重现GPT 1的模型和训练的过程。这次我打算用Pytorch来重现GPT 2的模型并从头进行训练。 GPT 2的模型相比GPT 1的改进并不多,主要在以下方面: 1. GPT 2把layer normalization放在每个decoder block的前…...
性能分析工具
性能分析工具 valgrind 交叉编译 android arm/arm64 平台 valgrind android32 #!/usr/bin/env bashexport NDKROOT~/opt/android-ndk-r14b/ export AR$NDKROOT/toolchains/arm-linux-androideabi-4.9/prebuilt/linux-x86_64/bin/arm-linux-androideabi-ar export LD$NDKROO…...

1.netty介绍
1.介绍 是JBOSS通过的java开源框架是异步的,基于事件驱动(点击一个按钮调用某个函数)的网络应用框架,高性能高可靠的网络IO程序基于TCP,面向客户端高并发应用/点对点大量数据持续传输的应用是NIO框架 (IO的一层层封装) TCP/IP->javaIO和网络编程–>NIO—>Netty 2.应用…...

【Jmeter】压测mysql数据库中间件mycat
目录 背景 环境准备 1、下载Jmeter 2、下载mysql数据库的驱动包 3、要进行测试的数据库 Jmeter配置 1、启动Jmeter图形界面 2、加载mysql驱动包 3、新建一个线程组,然后如下图所示添加 JDBC Connection Configuration 4、配置JDBC Connection Configurati…...

leetcode原题 路径总和 I II III(递归实现)
路径总和 I : 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径,这条路径上所有节点值相加等于目标和 targetSum 。如果存在,返回 true ;否则,返回 false 。…...

【css】css设置表格样式-边框线合并
<style> table, td, th {border: 1px solid black;//设置边框线 }table {width: 100%; }td {text-align: center;//设置文本居中 } </style> </head> <body><table><tr><th>Firstname</th><th>Lastname</th><t…...

使用Flutter的image_picker插件实现设备的相册的访问和拍照
文章目录 需求描述Flutter插件image_picker的介绍使用步骤1、添加依赖2、导入 例子完整的代码效果 总结 需求描述 在应用开发时,我们有很多场景要使用到更换图片的功能,即将原本的图像替换设置成其他的图像,从设备的相册或相机中选择图片或拍…...
数学建模体系
1评价类 主观求权重:层次分析法客观求权重:TOPSIS综合评价:典型相关分析 2预测插值算法拟合多元回归分析时间序列分析、ARCH和garch模型岭回归和lasso回归 3关系相关系数典型相关分析多元回归分析灰色关联分析 4图最短路径:迪杰斯…...

13.7 CentOS 7 环境下大量创建帐号的方法
13.7.1 一些帐号相关的检查工具 pwck pwck 这个指令在检查 /etc/passwd 这个帐号配置文件内的信息,与实际的主文件夹是否存在等信息, 还可以比对 /etc/passwd /etc/shadow 的信息是否一致,另外,如果 /etc/passwd 内的数据字段错…...

HTML5 Canvas(画布)
<canvas>标签定义图形,比如图表和其他图像,你必须用脚本来绘制图形。 在画布上( Canvas )画一个共红色矩形,渐变矩形,彩色矩形,和一些彩色文字。 什么是 Canvas? HTML5<c…...
io的异常处理以及properties
try(流对象的创建) { 对象的处理逻辑} catch(IOException e) { 异常的处理逻辑} public static void test4(){try(FileWriter fwnew FileWriter("a.txt",true); ){char[] cbuf{a};//写入一个字符串组fw.write(cbuf);}catch(IOException e){e.printStackTrace();}}上面…...

Linux下基于Dockerfile构建镜像应用(1)
目录 基于已有容器创建镜像 Dockerfile构建SSHD镜像 构建镜像 测试容器 可以登陆 Dockerfile构建httpd镜像 构建镜像 测试容器 Dockerfile构建nginx镜像 构建镜像 概述: Docker 镜像是Docker容器技术中的核心,也是应用打包构建发布的标准格式。…...
JS中常见的模块管理规范梳理
一、CommonJS规范 CommonJS规范是一种用于JavaScript模块化开发的规范,它定义了模块的导入、导出方式和加载机制,主要用在Node开发中。 1. 使用场景 服务器端开发:Node.js是使用CommonJS规范的,因此在服务器端开发中࿰…...
3维空间下按平面和圆柱面上排版设计
AR空间中将若干平面窗口排列在指定平面或圆柱体面上 平面排版思路 指定平面方向向量layout_centre ,平面上的一点作为排版版面的中心layout_position float3 layout_position = float3(0,0,-10); float3 layout_centre = float3(0,0,1...

【Spring框架】Spring AOP
目录 什么是AOP?AOP组成Spring AOP 实现步骤Spring AOP实现原理JDK Proxy VS CGLIB 什么是AOP? AOP(Aspect Oriented Programming):⾯向切⾯编程,它是⼀种思想,它是对某⼀类事情的集中处理。⽐如…...

寻找旋转排序数组中的最小值——力扣153
文章目录 题目描述解法 二分法 题目描述 解法 二分法 int findMin(vector<int>& nums){int l0, rnums.size()-1;while(l<r){int mid (lr)/2;if(nums[mid]<nums[r]) rmid;else lmid1;}return nums[l];}...

安卓逆向 - 基础入门教程
一、引言 1、我们在采集app数据时,有些字段是加密的,如某麦网x-mini-wua x-sgext x-sign x-umt x-utdid等参数,这时候我们需要去分析加密字段的生成。本篇将以采集的角度讲解入门安卓逆向需要掌握的技能、工具。 2、安卓(Androi…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...

【Linux】自动化构建-Make/Makefile
前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具:make/makfile 1.背景 在一个工程中源文件不计其数,其按类型、功能、模块分别放在若干个目录中,mak…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

C# winform教程(二)----checkbox
一、作用 提供一个用户选择或者不选的状态,这是一个可以多选的控件。 二、属性 其实功能大差不差,除了特殊的几个外,与button基本相同,所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...
13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析
LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...