Knapsack Problem
定义 Definition
“背包问题”：一种经典的组合优化与动态规划问题——给定一组物品（每件有重量/体积与价值），在容量限制内选择物品，使总价值最大（常见形式有 0/1 背包、完全背包、分数背包等）。
发音 Pronunciation (IPA)
/ˈnæpˌsæk ˈprɑːbləm/
例句 Examples
The knapsack problem is a classic example in dynamic programming.
背包问题是动态规划中的经典例题。
Researchers use the knapsack problem to model resource allocation when capacity is limited and trade-offs are unavoidable.
当容量受限且必须权衡取舍时，研究人员常用背包问题来建模资源分配。
词源 Etymology
“knapsack”原指“背包/行囊”（knap- 与古义“装载、携带”相关，sack 为“袋子”之意），而“knapsack problem”作为术语在 20 世纪的运筹学与计算机科学中流行起来，用“背包容量有限”来形象表达“在约束下选取组合以最大化收益”的抽象数学问题。
相关词 Related Words
文学与名著作品 Literary Works
- Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：以背包问题讲解动态规划与算法设计思想。
- The Art of Computer Programming, Volume 1: Fundamental Algorithms（Donald E. Knuth）：在组合问题与算法讨论中提及相关模型与思想。
- “On the history of the knapsack problem”（Silvano Martello & Paolo Toth 等相关综述/著作脉络）：回顾背包问题在运筹学与优化领域的发展与变体。
- Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：将背包及相关问题置于 NP-完全性与计算复杂性框架中讨论。
Select Language