解题思路

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

1. 问题拆解

• 网络共有 N 层，每层有 H 个权重
• 每一层只能选择一种量化比特数 $

题目内容

在一个深度神经网络中，网络的权重通常以浮点数的形式存储。为了减少内存占用和提高计算效率，需要将这些浮点数量化为整数,例如可通过$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$。