#P4568. 第2题-模型推理量化加速优化问题
-
1000ms
Tried: 16
Accepted: 5
Difficulty: 6
所属公司 :
华为
时间 :2026年2月4日-AI方向
-
算法标签>动态规划
第2题-模型推理量化加速优化问题
解题思路
题目要求:模型有 N 层,每层必须从给定的若干量化方案中选择一种。每种方案带来该层的精度损失 loss 与内存占用 mem。希望在满足总精度损失不超过阈值 T 的前提下,使总内存占用最小。
这是一个典型的相关算法:多重选择背包(Multiple-Choice Knapsack Problem, MCKP)
- “背包容量”是允许的总精度损失 T
- 每一层相当于一个“组”,组内必须选且只能选一个方案
- 目标是最小化总内存(而非最大化价值)
关键处理:浮点精度损失转整数
由于 loss 和 T 是浮点数,直接做 DP 容易受精度误差影响。题目输出内存保留两位小数,通常精度损失也可按两位小数处理,因此:
- 令缩放因子 S=100
- 将 loss 转为整数权重:w=round(loss×S)
- 将阈值转为整数容量:W=round(T×S)
这样就转化为整数背包,避免浮点比较误差。
状态设计(最小化型 DP)
设 dp[j] 表示:处理到当前层时,总精度损失为 j(整数)时的最小内存占用。
初始化:
- dp[0]=0
- 其他为 +∞
转移(逐层更新,保证每层必须选一个):
- 对每一层建立新数组 ndp,初始全为 +∞
- 对上一层所有可达的 j,枚举本层每个方案 (w,mem),更新:ndp[j+w]=min(ndp[j+w], dp[j]+mem),j+w≤W
答案:
- 处理完 N 层后,取 0≤j≤Wmindp[j]
复杂度分析
设总容量 W=round(100T),第 i 层方案数为 Ki,则:
- 时间复杂度:O(W⋅i=1∑NKi) 常见情况下 T 不大(例如 T≤100 则 W≤10000),该复杂度可接受。
- 空间复杂度:O(W) 仅使用两个长度为 W+1 的一维数组滚动更新。
代码实现
import sys
import math
INF = 1e100
def solve(n, T, layers):
# 将浮点阈值缩放为整数容量,避免精度误差
S = 100
W = int(round(T * S + 1e-9))
dp = [INF] * (W + 1)
dp[0] = 0.0
for options in layers:
ndp = [INF] * (W + 1)
for j in range(W + 1):
if dp[j] >= INF / 2:
continue
for loss, mem in options:
w = int(round(loss * S + 1e-9))
nj = j + w
if nj <= W:
val = dp[j] + mem
if val < ndp[nj]:
ndp[nj] = val
dp = ndp
ans = min(dp)
return ans
def main():
data = sys.stdin.read().strip().split()
if not data:
return
idx = 0
n = int(data[idx]); idx += 1
T = float(data[idx]); idx += 1
layers = []
for _ in range(n):
k = int(data[idx]); idx += 1
opts = []
for _ in range(k):
_bit = data[idx]; idx += 1 # 8bit/16bit 字符串,算法不需要用到
loss = float(data[idx]); idx += 1
mem = float(data[idx]); idx += 1
opts.append((loss, mem))
layers.append(opts)
ans = solve(n, T, layers)
print(f"{ans:.2f}")
if __name__ == "__main__":
main()
#include <bits/stdc++.h>
using namespace std;
static const double INF = 1e100;
// 题目核心功能:多重选择背包,约束总loss<=T,最小化总mem
double solve(int n, double T, const vector<vector<pair<double,double>>>& layers) {
int S = 100;
int W = (int)llround(T * S + 1e-9);
vector<double> dp(W + 1, INF);
dp[0] = 0.0;
for (const auto& options : layers) {
vector<double> ndp(W + 1, INF);
for (int j = 0; j <= W; j++) {
if (dp[j] >= INF / 2) continue;
for (auto &op : options) {
double loss = op.first;
double mem = op.second;
int w = (int)llround(loss * S + 1e-9);
int nj = j + w;
if (nj <= W) {
double val = dp[j] + mem;
if (val < ndp[nj]) ndp[nj] = val;
}
}
}
dp.swap(ndp);
}
double ans = INF;
for (int j = 0; j <= W; j++) ans = min(ans, dp[j]);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
double T;
if (!(cin >> n >> T)) return 0;
vector<vector<pair<double,double>>> layers;
layers.reserve(n);
for (int i = 0; i < n; i++) {
int k;
cin >> k;
vector<pair<double,double>> opts;
opts.reserve(k);
for (int j = 0; j < k; j++) {
string bit; // 8bit/16bit 字符串,算法不使用
double loss, mem;
cin >> bit >> loss >> mem;
opts.push_back({loss, mem});
}
layers.push_back(opts);
}
double ans = solve(n, T, layers);
cout.setf(std::ios::fixed);
cout << setprecision(2) << ans << "\n";
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static final double INF = 1e100;
// 题目核心功能:多重选择背包,约束总loss<=T,最小化总mem
static double solve(int n, double T, List<double[][]> layers) {
int S = 100;
int W = (int)Math.round(T * S + 1e-9);
double[] dp = new double[W + 1];
Arrays.fill(dp, INF);
dp[0] = 0.0;
for (double[][] options : layers) {
double[] ndp = new double[W + 1];
Arrays.fill(ndp, INF);
for (int j = 0; j <= W; j++) {
if (dp[j] >= INF / 2) continue;
for (int t = 0; t < options.length; t++) {
double loss = options[t][0];
double mem = options[t][1];
int w = (int)Math.round(loss * S + 1e-9);
int nj = j + w;
if (nj <= W) {
double val = dp[j] + mem;
if (val < ndp[nj]) ndp[nj] = val;
}
}
}
dp = ndp;
}
double ans = INF;
for (int j = 0; j <= W; j++) ans = Math.min(ans, dp[j]);
return ans;
}
public static void main(String[] args) throws Exception {
// 输入规模不明确,使用 BufferedReader + StringTokenizer,简洁且足够稳定
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
List<String> tokens = new ArrayList<>();
String line;
while ((line = br.readLine()) != null) {
line = line.trim();
if (line.isEmpty()) continue;
StringTokenizer st = new StringTokenizer(line);
while (st.hasMoreTokens()) tokens.add(st.nextToken());
}
if (tokens.isEmpty()) return;
int idx = 0;
int n = Integer.parseInt(tokens.get(idx++));
double T = Double.parseDouble(tokens.get(idx++));
List<double[][]> layers = new ArrayList<>();
for (int i = 0; i < n; i++) {
int k = Integer.parseInt(tokens.get(idx++));
double[][] opts = new double[k][2];
for (int j = 0; j < k; j++) {
idx++; // 8bit/16bit 字符串,算法不使用
double loss = Double.parseDouble(tokens.get(idx++));
double mem = Double.parseDouble(tokens.get(idx++));
opts[j][0] = loss;
opts[j][1] = mem;
}
layers.add(opts);
}
double ans = solve(n, T, layers);
System.out.printf(Locale.US, "%.2f%n", ans);
}
}
题目内容
深度学习模型的推理量化问题,该模型包含多个全连接层,每个层可以选择不同的量化方案(16−bit量化、8−bit量化),不同方案会带来不同的内存占用和精度损失。
需要选择模型最优的量化方案组合,在满足总精度损失约束的前提下最小化内存占用。
本题考虑16bit,8bit量化两种场景
在给定的如下条件:
每层在不同位宽下的精度损失(如8位量化时,第i层的精度损失为lossi)
每层在不同位宽下的内存占用(如8位量化时,第i层的内存占用为memi)
模型整体的精度损失不能超过阈值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