题目重点：容量受限选最大价值，和完全背包的状态更新方向不同。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 具体物品表未给，训练items=(正整数weight,value)、非负整数capacity，允许空选。
- 每项最多一次，不要求恰好填满；负价值可跳过。
解题路线
- best[c]为已处理物品且重量≤c的最大价值。处理(weight,value)时best[c]=max(best[c],best[c−weight]+value)。
- 容量必须从大到小：读到的best[c−weight]仍是本物品加入之前的状态，因此不会再使用当前项。正序会把同项多次使用，变成完全背包。
- 如果返回物品ID，可存二维决策或不可变前驱；直接在一维DP存可变指针可能后来被覆盖导致回溯重复项。
手动走一遍
一项(2,3)，容量4，0/1最优3不是6。容量0或全部负价值返回0；如果要求恰好装满需要−∞标不可达。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def maximize(items,capacity):
if capacity<0 or any(w<=0 for w,v in items):raise ValueError("positive weights, nonnegative capacity")
best=[0]*(capacity+1)
for weight,value in items:
for room in range(capacity,weight-1,-1):best[room]=max(best[room],best[room-weight]+value)
return best[capacity]
复杂度
n物品W容量O(nW)时间/O(W)空间，是依数值W的伪多项式；不能按W二进制位长度称多项式。
易错点与追问
容易失分的边界
- weight0正值在此合同拒绝。
- 输入容量很大时O(W)内存不可承诺，需收益维度或稀疏Pareto讨论。
继续深挖
- 固定物品数量要求如何增加状态维度？
- 容量极大、物品很少时meet-in-middle有什么取舍？
