会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
核心思路：把每个任务维度看成一「组」物品，组内候选适配器互斥（至多启用一个），整组也可以不启用；显存预算 M 相当于背包容量，能力提升分为价值。这是分组背包：按维度逐组处理，设 fi[j] 为处理完前 i 个维度、占用显存不超过 j 时的最大提升分。对第 i 组，先保留「整组不启用」的继承值 fi−1[j]，再对组内每个候选 (w,v) 用组前状态做转移 fi[j]=max(fi[j],fi−1[j−w]+v)。转移必须读取上一组的数组而非本组已更新的数组，否则会退化为同组多选，破坏互斥约束。
实现方法：滚动数组。每组开始前复制一份组前状态 pre，组内每个候选从 pre[j-w] 转移更新 f[j]；容量维度无需逆序，因为读取的是 pre（冻结副本）。w>M 的候选直接跳过。全负 / 全不选情形由 f 初始为 0 自然覆盖。也可写成自顶向下的记忆化搜索 dfs(i, 剩余显存)：不启用本组继承 dfs(i+1, cap)，再枚举组内每个候选 dfs(i+1, cap-w) + v 取最大，两者答案一致。
复杂度分析
时间复杂度 O(M×∑ki)：每组每个候选扫描全部容量档。取上限 M=500、∑ki=1000 时约 5×105 次转移，Python 记忆化搜索实测最坏约 60 毫秒，远低于时限。空间复杂度 O(M)，两个滚动数组（记忆化搜索为 O(N×M) 状态数）。
