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

2023-11-09 07:52

本文主要是介绍【华为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];}
}

推荐

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

这篇关于【华为OD题库-007】代表团坐车-Java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/374868

相关文章

Spring Security 单点登录与自动登录机制的实现原理

《SpringSecurity单点登录与自动登录机制的实现原理》本文探讨SpringSecurity实现单点登录(SSO)与自动登录机制,涵盖JWT跨系统认证、RememberMe持久化Token... 目录一、核心概念解析1.1 单点登录(SSO)1.2 自动登录(Remember Me)二、代码分析三、

springboot自定义注解RateLimiter限流注解技术文档详解

《springboot自定义注解RateLimiter限流注解技术文档详解》文章介绍了限流技术的概念、作用及实现方式,通过SpringAOP拦截方法、缓存存储计数器,结合注解、枚举、异常类等核心组件,... 目录什么是限流系统架构核心组件详解1. 限流注解 (@RateLimiter)2. 限流类型枚举 (

Java Thread中join方法使用举例详解

《JavaThread中join方法使用举例详解》JavaThread中join()方法主要是让调用改方法的thread完成run方法里面的东西后,在执行join()方法后面的代码,这篇文章主要介绍... 目录前言1.join()方法的定义和作用2.join()方法的三个重载版本3.join()方法的工作原

Spring AI使用tool Calling和MCP的示例详解

《SpringAI使用toolCalling和MCP的示例详解》SpringAI1.0.0.M6引入ToolCalling与MCP协议,提升AI与工具交互的扩展性与标准化,支持信息检索、行动执行等... 目录深入探索 Spring AI聊天接口示例Function CallingMCPSTDIOSSE结束语

Java获取当前时间String类型和Date类型方式

《Java获取当前时间String类型和Date类型方式》:本文主要介绍Java获取当前时间String类型和Date类型方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录Java获取当前时间String和Date类型String类型和Date类型输出结果总结Java获取

Spring Boot Actuator应用监控与管理的详细步骤

《SpringBootActuator应用监控与管理的详细步骤》SpringBootActuator是SpringBoot的监控工具,提供健康检查、性能指标、日志管理等核心功能,支持自定义和扩展端... 目录一、 Spring Boot Actuator 概述二、 集成 Spring Boot Actuat

OpenCV在Java中的完整集成指南分享

《OpenCV在Java中的完整集成指南分享》本文详解了在Java中集成OpenCV的方法,涵盖jar包导入、dll配置、JNI路径设置及跨平台兼容性处理,提供了图像处理、特征检测、实时视频分析等应用... 目录1. OpenCV简介与应用领域1.1 OpenCV的诞生与发展1.2 OpenCV的应用领域2

在Java中使用OpenCV实践

《在Java中使用OpenCV实践》用户分享了在Java项目中集成OpenCV4.10.0的实践经验,涵盖库简介、Windows安装、依赖配置及灰度图测试,强调其在图像处理领域的多功能性,并计划后续探... 目录前言一 、OpenCV1.简介2.下载与安装3.目录说明二、在Java项目中使用三 、测试1.测

Spring Bean初始化及@PostConstruc执行顺序示例详解

《SpringBean初始化及@PostConstruc执行顺序示例详解》本文给大家介绍SpringBean初始化及@PostConstruc执行顺序,本文通过实例代码给大家介绍的非常详细,对大家的... 目录1. Bean初始化执行顺序2. 成员变量初始化顺序2.1 普通Java类(非Spring环境)(

Spring Boot 中的默认异常处理机制及执行流程

《SpringBoot中的默认异常处理机制及执行流程》SpringBoot内置BasicErrorController,自动处理异常并生成HTML/JSON响应,支持自定义错误路径、配置及扩展,如... 目录Spring Boot 异常处理机制详解默认错误页面功能自动异常转换机制错误属性配置选项默认错误处理