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

【NOIP普及组】 装箱问题

【NOIP普及组】 装箱问题


💐The Begin💐点点关注,收藏不迷路💐

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30=,每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入

第一行,一个整数,表示箱子容量;
第二行,一个整数,表示有n个物品;
接下来n行,分别表示这n个物品的各自体积。

输出

一个整数,表示箱子剩余空间。

样例输入

24
6
8
3
12
7
9
7

样例输出

0 

C语言实现的代码:

#include <stdio.h>// 递归函数用于计算最小剩余空间
int pack(int capacity, int* items, int index, int n) {// 如果箱子容量为 0 或者已经考虑完所有物品,返回箱子容量if (capacity == 0 || index == n) return capacity;// 如果当前物品体积大于箱子容量,直接考虑下一个物品if (items[index] > capacity) return pack(capacity, items, index + 1, n);// 尝试放入当前物品和不放入当前物品,取剩余空间较小的情况return (capacity - items[index] >= 0)? (int)fmin(pack(capacity - items[index], items, index + 1, n), pack(capacity, items, index + 1, n)) : pack(capacity, items, index + 1, n);
}int main() {int capacity;scanf("%d", &capacity); // 输入箱子容量int n;scanf("%d", &n); // 输入物品数量int items[n];for (int i = 0; i < n; ++i) {scanf("%d", &items[i]); // 输入每个物品的体积}int result = pack(capacity, items, 0, n); // 调用函数计算最小剩余空间printf("%d\n", result); // 输出箱子剩余空间return 0;
}

在这里插入图片描述

C++实现的代码:

#include <iostream>
#include <vector>// 递归函数用于计算最小剩余空间
int pack(int capacity, const std::vector<int>& items, int index) {// 如果箱子容量为 0 或者已经考虑完所有物品,返回箱子容量if (capacity == 0 || index == items.size()) return capacity;// 如果当前物品体积大于箱子容量,直接考虑下一个物品if (items[index] > capacity) return pack(capacity, items, index + 1);// 尝试放入当前物品和不放入当前物品,取剩余空间较小的情况return std::min(pack(capacity - items[index], items, index + 1), pack(capacity, items, index + 1));
}int main() {int capacity;std::cin >> capacity; // 输入箱子容量int n;std::cin >> n; // 输入物品数量std::vector<int> items(n);for (int i = 0; i < n; ++i) {std::cin >> items[i]; // 输入每个物品的体积}int result = pack(capacity, items, 0); // 调用函数计算最小剩余空间std::cout << result << std::endl; // 输出箱子剩余空间return 0;
}

Python 实现的代码:

def pack(capacity, items, index):# 如果箱子容量为 0 或者已经考虑完所有物品,返回箱子容量if capacity == 0 or index == len(items):return capacity# 如果当前物品体积大于箱子容量,直接考虑下一个物品if items[index] > capacity:return pack(capacity, items, index + 1)# 尝试放入当前物品和不放入当前物品,取剩余空间较小的情况return min(pack(capacity - items[index], items, index + 1), pack(capacity, items, index + 1))capacity = int(input()) # 输入箱子容量
n = int(input()) # 输入物品数量
items = []
for _ in range(n):items.append(int(input())) # 输入每个物品的体积
result = pack(capacity, items, 0) # 调用函数计算最小剩余空间
print(result) # 输出箱子剩余空间

Java 实现的代码:

import java.util.Scanner;class Main{// 递归方法计算最小剩余空间public static int pack(int capacity, int[] items, int index) {// 如果箱子容量为 0 或者已经考虑完所有物品,返回箱子容量if (capacity == 0 || index == items.length) return capacity;// 如果当前物品体积大于箱子容量,直接考虑下一个物品if (items[index] > capacity) return pack(capacity, items, index + 1);// 尝试放入当前物品和不放入当前物品,取剩余空间较小的情况return Math.min(pack(capacity - items[index], items, index + 1), pack(capacity, items, index + 1));}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int capacity = scanner.nextInt(); // 输入箱子容量int n = scanner.nextInt(); // 输入物品数量int[] items = new int[n];for (int i = 0; i < n; i++) {items[i] = scanner.nextInt(); // 输入每个物品的体积}int result = pack(capacity, items, 0); // 调用函数计算最小剩余空间System.out.println(result); // 输出箱子剩余空间}
}

在这里插入图片描述


💐The End💐点点关注,收藏不迷路💐

相关文章:

【NOIP普及组】 装箱问题

【NOIP普及组】 装箱问题 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 有一个箱子容量为V&#xff08;正整数&#xff0c;0&#xff1c;&#xff1d;V&#xff1c;&#xff1d;20000&#xff09;&#xff0c;同时有n个物品&#xff08;0&…...

Flutter主题最佳实践

Styling your Flutter app not only makes it visually appealing but also enhances the user experience. Flutter offers a robust theming system that helps you maintain consistency and customize your app’s look and feel. 设计 Flutter 应用程序的风格不仅能使其在…...

计算机网络:网络层 —— IPv4 数据报的首部格式

文章目录 IPv4数据报的首部格式IPv4数据报分片生存时间 TTL字段协议字段首部检验和字段 IPv4数据报的首部格式 IPv4 数据报的首部格式及其内容是实现 IPv4 协议各种功能的基础。 在 TCP/IP 标准中&#xff0c;各种数据格式常常以32比特(即4字节)为单位来描述 固定部分&#x…...

MySQL 之 索引

索引 概述 是帮助MySQL高效获取数据的数据结构&#xff0c;在数据之外&#xff0c;数据库系统还维护着满足特定查找算法的数据结构&#xff0c;这些数据结构以某种方式引用&#xff08;指向&#xff09;数据&#xff0c;这样就可以在数据结构上实现高效查找算法&#xff0c;这种…...

手动探针台的用途及组成部分

探针台系统分为手动探针台与自动探针台&#xff0c;以下我们主要分析手动探针台。 探针台用途&#xff1a; 手动探针台又称探针测试台主要用途是为半导体芯片的电参数测试提供一个测试平台&#xff0c;探针台可吸附多种规格芯片&#xff0c;并提供多个可调测试针以及探针座&am…...

❤️算法笔记❤️-(每日一刷-5、最长回文串)

文章目录 题目思路解答 题目 给你一个字符串 s&#xff0c;找到 s 中最长的 回文 子串。 示例 1&#xff1a; 输入&#xff1a;s "babad" 输出&#xff1a;"bab" 解释&#xff1a;"aba" 同样是符合题意的答案。示例 2&#xff1a; 输入&#xf…...

nginx 路径匹配,关于“/“对规则的影响

1、基本规则 假如后端实际地址为&#xff1a; http://127.0.0.1:8080/api/user/getById?id123 则&#xff1a; 1&#xff09;通过nginx转发&#xff0c;使用http://127.0.0.1/api/user/getById?id123访问 server {listen 80;server_name 127.0.0.1;location /api…...

安全知识见闻-网络安全热门证书

一、OSCP(Offensive Security Certified Professional) 1. 证书介绍 2.考点 3.部分考试要求 4.练习方法 二、OSEP(Offensive Security Exploit Developer) 1.证书介绍 2.考点 3.练习方法 三、CISSP&#xff08;Certified lnformation Systems Security Professional&a…...

Pandabuy事件警示:反向海淘品牌如何规避风险

Pandabuy&#xff0c;作为一个曾经备受海外消费者青睐的跨境电商平台&#xff0c;以其丰富的商品种类、优质的服务和便捷的购物流程迅速崛起。然而&#xff0c;近期的一系列丑闻&#xff0c;尤其是涉嫌销售大量仿制名牌运动鞋的事件&#xff0c;让Pandabuy陷入了前所未有的信任…...

【纯血鸿蒙】安装hdc工具

这里我先写Mac版的,Windows的在下面 首先要知道你的SDK安装在哪里了,不知道的话,可以打开DevEco Studio,打开设置页面里的HarmonyOS SDK,这个我们之前配置环境变量的时候用过。 其实主要是用到这里toolchains下的hdc命令。 所以我们需要配置环境变量。 1、打开Mac下的…...

TensorFlow面试整理-给定一个任务(如图像分类、文本分类),如何从头构建一个TensorFlow模型?

构建一个 TensorFlow 模型来执行图像分类或文本分类任务的步骤基本类似,虽然数据类型不同,但核心流程相同。以下将以 图像分类任务 和 文本分类任务 为例,展示如何从头构建 TensorFlow 模型,覆盖数据预处理、模型构建、编译、训练和评估的完整流程。 一、图像分类任务:从头…...

unity中出现一些莫名其妙的问题

问题现象&#xff1a;一个功能昨天测试还正常的今天突然不能用了&#xff0c;而且关于这个功能的代码都没调整过。 原因&#xff1a;相关逻辑上存在异常代码&#xff0c;可能是别人提交的代码运行中有异常未处理导致 处理办法&#xff1a;解决异常 查找哪些位置使用了该异常脚本…...

Python爬虫-汽车投诉排行榜单数据

前言 本文是该专栏的第40篇,后面会持续分享python爬虫干货知识,记得关注。 本文以某汽车平台为例,通过python采集其“汽车投诉排行”榜单数据。具体的实现思路以及完整实现代码逻辑,笔者将在正文为你详细介绍。废话不多说,跟着笔者直接往下看正文详细内容。(附带完整代码…...

[C++][数据结构][哈希表]详细讲解

目录 1. 哈希概念 2.哈希冲突 3.哈希函数 4.哈希冲突解决 4.1闭散列 4.1.1何时扩容&#xff1f;如何扩容&#xff1f; 4.1.2线性探测 4.1.3二次探测 4.2开散列(哈希桶) 4.2.1概念 4.2.2开散列增容 1. 哈希概念 顺序结构以及平衡树中&#xff0c;元素关键码与其存储…...

Android Gradle

#1024程序员节&#xff5c;征文# Gradle 是一款强大的自动化构建工具&#xff0c;广泛应用于 Android 应用开发。它通过灵活的配置和丰富的插件系统&#xff0c;为项目构建提供了极大的便利。本文只是简单的介绍 Gradle 在 Android 开发中的使用&#xff0c;包括其核心概念、构…...

Vue2自定义指令及插槽

这里写目录标题 自定义指令基础语法指令的值封装v-loading指令 插槽默认插槽后备内容&#xff08;插槽的默认值&#xff09;具名插槽作用域插槽 自定义指令 自定义指令&#xff1a;自己定义的指令&#xff0c;封装一些dom操作&#xff0c;扩展额外功能 基础语法 全局注册&am…...

【Qt】系统相关——多线程、Qt多线程介绍、常用函数、线程安全、网络、UDP Socket、TCP Socket

文章目录 Qt系统相关1. 多线程1.1 Qt多线程介绍1.2 常用函数1.3 线程安全 2. 网络2.1 UDP Socket2.2 TCP Socket Qt 系统相关 1. 多线程 1.1 Qt多线程介绍 QThread 代表一个在应用程序中可以独立控制的线程&#xff0c;它还可以和进程中的其他线程共享数据。QThread 对象管理…...

1GS/s 4通道14bit PCIE采集卡

1GS/s 4通道14bit PCIE采集卡是一款同时具备直流耦合程控放大器和双极性宽带信号输入的高速数据采集卡。板载FPGA具备实时信号处理能力&#xff0c;这些特性使其成为激光雷达、光纤传感、粒子物理等应用领域进行信号采集和分析的理想工具。提供快速的PCI Express 3.0 x8数据传输…...

动态IP是什么?

随着互联网成为人们生活的重要组成部分&#xff0c;以信息传递为主导的时代种&#xff0c;网络连接质量对我们的工作效率、学习进度以及娱乐体验等方面都有很大影响。 动态IP&#xff0c;作为网络连接中的一种重要IP代理形式&#xff0c;越来越受到用户的欢迎。本文将深入解析…...

51单片机完全学习——红外遥控

一、红外接收模块原理 红外接收头内部本身有一个反相&#xff0c;意思就是&#xff1a;平时发送方无信号时接收到的是1&#xff0c;发送方有发送载波时接收头引脚输出的是0&#xff0c;写代码的时候注意这一点。红外协议&#xff0c;你也可以理解成&#xff0c;他对0和1重新做…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

[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…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...