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

【华为OD题库-007】代表团坐车-Java

题目

某组织举行会议,来了多个代表团同时到达,接待处只有一辆汽车,可以同时接待多个代表团,为了提高车辆利用率,请帮接待员计算可以坐满车的接待方案,输出方案数量。
约束:
1.一个团只能上一辆车,并且代表团人数(代表团数量小于30,每个代表团人数小于30)小于汽车容量(汽车容量小于100)
⒉.需要将车辆坐满
输入描述
第一行 :代表团人数,英文逗号隔开,代表团数量小于30,每个代表团人数小于30
第二行:汽车载客量,汽车容量小于100
输出描述
坐满汽车的方案数量
如果无解输出0
示例1:
输入
5,4,2,3,2,4,9
10
输出
4
说明
以下几种方式都可以坐满车,[2,3,5]、[2,4,4]、[2,3,5]、[2,4,4]

思路

题目翻译过来就是,在给定数组中找若干数,让他们的和等于目标值,问有多少种找法?
以示例数据为例:
输入:
5,4,2,3,2,4,9
10
记代表团人数为数组arr,长度为len,汽车载客量为total。
先将arr从小到大排序(不排序也是一样的):2 2 3 4 4 5 9
定义二维数组dp[][],dp[i][j]代表从arr的前i个数中选,使选择数的和等于j的方案数,比如:

dp[0][0],代表从arr选取0个元素,让他们的和等于0有几种选法?很明显,啥都不选,和就是0,所以有1种选法,即dp[0][0]=1
dp[0][1],代表从arr选取0个元素,让他们的和等于1有几种选法?很明显,选取0个元素,要使和为1,不可能,因此dp[0][1]=0
dp[1][0],代表从arr最多选取1个元素,使他们的和等于0有几种选法?选0个元素,和等于0为选法1;选择1个元素,只能选2,大于目标0,因此不能选。所以总的选法还是为1,即dp[1][0]=1。
dp[len][total], 代表从arr最多选取len个元素(也就是从arr整个数组中选),使他们的和等于total有几种选法?也就是题目所求的答案

让我们总结一般规律,对于dp[i][j]。
记录当前值cur,i为从arr选取i个元素,选取1个元素的时候为arr[0],选取i个元素的时候,应该为arr[i-1]。
如果cur>j,也就是如果选了当前元素,那么其和势必大于j(arr中全为正数),不满足,所以此时不能选当前元素,dp[i][j]=dp[i-1][j]
如果cur<=j,不选当前元素的方案数为dp[i-1][j],选了当前元素的方案数为:dp[i-1][j-cur],所以此分支总的方案数为:dp[i][j]=dp[i-1][j]+dp[i-1][j-cur]
现在有了dp的初始值和递推关系,我们可以使用动态规划求出此问题的解。

题解

package hwod;import java.util.Arrays;
import java.util.Scanner;public class TakeCar {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] inputs = sc.nextLine().split(",");int[] nums = Arrays.stream(inputs).mapToInt(Integer::parseInt).toArray();int target = sc.nextInt();System.out.println(getPlanCnt(nums, target));}private static int getPlanCnt(int[] nums, int target) {int n = nums.length;int[][] dp = new int[n + 1][target + 1];dp[0][0] = 1;for (int i = 1; i < n + 1; i++) {//dp[0][x],x大于0时,其值明显为0,int数组的默认值刚好为0,所以不用更新int cur = nums[i - 1];for (int j = 0; j < target+1; j++) {dp[i][j] = dp[i - 1][j];if(cur<=j) dp[i][j] += dp[i - 1][j - cur];}}return dp[n][target];}
}

说明

排序和不排序时,dp变化结果分别如下,可以看到最后还是得到相同的结果:4
排序:
在这里插入图片描述

不排序:
在这里插入图片描述
说明:标黄的,横向代表j,从0到10,纵向代表arr中第i个的值(从0开始,第0个代表不取arr的元素,为0)

推荐

如果你对本系列的其他题目感兴趣,可以参考华为OD机试真题及题解(JAVA),查看当前专栏更新的所有题目。

相关文章:

【华为OD题库-007】代表团坐车-Java

题目 某组织举行会议&#xff0c;来了多个代表团同时到达&#xff0c;接待处只有一辆汽车&#xff0c;可以同时接待多个代表团&#xff0c;为了提高车辆利用率&#xff0c;请帮接待员计算可以坐满车的接待方案&#xff0c;输出方案数量。 约束: 1.一个团只能上一辆车&#xff0…...

利用servlet实现对书籍书名、单价、数量等信息的添加,计算总价

1.题目要求 利用servlet实现对书籍书名、单价、数量等信息的添加&#xff0c;计算总价。 要求&#xff1a;输入两次表单信息&#xff0c;在一个成功返回的页面里面显示两次的数据。 2.Book实体类 package com.hjj.sevletgk.hw7.book;/*** author:嘉佳 Date:2023/10/8 15:16*…...

一键批量转码:将MP4视频转为MP3音频的简单方法

随着数字媒体设备的普及&#xff0c;视频和音频格式转换的需求也越来越常见。其中&#xff0c;将MP4视频批量转换为MP3音频的需求尤为普遍。无论是为了提取视频中的背景音乐&#xff0c;还是为了在手机或电脑上方便地收听视频音频&#xff0c;这个过程都变得非常重要。接下来我…...

java入门,记一次微服务间feigin请求的问题

一、前言 记录工作中遇到的开发问题&#xff0c;而不是写博客凑字数。 二、微服务调用 1、通过本服务调用另外一个服务&#xff0c;需要定义一个接口&#xff0c;并用FeignClient 注解进行注解 value "服务名" 要调用的服务名 服务得到路径&#xff0c;对应的是c…...

HarmonyOS应用开发者高级认证(88分答案)

看好选择题&#xff0c;每个2分多答对2个刚好88分&#xff0c;祝你顺利。 其它帮扶选择题。 一、判断 只要使用端云一体化的云端资源就需要支付费用&#xff08;错&#xff09;所有使用Component修饰的自定义组件都支持onPageShow&#xff0c;onBackPress和onPageHide生命周期…...

离散Hopfield神经网络分类——高校科研能力评价

大家好&#xff0c;我是带我去滑雪&#xff01; 高校科研能力评价的重要性在于它对高等教育和科研体系的有效运作、发展和提高质量具有深远的影响。良好的科研能力评价可以帮助高校识别其在不同领域的强项和薄弱点&#xff0c;从而制定战略&#xff0c;改进教学和科研&#xff…...

Run highlighted commands using IDE

背景 有时候在 IEDE 的命令行中输入命令&#xff0c;会弹出如下提示&#xff0c;或者命令被着了背景色了&#xff0c;是怎么回事&#xff1f; 其实就是提示你可以使用 IDEA 的功能替代命令行。比如使用ctrlenter或cmdenter之后使用的就是 IDEA 里的功能 直接enter运行&#x…...

vscode文件跳转(vue项目)

在 .vue 文件中&#xff0c;点击组件名打开 方式1&#xff1a; 在 vue 组件名上&#xff0c;桉住ctrl 鼠标左键 // 重新打开一个tab 方式2&#xff1a; 在 vue 组件名上&#xff0c;桉住ctrl shift 鼠标左键 // 在右侧拆分&#xff0c;并打开一个tab .vue文件的跳转 按住 …...

嵌入式Linux系统中内存分配详解

Linux中内存管理 内存管理的主要工作就是对物理内存进行组织&#xff0c;然后对物理内存的分配和回收。但是Linux引入了虚拟地址的概念。 虚拟地址的作用 如果用户进程直接操作物理地址会有以下的坏处&#xff1a; 1、 用户进程可以直接操作内核对应的内存&#xff0c;破坏…...

4、FFmpeg命令行操作4

ffplay命令-高级选项1 选项 说明 -stats 打印多个回放统计信息,包括显示流持续时间,编解码器参数,流中的当前位置,以及音频/视频同步差值。默认情况下处于启用状态,要显式禁用它则需要指定-nostats。。 -fast 非标准化规范的多媒体兼容优化。 -genpts 生…...

如何通过命令查看某一文件的内容改动和提交记录

1. 查看最近10条的提交记录 一行显示 git log --oneline -102.查看某一个文件的提交记录 git log --oneline -10 文件路径3.查看某个文件的修改内容 查看某次提交的修改 内容 git show bcd9299 查看某次提交某个文件的修改内容git show bcd9299 文件路径4.对比两次提交内容的…...

更安全的ssh协议与Gui图形化界面使用

目录 前言&#xff1a; 一.Gui图形化界面的使用 二.ssh协议 SSH的主要作用包括&#xff1a; 相比其他网络协议&#xff0c;SSH的优势包括&#xff1a; 三.idea集成Git 前言&#xff1a; 上一篇讲解了git的命令用法以及https协议&#xff0c;但是这个协议放在做团队项目的…...

❤ Uniapp使用 ( 三 配置和各种使用篇)

❤ Uniapp使用 ( 三 配置和各种使用篇) 1、 uniapp引入 vant 引入方式 1、下载vant源码 方式一&#xff1a;从 Vant 官网首页进入 GitHub下载对应版本的压缩包,将文件解压后备用,确保下载的压缩包里有dist 文件夹 2、创建 uniapp 项目,在根目录下新建 一个文件夹wxcomponent…...

k8s 创建普通用户使用

创建一个用户只能访问"abc", “dev”, “prod” 的三个命名空间 创建用户 apiVersion: v1 kind: ServiceAccount metadata:name: abc-bbc-mmc-user或者直接创建 kubectl create user abc-bbc-mmc-user创建角色 apiVersion: rbac.authorization.k8s.io/v1 kind: R…...

【微软技术栈】C#.NET 依赖项注入

本文内容 多个构造函数发现规则使用扩展方法注册服务组框架提供的服务服务生存期服务注册方法作用域验证范围场景 .NET 支持依赖关系注入 (DI) 软件设计模式&#xff0c;这是一种在类及其依赖项之间实现控制反转 (IoC) 的技术。 .NET 中的依赖关系注入是框架的内置部分&#…...

评国青、优青、杰青,到底需要什么级别的文章?五篇代表作如何选?

一到年底就听同事们讨论到底申报“杰青”、“优青”还是“国青”&#xff0c;那么&#xff0c;“杰青”到底是什么呢&#xff1f;它和“优青”、“国青”又有什么区别呢&#xff1f; 杰青&#xff0c;全称“国家杰出青年基金获得者”&#xff0c;是国家自然科学基金里人才资助…...

使用双动态令牌混合器学习全局和局部动态以进行视觉识别

TransXNet: Learning Both Global and Local Dynamics with a Dual Dynamic Token Mixer for Visual Recognition 1、问题与解决2、引言3、方法3.1 双动态令牌混合器(D- Mixer)3.2 IDConv(Input-dependent Depthwise Convolution)3.3 Overlapping Spatial Reduction Attention …...

Flutter笔记 - 关于 fit 属性以及相关知识的总结

Flutter笔记 关于 fit 属性以及相关知识的总结 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/13434451…...

如何在PPT中去除编辑密码?

&#xff1a;忘记PPT幻灯片密码&#xff1f;最简单的办法在这里&#xff01; 【摘要】&#xff1a;具体步骤如下&#xff1a;第一步百度搜索【密码帝官网】&#xff0c;第二步点击“立即开始”&#xff0c;在用户中心上传文件即可。不用下载软件&#xff0c;手机电脑都可以用。…...

Kotlin库实现多线程爬取数据

由于字数限制&#xff0c;以下是一个简化版的爬虫程序示例&#xff0c;使用了Kotlin的网络库kotlinx.coroutines和kotlinx.html。这个程序会爬取一个简单的Python多线程跑数据的网页&#xff0c;并打印出结果。 import kotlinx.coroutines.* import kotlinx.html.* import java…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...