核心代码编程-多模态版本的最优调度-200分

在大语言模型推理服务中有多个不同大小的模型版本可供选择。每个模型版本有不同的准确率和推理延迟。给定查询次数N和总时间预算T为每个查询选择一个模型版本使得在不超过时间预算的前提下总准确率最大。输入查询次数N总时间预算T模型准确率 accuracy[i]模型延迟 latency[i]输出最大总准确率同一个模型可以被多次选择0查询数量N100总时间预算T1000准确率 accuracy[i]100表示多个百分点0延迟 latency[i]200模型版本数量10可以考虑采用递归方法完成必须查满N次补充说明示例1输入2,4,[80,90, 95],[1,2,3]输出 180说明最优选择为选取两个准确率为90的模型总耗时为4总准确率为180。示例2输入 2,2,[80, 90, 95],[2,2,3]输出0说明无法有效选到要求的2个模型因此总准确率为0以下是针对您提出的问题使用不同编程语言实现的解决方案。问题描述为给定查询次数 (N)、总时间预算 (T)、模型准确率数组accuracy和模型延迟数组latency需要为每个查询选择一个模型版本可重复选择在不超过时间预算 (T) 的前提下最大化总准确率。如果无法满足条件则返回 0。C 语言实现#include stdlib.h #include limits.h int maxAccuracy(int N, int T, int* accuracy, int* latency, int M) { int** dp (int**)malloc((N 1) * sizeof(int*)); for (int i 0; i N; i) { dp[i] (int*)malloc((T 1) * sizeof(int)); for (int j 0; j T; j) { dp[i][j] -1; } } for (int t 0; t T; t) { dp[0][t] 0; } for (int k 1; k N; k) { for (int t 0; t T; t) { int bestVal -1; for (int m 0; m M; m) { int l latency[m]; int a accuracy[m]; if (t l) { int prevT t - l; if (dp[k - 1][prevT] ! -1) { int candidate dp[k - 1][prevT] a; if (candidate bestVal) { bestVal candidate; } } } } dp[k][t] bestVal; } } int maxAcc -1; for (int t 0; t T; t) { if (dp[N][t] maxAcc) { maxAcc dp[N][t]; } } for (int i 0; i N; i) { free(dp[i]); } free(dp); return (maxAcc -1) ? 0 : maxAcc; }C 语言实现#include vector #include algorithm #include climits int maxAccuracy(int N, int T, std::vectorint accuracy, std::vectorint latency) { int M accuracy.size(); std::vectorstd::vectorint dp(N 1, std::vectorint(T 1, -1)); for (int t 0; t T; t) { dp[0][t] 0; } for (int k 1; k N; k) { for (int t 0; t T; t) { int bestVal -1; for (int m 0; m M; m) { int l latency[m]; int a accuracy[m]; if (t l) { int prevT t - l; if (dp[k - 1][prevT] ! -1) { int candidate dp[k - 1][prevT] a; if (candidate bestVal) { bestVal candidate; } } } } dp[k][t] bestVal; } } int maxAcc -1; for (int t 0; t T; t) { if (dp[N][t] maxAcc) { maxAcc dp[N][t]; } } return (maxAcc -1) ? 0 : maxAcc; }JavaScript 语言实现function maxAccuracy(N, T, accuracy, latency) { const M accuracy.length; const dp Array.from({ length: N 1 }, () Array(T 1).fill(-1)); for (let t 0; t T; t) { dp[0][t] 0; } for (let k 1; k N; k) { for (let t 0; t T; t) { let bestVal -1; for (let m 0; m M; m) { const l latency[m]; const a accuracy[m]; if (t l) { const prevT t - l; if (dp[k - 1][prevT] ! -1) { const candidate dp[k - 1][prevT] a; if (candidate bestVal) { bestVal candidate; } } } } dp[k][t] bestVal; } } let maxAcc -1; for (let t 0; t T; t) { if (dp[N][t] maxAcc) { maxAcc dp[N][t]; } } return maxAcc -1 ? 0 : maxAcc; }Java 语言实现public class ModelSelector { public static int maxAccuracy(int N, int T, int[] accuracy, int[] latency) { int M accuracy.length; int[][] dp new int[N 1][T 1]; for (int k 0; k N; k) { for (int t 0; t T; t) { dp[k][t] -1; } } for (int t 0; t T; t) { dp[0][t] 0; } for (int k 1; k N; k) { for (int t 0; t T; t) { int bestVal -1; for (int m 0; m M; m) { int l latency[m]; int a accuracy[m]; if (t l) { int prevT t - l; if (dp[k - 1][prevT] ! -1) { int candidate dp[k - 1][prevT] a; if (candidate bestVal) { bestVal candidate; } } } } dp[k][t] bestVal; } } int maxAcc -1; for (int t 0; t T; t) { if (dp[N][t] maxAcc) { maxAcc dp[N][t]; } } return (maxAcc -1) ? 0 : maxAcc; } }Go 语言实现package main func maxAccuracy(N int, T int, accuracy []int, latency []int) int { M : len(accuracy) dp : make([][]int, N1) for i : range dp { dp[i] make([]int, T1) for j : range dp[i] { dp[i][j] -1 } } for t : 0; t T; t { dp[0][t] 0 } for k : 1; k N; k { for t : 0; t T; t { bestVal : -1 for m : 0; m M; m { l : latency[m] a : accuracy[m] if t l { prevT : t - l if dp[k-1][prevT] ! -1 { candidate : dp[k-1][prevT] a if candidate bestVal { bestVal candidate } } } } dp[k][t] bestVal } } maxAcc : -1 for t : 0; t T; t { if dp[N][t] maxAcc { maxAcc dp[N][t] } } if maxAcc -1 { return 0 } return maxAcc }Python 语言实现def max_accuracy(N, T, accuracy, latency): M len(accuracy) dp [[-1] * (T 1) for _ in range(N 1)] for t in range(T 1): dp[0][t] 0 for k in range(1, N 1): for t in range(T 1): best_val -1 for m in range(M): l latency[m] a accuracy[m] if t l: prev_t t - l if dp[k - 1][prev_t] ! -1: candidate dp[k - 1][prev_t] a if candidate best_val: best_val candidate dp[k][t] best_val max_acc -1 for t in range(T 1): if dp[N][t] max_acc: max_acc dp[N][t] return 0 if max_acc -1 else max_acc算法说明以上代码均使用动态规划解决该问题创建一个二维数组dp[k][t]表示选择k个查询且总时间不超过t时的最大总准确率。初始化dp[0][t] 00 个查询时准确率为 0。对于每个查询数量k从 1 到 (N)每个时间t从 0 到 (T)遍历所有模型版本如果当前时间t大于等于模型延迟latency[m]且前一个状态dp[k-1][t - latency[m]]有效不为 -1则计算候选值dp[k-1][t - latency[m]] accuracy[m]。更新dp[k][t]为所有候选值中的最大值。最终在dp[N][t](t \leq T)) 中寻找最大值如果所有值均为 -1不可能则返回 0。该算法时间复杂度为 (O(N \times T \times M))空间复杂度为 (O(N \times T))符合问题约束(N \leq 100), (T 1000), (M \leq 10)。