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

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&#xff0c;同时有 n 个物品&#xff0c;每个物品有一个体积。 现在从 n 个物品中&#xff0c;任取若干个装入箱内&#xff08;也可以不取&#xff09;&#xff0c;使箱子的剩余空间最小。输出这个最小值。 输入格式 第一行共一个整数 V&#…...

QCustomPlot获取选点坐标

QCustomPlot版本&#xff1a;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&#xff0c;NDK 具体参考该博客【原创】基于Qt5.14的一站式安卓开发环境搭建_qt安卓开发环境搭建_Jamie.T的博客-CSDN博客 3.后续可能会遇到的问题&#xff1a; ①SDK配置问题&#xff1a; 若出现以下编译错误&#xff0c;是build-tools 2…...

花费7元训练自己的GPT 2模型

在上一篇博客中&#xff0c;我介绍了用Tensorflow来重现GPT 1的模型和训练的过程。这次我打算用Pytorch来重现GPT 2的模型并从头进行训练。 GPT 2的模型相比GPT 1的改进并不多&#xff0c;主要在以下方面&#xff1a; 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、新建一个线程组&#xff0c;然后如下图所示添加 JDBC Connection Configuration 4、配置JDBC Connection Configurati…...

leetcode原题 路径总和 I II III(递归实现)

路径总和 I &#xff1a; 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 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、导入 例子完整的代码效果 总结 需求描述 在应用开发时&#xff0c;我们有很多场景要使用到更换图片的功能&#xff0c;即将原本的图像替换设置成其他的图像&#xff0c;从设备的相册或相机中选择图片或拍…...

数学建模体系

1评价类 主观求权重&#xff1a;层次分析法客观求权重&#xff1a;TOPSIS综合评价&#xff1a;典型相关分析 2预测插值算法拟合多元回归分析时间序列分析、ARCH和garch模型岭回归和lasso回归 3关系相关系数典型相关分析多元回归分析灰色关联分析 4图最短路径&#xff1a;迪杰斯…...

13.7 CentOS 7 环境下大量创建帐号的方法

13.7.1 一些帐号相关的检查工具 pwck pwck 这个指令在检查 /etc/passwd 这个帐号配置文件内的信息&#xff0c;与实际的主文件夹是否存在等信息&#xff0c; 还可以比对 /etc/passwd /etc/shadow 的信息是否一致&#xff0c;另外&#xff0c;如果 /etc/passwd 内的数据字段错…...

HTML5 Canvas(画布)

<canvas>标签定义图形&#xff0c;比如图表和其他图像&#xff0c;你必须用脚本来绘制图形。 在画布上&#xff08; Canvas &#xff09;画一个共红色矩形&#xff0c;渐变矩形&#xff0c;彩色矩形&#xff0c;和一些彩色文字。 什么是 Canvas&#xff1f; 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镜像 构建镜像 概述&#xff1a; Docker 镜像是Docker容器技术中的核心&#xff0c;也是应用打包构建发布的标准格式。…...

JS中常见的模块管理规范梳理

一、CommonJS规范 CommonJS规范是一种用于JavaScript模块化开发的规范&#xff0c;它定义了模块的导入、导出方式和加载机制&#xff0c;主要用在Node开发中。 1. 使用场景 服务器端开发&#xff1a;Node.js是使用CommonJS规范的&#xff0c;因此在服务器端开发中&#xff0…...

3维空间下按平面和圆柱面上排版设计

AR空间中将若干平面窗口排列在指定平面或圆柱体面上 平面排版思路 指定平面方向向量layout_centre ,平面上的一点作为排版版面的中心layout_position float3 layout_position = float3(0,0,-10); float3 layout_centre = float3(0,0,1...

【Spring框架】Spring AOP

目录 什么是AOP&#xff1f;AOP组成Spring AOP 实现步骤Spring AOP实现原理JDK Proxy VS CGLIB 什么是AOP&#xff1f; AOP&#xff08;Aspect Oriented Programming&#xff09;&#xff1a;⾯向切⾯编程&#xff0c;它是⼀种思想&#xff0c;它是对某⼀类事情的集中处理。⽐如…...

寻找旋转排序数组中的最小值——力扣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数据时&#xff0c;有些字段是加密的&#xff0c;如某麦网x-mini-wua x-sgext x-sign x-umt x-utdid等参数&#xff0c;这时候我们需要去分析加密字段的生成。本篇将以采集的角度讲解入门安卓逆向需要掌握的技能、工具。 2、安卓&#xff08;Androi…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; 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 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Debian系统简介

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

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...