完全背包：物品可重复，正序更新接纳当前项

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练正整数重量、整数价值、非负容量，物品可用任意份，允许不装满。
• 零重正价值会让最优无界，示例直接拒绝所有非正重量。

解题路线

1. 状态仍是容量以内最大价值，处理当前物品时容量从weight到W正序。best[c−weight]已经允许当前项，因此加当前项后能重复使用。
2. 每个可行组合最后由当前物品若干份与之前类型组合构成，正序递推覆盖所有份数；不需另枚举quantity。
3. 与0/1唯一核心差异是次数合同，而不是变量名字；返回份数时需有相应重构状态，最优价值相同不意味物品组合唯一。

手动走一遍

(2,3)容量4能取2份得到6；容量5仍6，剩1空闲。(3,5),(4,6)容量6选两份3得10，而非一份4得6。

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(weight,capacity+1):best[room]=max(best[room],best[room-weight]+value)
    return best[capacity]

复杂度

O(nW)时间/O(W)空间，伪多项式；较大容量或特殊收益结构需另讨论。

易错点与追问

容易失分的边界

• 逆序会把每项限制一份。
• 要求exact fill却用全零初始化，会错误允许不满。

继续深挖

• 多重背包上限q时怎样二进制拆分或单调队列优化？
• 树形依赖背包需要哪种父子选择合同才能写递推？