面试题库 › 游戏开发 › 0-1 背包问题的实现与复杂度分析

0-1 背包问题的实现与复杂度分析

难度 ★★☆在 1 场真实面经中被问到 方向:游戏开发考点:动态规划

哪些公司问过

网易1

常见岗位:游戏服务端

答案要点

  1. 状态:dp[i][j] 为前 i 件物品、容量 j 时的最大价值
  2. 转移:dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]] + v[i]),需 j ≥ w[i]
  3. 时间 O(nW),二维空间 O(nW),一维滚动数组 O(W)
  4. 一维时容量必须倒序遍历,保证每件物品只用一次;正序即完全背包
  5. O(nW) 为伪多项式,容量很大时需考虑其他方法

易错点

面试官常见追问

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

相关面试题