华为OD机试 - 代表团坐车 - 动态规划（Java 2023 B卷 200分）

本文主要是介绍华为OD机试 - 代表团坐车 - 动态规划（Java 2023 B卷 200分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车，可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满的接待方案，输出方案数量。

约束：

1. 一个团只能上一辆车，并且代表团(代表团数量小于30，每个代表团人数小于30)小于汽车容量(汽车容量小于100)；
2. 需要将车辆坐满。

二、输入描述

第一行输入代表团人数，英文逗号隔开，代表团数量小于30，每个代表团人数小于30
第二行输入汽车载客量，汽车容量小于100

三、输出描述

坐满汽车的方案数量
如果无解输出0

四、解题思路

1. 第一行输入代表团人数，英文逗号隔开；
2. 第二行输入汽车载客量，汽车容量小于100；
3. 通过java8 Stream表达式（简洁/方便/上档次）快速拆解输入行；
4. 初始化动态规划数组，dp[i]表示载客量为i时的方案数；
5. 载客量为0时，方案数为1（不接待任何代表团）；
6. 动态规划转移，从后往前遍历，避免重复计算；
7. 转移方程：dp[j] += dp[j - group]，表示加上接待当前代表团后的方案数；
8. 输出坐满汽车的方案数量；

五、Java算法源码

package com.guor.od;import java.util.*;public class OdTest {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取代表团人数int[] groups = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();// 读取汽车载客量int capacity = Integer.parseInt(sc.nextLine());// 初始化动态规划数组，dp[i]表示载客量为i时的方案数int[] dp = new int[capacity + 1];// 载客量为0时，方案数为1（不接待任何代表团）dp[0] = 1;// 动态规划转移for (int group : groups) {// 从后往前遍历，避免重复计算for (int j = capacity; j >= group; j--) {// 转移方程：dp[j] += dp[j - group]，表示加上接待当前代表团后的方案数dp[j] += dp[j - group];}}// 无解if (dp[capacity] == 0) {System.out.println(0);} else { // 有解System.out.println(dp[capacity]);}}
}

六、效果展示

1、输入

5,4,2,3,2,4,9
10

2、输出

4

3、说明

解释以下几种方式都可以坐满扯，所以优先街道输出为4
[2, 3, 5]
[2, 4, 4]
[2, 3, 5]
[2, 4, 4]

🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

这篇关于华为OD机试 - 代表团坐车 - 动态规划（Java 2023 B卷 200分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---