解题思路

本题本质是一个 带约束的最优化问题，可以转化为 多重选择的动态规划（Multiple Choice Knapsack）。

1. 问题拆解

• 网络共有 N 层，每层有 H 个权重
• 每一层只能选择一种量化比特数 $Q_i \in {2, 4, 8}$
• 整体约束： $\sum_{i=1}^N Q_i \le Q_{\max}$
• 目标：最小化所有层的量化误差总和

2. 单层量化误差的计算（预处理）

对于某一层 i，如果选择量化比特 Q：

$$W_q = \text{int}(W_{\text{float}} \times 2^Q)$$

量化还原后为：

$$\hat{W} = \frac{W_q}{2^Q}$$

该层的总误差为：

$$\text{err}[i][Q] = \sum_{j=1}^{H} \left| W_{i,j} - \hat{W}_{i,j} \right|$$

由于 Q 只有 {2,4,8} 三种取值，我们可以 预先计算 每一层在三种量化比特下的误差。

3. 动态规划建模

状态定义

设：

$$dp[i][q] = \text{前 } i \text{ 层，总比特数为 } q \text{ 时的最小误差}$$

状态转移

对于第 i 层，尝试选择 {2,4,8} 中的一种：

$$dp[i][q] = \min \Big( dp[i-1][q-2] + err[i][2],; dp[i-1][q-4] + err[i][4],; dp[i-1][q-8] + err[i][8] \Big)$$

前提是 q - Q >= 0。

初始化

• dp[0][0] = 0
• 其他状态初始化为极大值

最终答案

$\min_{q \le Q_{\max}} dp[N][q]$

4. 输出处理

题目要求输出：

$\lfloor \text{最小误差} \times 100 \rfloor$

复杂度分析

时间复杂度

• 误差预处理： $O(N \times H \times 3)$
• 动态规划： $O(N \times Q_{\max} \times 3)$

空间复杂度

• 使用滚动数组优化后： $O(Q_{\max})$

代码实现

Python

import math
import sys

def solve():
    data = sys.stdin.read().strip().split()
    idx = 0

    N = int(data[idx]); idx += 1
    H = int(data[idx]); idx += 1
    Qmax = int(data[idx]); idx += 1

    # 读取权重
    weights = []
    for _ in range(N):
        layer = []
        for _ in range(H):
            layer.append(float(data[idx]))
            idx += 1
        weights.append(layer)

    # 预计算每一层在 2/4/8 bit 下的误差
    bits = [2, 4, 8]
    err = [[0.0]*3 for _ in range(N)]

    for i in range(N):
        for k, Q in enumerate(bits):
            scale = 2 ** Q
            e = 0.0
            for w in weights[i]:
                wq = int(w * scale)
                wr = wq / scale
                e += abs(w - wr)
            err[i][k] = e

    INF = 1e100
    dp = [INF] * (Qmax + 1)
    dp[0] = 0.0

    # 动态规划
    for i in range(N):
        ndp = [INF] * (Qmax + 1)
        for q in range(Qmax + 1):
            if dp[q] >= INF:
                continue
            for k, Q in enumerate(bits):
                if q + Q <= Qmax:
                    ndp[q + Q] = min(ndp[q + Q], dp[q] + err[i][k])
        dp = ndp

    ans = min(dp)
    print(int(ans * 100))

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {

    static double solve(int N, int H, int Qmax, double[][] w) {
        int[] bits = {2, 4, 8};
        double[][] err = new double[N][3];

        // 预处理误差
        for (int i = 0; i < N; i++) {
            for (int k = 0; k < 3; k++) {
                int Q = bits[k];
                double scale = 1 << Q;
                double e = 0.0;
                for (int j = 0; j < H; j++) {
                    int wq = (int)(w[i][j] * scale);
                    double wr = wq / scale;
                    e += Math.abs(w[i][j] - wr);
                }
                err[i][k] = e;
            }
        }

        double INF = 1e100;
        double[] dp = new double[Qmax + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0.0;

        // 动态规划
        for (int i = 0; i < N; i++) {
            double[] ndp = new double[Qmax + 1];
            Arrays.fill(ndp, INF);
            for (int q = 0; q <= Qmax; q++) {
                if (dp[q] >= INF) continue;
                for (int k = 0; k < 3; k++) {
                    int Q = bits[k];
                    if (q + Q <= Qmax) {
                        ndp[q + Q] = Math.min(ndp[q + Q], dp[q] + err[i][k]);
                    }
                }
            }
            dp = ndp;
        }

        double ans = INF;
        for (int q = 0; q <= Qmax; q++) {
            ans = Math.min(ans, dp[q]);
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int H = sc.nextInt();
        int Qmax = sc.nextInt();

        double[][] w = new double[N][H];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < H; j++) {
                w[i][j] = sc.nextDouble();
            }
        }

        double ans = solve(N, H, Qmax, w);
        System.out.println((int)(ans * 100));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, H, Qmax;
    cin >> N >> H >> Qmax;

    vector<vector<double>> w(N, vector<double>(H));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < H; j++) {
            cin >> w[i][j];
        }
    }

    vector<int> bits = {2, 4, 8};
    vector<vector<double>> err(N, vector<double>(3, 0.0));

    // 预处理误差
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < 3; k++) {
            int Q = bits[k];
            double scale = 1 << Q;
            double e = 0.0;
            for (int j = 0; j < H; j++) {
                int wq = (int)(w[i][j] * scale);
                double wr = wq / scale;
                e += fabs(w[i][j] - wr);
            }
            err[i][k] = e;
        }
    }

    const double INF = 1e100;
    vector<double> dp(Qmax + 1, INF);
    dp[0] = 0.0;

    // 动态规划
    for (int i = 0; i < N; i++) {
        vector<double> ndp(Qmax + 1, INF);
        for (int q = 0; q <= Qmax; q++) {
            if (dp[q] >= INF) continue;
            for (int k = 0; k < 3; k++) {
                int Q = bits[k];
                if (q + Q <= Qmax) {
                    ndp[q + Q] = min(ndp[q + Q], dp[q] + err[i][k]);
                }
            }
        }
        dp.swap(ndp);
    }

    double ans = *min_element(dp.begin(), dp.end());
    cout << (int)(ans * 100) << "\n";

    return 0;
}

题目内容

在一个深度神经网络中，网络的权重通常以浮点数的形式存储。为了减少内存占用和提高计算效率，需要将这些浮点数量化为整数,例如可通过$int (W _{float }*2^8)$将一个小于$1$的浮点数量化为$INT8$。

假设我们有一组$[N,H]$的模型权重，其中：$N$表示网络的层数，$H$表示每一层的维度。现在需要将网络权重进行量化，已知权重已经过预处理缩放到合适的值，可通过$W_q=int(W_{float} *2^{Q_i})$直接量化到对应的比特位$Q_i$，同时定义量化误差为$\Delta = \left| W_{\text{float}} - \frac{W_q}{2q_i} \right|$ 同一层选用的量化比特是相同的，不同层之间可选择不同的量化比特。定义整个模型每一层的量化比特数为$[Q_1,Q_2,...,Q_N]$,并限定 $Q_i∈ [2,4,8]$，为了保证整体空间压缩足够小，需满足$\sum_{i=1}^{N} Q_i \leq Q_{\text{max}}$。请给出最优的量化方案，使得所有层的量化误差总和最小。

输入描述

第一行:$N,H,Q_{max}$

接下来$N$行是模型权重，每行$H$个系数，系数间用空格分隔$(0<N<=300，0<H<=100，0<Q_{max} <=2400)$

输出描述

请输出在最优方案下，整个网络的最小总量化误差。请将答案*$100$后取整输出(例如最小总量化误差为$12.345678$时，输出$1234$)

样例1

输入

3 10 6
0.669342691379556 0.6232664728193106 0.009648814115477689 0.25655923835608296 0.8542091541905418 0.22734652633918107 0.3856022177718754 0.4735219607872916 0.7352822546717339 0.8810700172773613
0.8998864964296006 0.5355025966489801 0.9114305820079228 0.7237159502129922 0.8114010729538255 0.5647698690173886 0.5656036144842292 0.2915636526042238 0.4633626072815791 0.4933586717844284
0.5681407125745037 0.972337640852664 0.33248445308239827 0.8870229039214033 0.2869760304712957 0.5912444652782809 0.2513253965878265 0.8945001503120086 0.7217848272492855 0.21360959764416299

输出

384

说明

$N=3,H=10,\sum Q_i=6$ 每层只能使用2比特量化，量化误差分别为$1.365,1.260,1.219$,总量化误差$3.844$,*$100$后输出整数为$384$。

样例2

输入

3 10 24
0.669342691379556 0.6232664728193106 0.009648814115477689 0.25655923835608296 0.8542091541905418 0.22734652633918107 0.3856022177718754 0.4735219607872916 0.7352822546717339 0.8810700172773613
0.8998864964296006 0.5355025966489801 0.9114305820079228 0.7237159502129922 0.8114010729538255 0.5647698690173886 0.5656036144842292 0.2915636526042238 0.4633626072815791 0.4933586717844284
0.5681407125745037 0.972337640852664 0.33248445308239827 0.8870229039214033 0.2869760304712957 0.5912444652782809 0.2513253965878265 0.8945001503120086 0.7217848272492855 0.21360959764416299

输出

5

说明

$N=3,H=10,\sum Q_i=24$ 每层只能使用$8$比特量化，量化误差分别为$0.018,0.018,0.02$,总量化误差$0.056$,*$100$后输出整数为$5$。