【华为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
题目 某组织举行会议,来了多个代表团同时到达,接待处只有一辆汽车,可以同时接待多个代表团,为了提高车辆利用率,请帮接待员计算可以坐满车的接待方案,输出方案数量。 约束: 1.一个团只能上一辆车࿰…...
利用servlet实现对书籍书名、单价、数量等信息的添加,计算总价
1.题目要求 利用servlet实现对书籍书名、单价、数量等信息的添加,计算总价。 要求:输入两次表单信息,在一个成功返回的页面里面显示两次的数据。 2.Book实体类 package com.hjj.sevletgk.hw7.book;/*** author:嘉佳 Date:2023/10/8 15:16*…...
一键批量转码:将MP4视频转为MP3音频的简单方法
随着数字媒体设备的普及,视频和音频格式转换的需求也越来越常见。其中,将MP4视频批量转换为MP3音频的需求尤为普遍。无论是为了提取视频中的背景音乐,还是为了在手机或电脑上方便地收听视频音频,这个过程都变得非常重要。接下来我…...
java入门,记一次微服务间feigin请求的问题
一、前言 记录工作中遇到的开发问题,而不是写博客凑字数。 二、微服务调用 1、通过本服务调用另外一个服务,需要定义一个接口,并用FeignClient 注解进行注解 value "服务名" 要调用的服务名 服务得到路径,对应的是c…...
HarmonyOS应用开发者高级认证(88分答案)
看好选择题,每个2分多答对2个刚好88分,祝你顺利。 其它帮扶选择题。 一、判断 只要使用端云一体化的云端资源就需要支付费用(错)所有使用Component修饰的自定义组件都支持onPageShow,onBackPress和onPageHide生命周期…...
离散Hopfield神经网络分类——高校科研能力评价
大家好,我是带我去滑雪! 高校科研能力评价的重要性在于它对高等教育和科研体系的有效运作、发展和提高质量具有深远的影响。良好的科研能力评价可以帮助高校识别其在不同领域的强项和薄弱点,从而制定战略,改进教学和科研ÿ…...
Run highlighted commands using IDE
背景 有时候在 IEDE 的命令行中输入命令,会弹出如下提示,或者命令被着了背景色了,是怎么回事? 其实就是提示你可以使用 IDEA 的功能替代命令行。比如使用ctrlenter或cmdenter之后使用的就是 IDEA 里的功能 直接enter运行&#x…...
vscode文件跳转(vue项目)
在 .vue 文件中,点击组件名打开 方式1: 在 vue 组件名上,桉住ctrl 鼠标左键 // 重新打开一个tab 方式2: 在 vue 组件名上,桉住ctrl shift 鼠标左键 // 在右侧拆分,并打开一个tab .vue文件的跳转 按住 …...
嵌入式Linux系统中内存分配详解
Linux中内存管理 内存管理的主要工作就是对物理内存进行组织,然后对物理内存的分配和回收。但是Linux引入了虚拟地址的概念。 虚拟地址的作用 如果用户进程直接操作物理地址会有以下的坏处: 1、 用户进程可以直接操作内核对应的内存,破坏…...
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图形化界面使用
目录 前言: 一.Gui图形化界面的使用 二.ssh协议 SSH的主要作用包括: 相比其他网络协议,SSH的优势包括: 三.idea集成Git 前言: 上一篇讲解了git的命令用法以及https协议,但是这个协议放在做团队项目的…...
❤ Uniapp使用 ( 三 配置和各种使用篇)
❤ Uniapp使用 ( 三 配置和各种使用篇) 1、 uniapp引入 vant 引入方式 1、下载vant源码 方式一:从 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) 软件设计模式,这是一种在类及其依赖项之间实现控制反转 (IoC) 的技术。 .NET 中的依赖关系注入是框架的内置部分&#…...
评国青、优青、杰青,到底需要什么级别的文章?五篇代表作如何选?
一到年底就听同事们讨论到底申报“杰青”、“优青”还是“国青”,那么,“杰青”到底是什么呢?它和“优青”、“国青”又有什么区别呢? 杰青,全称“国家杰出青年基金获得者”,是国家自然科学基金里人才资助…...
使用双动态令牌混合器学习全局和局部动态以进行视觉识别
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 属性以及相关知识的总结 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/details/13434451…...
如何在PPT中去除编辑密码?
:忘记PPT幻灯片密码?最简单的办法在这里! 【摘要】:具体步骤如下:第一步百度搜索【密码帝官网】,第二步点击“立即开始”,在用户中心上传文件即可。不用下载软件,手机电脑都可以用。…...
Kotlin库实现多线程爬取数据
由于字数限制,以下是一个简化版的爬虫程序示例,使用了Kotlin的网络库kotlinx.coroutines和kotlinx.html。这个程序会爬取一个简单的Python多线程跑数据的网页,并打印出结果。 import kotlinx.coroutines.* import kotlinx.html.* import java…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
python爬虫——气象数据爬取
一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用: 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests:发送 …...
