华为 · 动态规划 · 算法编程题
华为 动态规划 时限 1 秒 / 256 MB

题目描述

在一台边缘设备上部署一个已缩放到合适范围的神经网络权重矩阵。网络共有 N 层，每层有 H 个实数权重。每一层必须统一选择一个量化位宽 q，且 q 只能取 2、4、8 三种之一。所有层选择的位宽之和不超过 Qmax。
若某层选择位宽 q，则对该层每个权重 w 执行：
1) 放大并取整：wq = int(w * 2^q)
2) 还原：wr = wq / 2^q
该层的量化误差定义为该层所有权重的 |w - wr| 之和。全网误差为各层误差之和。目标是在总位宽预算不超过 Qmax 的前提下，使全网误差最小。输出最小总误差乘以 100 后向下取整的结果。

输入输出

输入描述
· 第一行：N H Qmax
· 接下来 N 行：每行 H 个实数，表示对应层的权重
输出描述
· 一行，一个整数，为最小总误差乘以 100 后向下取整

样例共 1 组

样例 1 · 若两层都选 4 比特，误差之和为 0.0625 + 0.0625 = 0.125 预算 4 + 4 = 8，满足约束 输出 floor(0.125 * 100) = 12 其他组合（如 2+4 或 2+2）误差更大
输入
2 3 8
0.1 0.5 0.9
0.3 0.75 0.2
输出
12

算法解析依据充分

考点：动态规划

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：动态规划

本题切入点

每层独立选 2/4/8 位宽、总位宽不超 Qmax 的最小总误差：先对每层算三种位宽各自的误差，再做以「位宽和」为容量的分组背包 DP。

把问题拆成子问题，用状态表示「已处理到哪儿」，靠转移方程递推。

思路框架（动态规划 通法 · 非本题专属）

  1. 定义状态：dp[i] / dp[i][j] 表示什么（这是最关键的一步，状态定义错就全错）。
  2. 写转移方程：当前状态由哪些更小的状态推来。
  3. 确定初始条件与遍历顺序（保证用到的状态已算好）。
  4. 确定答案取哪个状态；数值大时全程取模。

实现要点：一般是「先枚举阶段，再枚举状态，最后枚举决策」三层循环；空间大时可滚动数组优化。

复杂度：时间 O(状态数 × 转移代价) ｜ 空间 O(状态数)

该范式的通法易错点

  • 状态定义不完整（漏了必要维度），导致子问题之间有后效性。
  • 初始化写错（尤其「恰好」与「至多」的初值差别）。
  • 遍历顺序与依赖方向不一致。

样例解读

样例 1：输入 2 3 8 / 0.1 0.5 0.9 / 0.3 0.75 0.2 → 输出 12

若两层都选 4 比特，误差之和为 0.0625 + 0.0625 = 0.125

预算 4 + 4 = 8，满足约束

输出 floor(0.125 * 100) = 12

其他组合（如 2+4 或 2+2）误差更大

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2025年秋招-华为-12月17号AI岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解