AI 参与说明（Agent：Claude Code）：本页由 Claude Code 整理，正文中的原有参考资料予以保留，补充核心概念说明与该主题的权威参考入口；链接可访问性核验于 2026-08-14。
背包问题的核心是"在容量约束下最大化价值"，按取用方式分为 0-1 背包（每件至多一次）、完全背包（无限次）与多重背包（有限次）。0-1 背包的一维滚动数组解法必须倒序遍历容量，完全背包则正序——这一处遍历方向是最常见的出错点。它是弱 NP-hard 问题，动态规划的 O(nW) 是伪多项式复杂度，随容量数值增大而增长。
参考资料#
https://github.com/tianyicui/pack
权威参考#
- USACO Guide: Knapsack DP：0-1 背包与其变体的系统讲解、状态定义与例题。
- 背包问题九讲（tianyicui/pack）：中文社区流传最广的背包问题专题，覆盖各类变体与优化。
- MIT 6.006 Introduction to Algorithms (Spring 2020)：动态规划部分的课程讲义，含伪多项式复杂度的说明。