【蓝桥杯冲冲冲】[NOIP2001 普及组] 装箱问题

2024-02-04 06:04

本文主要是介绍【蓝桥杯冲冲冲】[NOIP2001 普及组] 装箱问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

蓝桥杯备赛 | 洛谷做题打卡day26

文章目录

  • 蓝桥杯备赛 | 洛谷做题打卡day26
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
      • 思路
    • 题解代码
    • 我的一些话

  • [NOIP2001 普及组] 装箱问题

    题目描述

    有一个箱子容量为 V V V,同时有 n n n 个物品,每个物品有一个体积。

    现在从 n n n 个物品中,任取若干个装入箱内(也可以不取),使箱子的剩余空间最小。输出这个最小值。

    输入格式

    第一行共一个整数 V V V,表示箱子容量。

    第二行共一个整数 n n n,表示物品总数。

    接下来 n n n 行,每行有一个正整数,表示第 i i i 个物品的体积。

    输出格式

    • 共一行一个整数,表示箱子最小剩余空间。

    样例 #1

    样例输入 #1

    24
    6
    8
    3
    12
    7
    9
    7
    

    样例输出 #1

    0
    

    提示

    对于 100 % 100\% 100% 数据,满足 0 < n ≤ 30 0<n \le 30 0<n30 1 ≤ V ≤ 20000 1 \le V \le 20000 1V20000

    【题目来源】

    NOIP 2001 普及组第四题

在这里插入图片描述

思路

这道题看似是搜索,但是可以用背包做。

题目要求求出最小的剩余空间,也就是要求出最大的可装重量

这样,我们可以将一个物体的重量当作它的价值,进而将题目转变为一个基本的01背包问题:

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)和一个价值(等于体积)。

要求n个物品中,任取若干个装入箱内,使总价值最大。

对于每一个物体,都有两种状态:装 与不装

那么,对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )(w为重量(即价值))

其中,f ( m - w[i] ) 指在装了物品i后,箱子的剩余容量能装的最大重量

f ( m - w[i] ) + w[i] 指在在装了物品i后,箱子能装的最大重量

题解代码

学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是题解代码 ~

#include<cstdio>
using namespace std;
int m,n;                m即箱子容量V
int f[20010];
int w[40];
int main(){int i,j;scanf("%d%d",&m,&n);for(i=1;i<=n;i++){scanf("%d",&w[i]);}for(i=1;i<=n;i++){for(j=m;j>=w[i];j--){                            注意:这里必须是从m到w[i],否则一个物体会被多次装入箱子,见例1if(f[j]<f[j-w[i]]+w[i]){f[j]=f[j-w[i]]+w[i];}}}printf("%d\n",m-f[m]);
}

我的一些话

  • 今天学习动态规划,dp属于比较难的部分,需要多动脑,多思考思路还是很好掌握的,虽然一次性AC有一定难度,需要通盘的考虑和理解,以及扎实的数据结构基础才能独立写出AC代码。但无论难易,大家都要持续做题,保持题感喔!一起坚持(o´ω`o)

  • 如果有非计算机专业的uu自学的话,关于数据结构的网课推荐看b站上青岛大学王卓老师的课,讲的很细致,有不懂都可以私信我喔

  • 总结来说思路很重要,多想想,多在草稿纸上画画,用测试数据多调试,debug后成功编译并运行出正确结果真的会感到很幸福!

  • 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识,之前的博文我都有写,欢迎大家关注我,翻阅自取哦~

  • 不管什么都要坚持吧,三天打鱼两天晒网无法形成肌肉记忆和做题思维,该思考的时候一定不要懈怠,今天就说这么多啦,欢迎评论留言,一起成长:)

这篇关于【蓝桥杯冲冲冲】[NOIP2001 普及组] 装箱问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/676529

相关文章

Redis 热 key 和大 key 问题小结

《Redis热key和大key问题小结》:本文主要介绍Redis热key和大key问题小结,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、什么是 Redis 热 key?热 key(Hot Key)定义: 热 key 常见表现:热 key 的风险:二、

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》:本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用?循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t