每种物品最多选若干件多重背包若逐件展开会被巨大数量拖慢。本文沿着面试官的层层追问把数量拆成一、二、四等二进制组再复用一维零一背包Python 完整代码覆盖容量为零、数量截断和剩余组并解释为什么容量循环必须倒序。仓库有重量三、价值五的零件一百万件背包容量只有一百。把一百万件逐个展开再做零一背包显然浪费因为最多只能装三十三件。面试官真正想听的不是一句“二进制优化”而是为什么若干组能表示任意可选数量、为什么每组只能用一次以及如何先按容量截断无效库存。第一问为什么不能复制所有物品将数量 m 拆成 1、2、4、8 等组最后留下不足下一次幂的余数。例如 13 拆成 1、2、4、6。每组视为一个重量和价值都乘以组大小的新物品并做零一背包。前三组能组合出 0 到 7加入最后六件组后又能表示 6 到 13与原范围连接且覆盖全部合法数量。组数从 m 降到 O(log m)。第二问一二四为什么能覆盖数量状态dp[c]表示容量不超过 c 时的最大价值。处理一个组包(groupWeight,groupValue)时容量从 cap 倒序到 groupWeight更新dp[c]max(dp[c],dp[c-groupWeight]groupValue)。倒序保证右侧旧状态仍来自处理当前组之前因此每个组最多使用一次。若正序刚更新的 dp 会在同一轮再次被读取等价于无限使用当前组悄悄变成完全背包。第三问拆完后状态怎样定义样例容量十物品 A 重三值五最多三件拆成一件组和两件组物品 B 重四值六最多两件拆成一件组和一件余数组。最优选择是两件 A 加一件 B重量十、价值十六。三件 A 价值十五仍略小两件 B 加零件 A 会超重。测试直接断言十六并用一件数量巨大的重五物品验证先按capacity//weight截断后仍只需少数组包。第四问倒序循环防住了什么对某种物品的所有组包做零一选择时组大小的子集和覆盖 0 到有效数量的每个整数因此任何原问题选法都能映射为组包选法每个组最多选一次组合总数又不会超过原数量因此反向映射也成立。零一背包转移枚举选或不选当前组在处理完全部组后dp 恰好包含所有合法组合的最大价值。第五问数量很大还有没有意义若重量或价值为负状态语义会改变示例直接拒绝数量为零则跳过。库存一百万但容量很小时先取min(count,capacity//weight)能显著减少拆分位数。若业务要求恰好装满需要把不可达状态初始化为负无穷只保留 dp[0]0不能沿用“容量不超过”的全零初始化。返回最大价值之外还要恢复方案时可保存选择路径或使用二维状态。完整可运行代码defbounded_knapsack(capacity,items):ifcapacity0:raiseValueError(negative capacity)dp[0]*(capacity1)forweight,value,countinitems:ifweight0orvalue0orcount0:raiseValueError(invalid item)countmin(count,capacity//weight)power1whilecount0:takemin(power,count)group_w,group_vweight*take,value*takeforcinrange(capacity,group_w-1,-1):dp[c]max(dp[c],dp[c-group_w]group_v)count-take power1returndp[capacity]if__name____main__:assertbounded_knapsack(10,[(3,5,3),(4,6,2)])16assertbounded_knapsack(0,[(1,9,100)])0assertbounded_knapsack(11,[(5,7,1_000_000)])14assertbounded_knapsack(6,[(2,3,0),(3,4,2)])8print(bounded-knapsack tests passed)把组包列表与状态更新对照count先被容量截断然后每轮取 power 与剩余数量的较小值所以最后一组可以不是二的幂。容量倒序是整个实现的关键不变量。函数返回 dp[capacity]其含义是容量上限而非必须用满由于 dp 随容量不减返回最后一格就是不超过总容量的最大价值。数量为零不会进入拆分循环。什么时候改用单调队列优化二进制拆分把数量维降到对数级容易复用零一背包也便于恢复选择。若物品种类很多、容量很大C*Σlog m仍可能太慢。单调队列优化会按重量余数把容量分组把转移改写成固定窗口最大值从而让每种物品只扫描 O© 状态。它更快却要求对价值表达式做代数变形窗口边界和不可达状态都更容易出错。选择优化前应先计算有效数量。若绝大多数 count 在容量截断后只有零、一或二二进制拆分的常数小、实现清楚往往已经足够。只有当大量物品都能重复很多次且 C 成为真实瓶颈单调队列才值得引入。可以同时保留朴素小规模实现作为测试 oracle随机对照优化版本避免性能改造悄悄改变“恰好装满”或“至多容量”的语义。背包服务化时还会遇到资源上限与超时。状态数组大小由容量决定不能让调用方提交任意大整数直接分配内存。价值和重量的单位应先归一化以克和毫克混用会把容量放大一千倍。若用最大公约数缩放所有重量与容量结果保持不变且状态数下降。返回方案时对同价值结果还要约定偏好更轻、件数更少或字典序更小否则不同实现可能给出不同但同样最优的组合。优化版本必须接受朴素裁判在容量零到三十、物品种类一到五的范围随机生成数据用逐种枚举选取件数的三维朴素 DP 作为参考。二进制拆分版本与参考值必须完全相同若还实现单调队列版三者一起对照。测试集合要刻意包含数量零、重量大于容量、数量远大于可容纳数、价值相同和恰好装满不可达。性能测试另行使用大容量不能为了跑得快而删掉正确性裁判。记录拆分后的组包数可直接观察容量截断是否真正生效。进一步推导练习将容量改为十二为同一种物品设置重量三、价值五、数量十三先按容量截断再写出组包大小。分别用倒序和正序更新一轮找出正序版本如何在同一组上重复获利。然后把目标改成必须恰好装满重新初始化不可达状态。预期会看到算法骨架相似但状态含义一变初始化和返回条件都必须同步改变。复杂度分析第 i 种物品的有效数量为 mi拆成 O(log(mi1)) 个组包。每个组包扫描容量 C时间 O(C * Σlog(mi1))空间 O©。先按 C/weight 截断后mi 不会大于容量可容纳件数。若物品数量和容量都很大还可研究单调队列优化到 O(NC)但实现与证明更复杂。边界条件容量零返回零数量零跳过重量必须为正以避免无限可装示例要求价值非负有效数量被容量截断最后余数组必须保留。数值可能超过 32 位时 Python 自动扩展迁移到 Java 或 C 应使用 64 位并估算最大总价值。常见错误组大小只取一二四却忘记剩余量容量正序导致组包可重复选把 count 在拆分前错误清零没有容量截断导致无意义的大整数循环恰好装满问题仍以零初始化全部状态返回 max(dp) 虽通常相同却掩盖了 dp 定义不清。可复制的测试用例运行后预期输出bounded-knapsack tests passed。四个断言覆盖普通组合、零容量、百万库存截断和零数量物品。进一步可在小容量下用三重循环的朴素多重背包做对照随机生成重量、价值与数量逐例比较结果。上线前复核清单**状态**先写清 dp 是不超过容量还是恰好容量。**拆分**组大小之和必须等于有效数量余数组不能丢。**顺序**每个组是零一物品所以容量必须倒序。**截断**数量超过容量可容纳上限的部分永远无用。**恢复**若要输出件数方案需要额外记录选择而非只有一维价值。总结二进制拆分的价值是用对数个零一选择精确覆盖零到 m 的所有件数。理解覆盖证明和倒序更新后多重背包就不再是另一套陌生模板而是对零一背包输入规模的一次压缩。
