模型量化最小误差

题目分析

神经网络有 层，每层有 个实数权重。每层需要选择一个量化位宽 ，所有层的位宽之和不能超过 。

对于位宽 ，每个权重 的量化过程为：

1. 放大并取整：
2. 还原：

每层的量化误差为该层所有权重的 之和，总误差为所有层误差之和。求最小总误差乘以 后向下取整的结果。

思路

分组背包 DP

这是一个经典的分组背包问题。每一层是一个"组"，每组有 种选择（位宽 、、），对应的"体积"就是位宽值，"价值"就是该层在对应位宽下的量化误差。背包容量为 ，目标是在总位宽不超过预算的前提下，最小化总误差。

预处理： 对于每一层，分别计算选择位宽 、、 时的量化误差。具体地，对每个权重 ，计算 ，然后对该层所有权重求和。

DP 转移： 设 表示已经处理完前若干层、总位宽恰好为 时的最小总误差。对于第 层，枚举三种位宽选择 ，转移为：

$$

最终答案为 。

以样例验证： 。

• 第 层 ： 误差 ， 误差 ， 误差
• 第 层 ： 误差 ， 误差 ， 误差

选 ，总位宽 ，总误差 ，结果 。

复杂度

• 时间复杂度：，预处理每层误差 ，DP 转移
• 空间复杂度：，存储权重和 DP 数组

代码

import sys
import math

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    H = int(input_data[idx]); idx += 1
    Qmax = int(input_data[idx]); idx += 1

    # 预处理每层在三种位宽下的量化误差
    layer_errors = []
    for i in range(N):
        weights = []
        for j in range(H):
            weights.append(float(input_data[idx])); idx += 1
        errors = {}
        for q in [2, 4, 8]:
            err = 0.0
            scale = 2 ** q
            for w in weights:
                wq = int(w * scale)
                wr = wq / scale
                err += (w - wr)
            errors[q] = err
        layer_errors.append(errors)

    # 分组背包 DP
    INF = float('inf')
    dp = [INF] * (Qmax + 1)
    dp[0] = 0.0

    for i in range(N):
        new_dp = [INF] * (Qmax + 1)
        for used in range(Qmax + 1):
            if dp[used] == INF:
                continue
            for q in [2, 4, 8]:
                new_used = used + q
                if new_used <= Qmax:
                    val = dp[used] + layer_errors[i][q]
                    if val < new_dp[new_used]:
                        new_dp[new_used] = val
        dp = new_dp

    min_err = min(dp)
    print(math.floor(min_err * 100))

main()