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…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
