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…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...