解题思路

题目要求：模型有 $N$ 层，每层必须从给定的若干量化方案中选择一种。每种方案带来该层的精度损失 $loss$ 与内存占用 $mem$。希望在满足总精度损失不超过阈值 $T$ 的前提下，使总内存占用最小。

这是一个典型的相关算法：多重选择背包（Multiple-Choice Knapsack Problem, MCKP）

• “背包容量”是允许的总精度损失 $T$
• 每一层相当于一个“组”，组内必须选且只能选一个方案
• 目标是最小化总内存（而非最大化价值）

题目内容

深度学习模型的推理量化问题，该模型包含多个全连接层，每个层可以选择不同的量化方案（$16-bit$量化、$8-bit$量化），不同方案会带来不同的内存占用和精度损失。

需要选择模型最优的量化方案组合，在满足总精度损失约束的前提下最小化内存占用。

本题考虑$16bit$，$8bit$量化两种场景

在给定的如下条件：

每层在不同位宽下的精度损失（如$8$位量化时，第i层的精度损失为$loss_i$）

每层在不同位宽下的内存占用（如$8$位量化时，第i层的内存占用为$mem_i$）

模型整体的精度损失不能超过阈值$T$

请设计一个算法，为每层选择最优量化位宽，使得总内存占用最小且满足总精度损失小于$T$。

输入描述

第一行：整数$L$（层数）和浮点数$T$（精度损失阈值）

接下来$L$行，每行描述一层的量化选项：

整数$K$（该层可选的量化位宽数量）

$K$组数据，每组包含：位宽描述字符串($8bit$和$16bit$)、精度损失（浮点数）、内存占用（浮点数）

输出描述

最优总内存占用（保留两位小数）

样例1

输入

3 0.3
2 8bit 0.2 100.0 16bit 0.1 200.0
2 8bit 0.3 150.0 16bit 0.1 300.0
1 8bit 0.1 150.0

输出

650.00

说明

$3$层，满足精度阈值$0.3$

第一层，$2$种量化位宽数量，$8bit$ 精度损失$0.2$，内存$100$；$16bit$ 精度损失$0.1$，内存$200$

第二层，$2$种量化位宽数量，$8bit$ 精度损失$0.3$，内存$150$；$16bit$ 精度损失$0.1$，内存$300$

第三层，1种量化位宽数量，$8bit$ 精度损失$0.1$，内存$150$

满足$0.3$精度损失的最优内存占用为$650$

第一层$16bit$，精度损失$200$

第二层$16bit$，精度损失$300$

第三层$8bit$，精度损失$150$

总共内存占用$200+300+150=650$

样例2

输入

2 0.5
2 8bit 0.2 100.0 16bit 0.1 200.0
2 8bit 0.3 150.0 16bit 0.15 300.0

输出

250.00

说明

$2$层，精度阈值为$0.5$

第一层，$2$种量化位宽数量，$8bit$ 精度损失$0.2$ 内存$100$；$16bit$精度损失$0.1$ 内存$200$

第二层，$2$种量化位宽数量，$8bit$ 精度损失$0.3$ 内存$150$；$16bit$精度损失$0.15$ 内存$300$

满足$0.5$精度损失的最优内存占用为$250$

第一层$8bit$，精度损失$0.2$，内存占用$100$

第二层$8bit$，精度损失$0.3$，内存占用$150$

总共内存占用$100+150=250$