0/k背包问题如何求解：从0/1背包延伸的O(nKS)实现方法

统一的状态定义基础 #

所有经典背包问题的状态设计可以完全对齐你已经掌握的0/1背包逻辑，不存在本质的认知跳跃：

• 统一采用二维状态dp[i][s]，代表考虑前i种物品、背包总承重为s时，能够获取的最大价值
• 三类经典背包的核心差异仅在于单种物品的可选数量上限：
  • 0/1背包是单种物品最多选1个（k=1）的特例
  • 完全（0/inf）背包是单种物品可选数量超过背包容量可容纳上限的特例
  • 0/k背包是单种物品最多选k个的通用场景

O(nKS)复杂度的无优化基础实现 #

这个版本是完全从0/1背包的转移逻辑自然延伸出来的，没有引入任何二进制拆分、单调队列这类优化技巧，是最贴合入门阶段认知的实现：

• 转移逻辑完全承接0/1背包的分支判断框架，仅拓展枚举范围：
  • 不选第i种物品的分支：价值直接继承上一层状态dp[i-1][s]，和0/1背包的逻辑完全一致
  • 选择若干个第i种物品的分支：从选1个开始枚举，一直枚举到最多选k个的上限，只要当前剩余容量足够装下t个物品（t的取值范围为1到k），就计算对应的价值dp[i-1][s - t*w[i]] + t*v[i]
• 最终状态转移方程为：

  dp[i][s] = max( dp[i-1][s], max_{t=1到min(k, s//w[i])} ( dp[i-1][s - t*w[i]] + t*v[i] ) )

• 复杂度匹配：遍历n种物品、每种物品遍历所有S个承重档位、每个档位最多枚举k个可选的选择数量，总运算量恰好为O(nKS)，就是要找的基础版本

和已掌握知识点的交叉验证 #

这个朴素实现可以完全覆盖已经学过的两类背包场景，不存在逻辑偏差：

• 当k=1时，枚举的t值只有1个，方程直接退化为标准0/1背包的转移逻辑
• 当k大于背包最多能装下的单种物品数量（即k > S//w[i]）时，枚举的t值已经覆盖了所有可能的选择上限，计算结果和完全背包完全等价

为什么公开资料很少提及这个基础版本 #

• 这个朴素实现没有任何效率优化，实际编码场景中大家通常会直接使用更高效的二进制拆分、单调队列等优化方案，因此多数教程会直接跳过朴素实现的讲解，重点放在优化思路上
• 多数内容创作者默认读者已经可以自行从0/1背包的枚举逻辑延伸到“枚举选多个”的思路，因此没有特意把从k=1到k个的推导过程单独拆解出来，容易让刚建立DP解题直觉的人觉得学习内容存在断层

内容的提问来源于stack exchange，提问作者Pulkit Joshi