页面加载中…
AI017. 显存装箱
中等通过率 0% · 提交 0 · 通过 0
华为 AI 岗0-1 背包显存预算动态规划
本题改编自算法机考高频题型 · 考点：华为 AI 岗 / 0-1 背包 · 难度：中等
一台推理服务器的显存预算为 C MB。现有 n 个候选模型,第 i 个模型部署后占用显存 w_i MB,带来收益 v_i。每个模型至多部署一份,所选模型的显存占用之和不能超过 C。请输出可以获得的最大总收益。注意:w_i 可以为 0,表示该模型经过量化后几乎不占显存,可以直接部署。
这类题属于算法机考高频题型中「华为 AI 岗 / 0-1 背包」方向的高频题型，通常考察对「华为 AI 岗 / 0-1 背包」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
输入描述
第一行输入两个整数 n C。随后 n 行,每行两个整数 w_i v_i,表示一个模型的显存占用与收益。
输出描述
输出一行一个整数,表示最大总收益。
示例
示例 1
输入示例
4 10 3 4 4 5 5 6 2 3
输出示例
13
说明：
基础混合选择
示例 2
输入示例
3 5 0 7 6 9 5 4
输出示例
11
说明：
零占用模型直接部署
时间限制 2000 ms · 内存限制 256 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
⚠️ 这道题的坑 · 易错点与反直觉
这些是真正决定能不能 AC、但通用题解里常被略过的点。
- 容量维正序更新就是完全背包,同一模型会被装两次
- w=0 的模型只赚不亏直接必选;倒序循环里它也只会被加一次收益,单独累加是为表达清晰,不是防重复计费
解题思路
这道题在考什么
0-1 背包的标准形:每个模型选或不选,占用之和不超预算,收益最大化。机考 150-200 分档最爱的模型之一,考点是转移方向和边界脏活(w=0)。
数据范围读档:先算部分分的账
n ≤ 300、C ≤ 30000,O(n·C) = 9×10⁶,正解稳过。如果考场上一时想不起背包,2^n 枚举在 n 很小的用例上也能骗到部分分——华为按用例给分,先交一版暴力保底、再换正解,是 120 分到 200 分的现实路径。这道题的正解不难,直接上 DP。
状态与转移(DP 三问)
dp[c] = 预算恰好不超过 c 时的最大收益。逐个模型转移:
for w, v in models:
for c in range(C, w - 1, -1):
dp[c] = max(dp[c], dp[c - w] + v)容量维必须倒序。正序更新时 dp[c-w] 已经是「本轮用过这个模型」的值,同一模型会被装进去两次——那是完全背包(AI008 的世界)。这道题专门放了一组「正序会多算」的用例卡这个,倒序是 0-1 背包的身份证。
w = 0 的模型
占用为 0、收益非负的模型,装进去只赚不亏,直接必选。倒序循环 range(C, -1, -1) 遇到 w=0 时 dp[c] 和 dp[c-0] 是同一格,转移退化成 dp[c] = max(dp[c], dp[c] + v)——每格只会加一次 v,结果仍然正确,但这步转移已经失去「选或不选」的意义。更清晰的处理:把 w=0 的模型拎出来,收益直接累加,剩下的跑标准背包——单独处理是为了表达清晰、跳过无意义的容量转移,不是防重复计费。
复杂度
时间 O(n·C),空间 O(C) 一维滚动。答案是 dp 数组的最大值(等价于 dp[C],因为占用不超过 c 的定义是单调的)。
易错点展开
- 容量维正序:同一模型重复部署,答案偏大。
- w=0 不单独处理结果也对(每格只会加一次收益),但该转移已无「选或不选」的意义;拎出来直接累加收益,表达更清晰。
- v=0 的模型装不装无所谓,跳过省时间。
- 收益上限 300×10000 = 3×10⁶,int 够,但别用 short 之类的窄类型。
参考实现怎么读
参考实现遇到 w=0 且 v>0 的模型,直接给整条 dp 数组每格加 v(等价于必选);其余模型跑一维滚动数组,容量维从 C 倒序到 w;答案是 dp[C]。dp 长度 C+1,初值全 0——「占用不超过 c」的定义下不需要负无穷初始化,这一点和「恰好装满」的变体不同,别混。
数据范围再读一遍
n ≤ 300、C ≤ 30000,O(n·C) = 9×10⁶ 次转移,Python 也就几百毫秒。w_i 可以大于 C(装不进的模型内层循环直接空转),v_i = 0 的模型跳不跳过都对。
写完先自查这三组
1. 样例 2:w=0 收益 7 直接进账,剩余预算 5 装不下 6、装得下 5(收益 4),答案 7 + 4 = 11。 2. 单模型恰好 w = C:装得进,验证倒序循环的边界 range(C, w-1, -1) 含 w。 3. 把倒序临时改成正序跑一遍第一组样例:如果答案变大了,说明你原来的倒序是对的——用反例确认自己理解了为什么倒序。
参考代码
# 0-1 背包:dp[c]=占用不超 c 的最大收益,容量维倒序防同一模型重复部署
# w=0 的模型只赚不亏,收益单独累加,不进背包循环
import sys
def solve() -> None:
data = sys.stdin.buffer.read().split()
if not data:
return
it = iter(data)
n = int(next(it))
cap = int(next(it))
dp = [0] * (cap + 1)
for _ in range(n):
w = int(next(it))
v = int(next(it))
if v <= 0:
continue
if w == 0:
dp = [x + v for x in dp]
elif w <= cap:
old = dp[: cap + 1 - w]
dp[w:] = [b + v if b + v > a else a for a, b in zip(dp[w:], old)]
print(dp[cap])
if __name__ == "__main__":
solve()
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
