面试题库 › 算法 / 大模型 › 0-1 背包问题及下标不相邻变体

0-1 背包问题及下标不相邻变体

难度 ★★☆在 2 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

蔚来1中智行1

常见岗位:人工智能

答案要点

  1. 状态 dp[i][c]:前 i 件物品、容量 c 的最大价值
  2. 转移:dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])
  3. 一维优化 dp[c] = max(dp[c], dp[c-w]+v),容量需逆序遍历
  4. 初始化:不要求装满时全 0;要求恰好装满时非零容量初始化为负无穷
  5. 不相邻变体:选 i 时从 dp[i-2] 转移,或用选/不选两维状态

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题