【蓝桥杯冲冲冲】[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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

解决Java中基于GeoTools的Shapefile读取乱码的问题

《解决Java中基于GeoTools的Shapefile读取乱码的问题》本文主要讨论了在使用Java编程语言进行地理信息数据解析时遇到的Shapefile属性信息乱码问题,以及根据不同的编码设置进行属... 目录前言1、Shapefile属性字段编码的情况:一、Shp文件常见的字符集编码1、System编码

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Java程序运行时出现乱码问题的排查与解决方法

《Java程序运行时出现乱码问题的排查与解决方法》本文主要介绍了Java程序运行时出现乱码问题的排查与解决方法,包括检查Java源文件编码、检查编译时的编码设置、检查运行时的编码设置、检查命令提示符的... 目录一、检查 Java 源文件编码二、检查编译时的编码设置三、检查运行时的编码设置四、检查命令提示符