5.20华为OD机试真题 新系统 - 多模型版本的最优调度 (JavaPyCC++JsGo)

多模型版本的最优调度

2026 华为OD机试真题 5月20日华为OD上机新系统考试真题 100 分题型

Click查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在大语言模型推理服务中，有多个不同大小的模型版本可供选择。每个模型版本有不同的准确率和推理延迟。给定查询次数 N 和总时间预算 T，为每个查询选择一个模型版本，使得在不超过时间预算的前提下，总准确率最大。

2026 华为OD机试真题 5月20日华为OD上机新系统考试真题 100 分题型

输入描述

• 查询次数 N
• 总时间预算 T
• 模型准确率 accuracy[i]
• 模型延迟 latency[i]

输入格式：N,T,{accuracy[0],accuracy[1],...},{latency[0],latency[1],...}

输出描述

最大总准确率

补充说明

• 同一个模型可以被多次选择
• 0< 查询数量 N <= 10
• 0< 总时间预算 T < 100
• 0< 准确率 accuracy[i] <100，表示多个百分点
• 0< 延迟 latency[i] < 20
• 0< 模型版本数量 <= 10
• 可以考虑采用递归方法完成
• 必须查满 N 次

示例1

输入

2,4,{80,90,95},{1,2,3}

输出

180

说明

最优选择为选取两个准确率为 90 的模型，总耗时为 4，总准确率为 180。

示例2

输入

2,2,{80,90,95},{2,2,3}

输出

0

说明

无法凑满要求的 2 个模型，因此总准确率为 0

解题思路

本题是一个多阶段决策优化问题，等价于在有容量限制的背包中装入 N 件物品（每件物品可重复选），求最大价值。由于 N <= 10、T < 100，数据规模较小，适合使用动态规划。

动态规划状态定义：dp[i][t]表示完成 i 次查询且恰好用时 t 时，能够达到的最大总准确率。初始状态dp[0][0] = 0，其余为不可达（-1）。

状态转移方程：对于第 i 次查询，枚举所有可用的模型版本 j：

• 若当前时间 t >= latency[j] 且 dp[i-1][t - latency[j]] 可达，则：dp[i][t] = max(dp[i][t], dp[i-1][t - latency[j]] + accuracy[j])

答案：从 dp[N]（完成 N 次查询的所有可能用时）中取最大值，即为不超过时间预算 T 的最大总准确率。若 dp[N] 全为 -1（无法凑满 N 次查询），返回 0。

复杂度分析

• 时间复杂度: O(N * T * M)，其中 M 为模型版本数量，N <= 10，T < 100，M <= 10，最多约 10000 次操作。
• 空间复杂度: O(N * T)，使用二维 DP 表，大小不超过