带负权物品的完全背包问题：凑出重量W的最少物品数求解算法

前置预处理 #

• 先做无解快速判定：
  1. 若不存在重量为正的物品，无法凑出W>0，直接返回-1
  2. 计算所有物品重量的最大公约数g，若W % g != 0，不存在符合条件的组合，直接返回-1
  3. 若不存在重量为负的物品，直接用常规完全背包求解即可

核心算法：带范围限制的最短路径搜索（BFS/SPFA） #

这个问题可以等价转化为单源最短路径问题：

• 把每一个可能的重量值看作图的节点
• 对任意重量节点u，选取任意一件物品xi，就可以到达节点u + xi，对应边权为1（物品数+1）
• 我们的目标就是找从节点0出发到节点W的最短路径长度

为了避免负重量导致的状态无限扩张，我们可以限定搜索的重量范围：
设所有物品重量的最大绝对值为A，最优解的中间重量一定落在区间[-A, W + A]内，超出这个范围的路径不可能是最优解，可以直接剪枝。

具体实现步骤 #

1. 计算偏移量offset = A，将负重量映射为非负数组索引：重量w对应数组索引为w + offset，数组总长度为W + 2*A + 1
2. 初始化距离数组dist，所有值设为无穷大，dist[0 + offset] = 0（凑重量0需要0件物品）
3. 用队列做BFS（边权全为1，BFS天然求最短路），初始将重量0入队
4. 每次取出队首重量u，遍历所有物品：
   • 计算新重量v = u + xi
   • 若v < -A或v > W + A，跳过超出范围的状态
   • 若dist[v + offset] > dist[u + offset] + 1，更新距离，将v入队
5. 遍历结束后，若dist[W + offset]还是无穷大，返回-1，否则返回dist[W + offset]

示例验证 #

以你给出的用例x1=3, x2=-1, W=2为例：

• 最大绝对值A=3，搜索范围为[-3,5]，偏移量offset=3
• 初始dist[3] = 0（对应重量0）
• 处理重量0时，得到重量3（dist[6] = 1）和重量-1（dist[2] =1）
• 处理重量3时，加-1得到重量2，dist[5] = 2，刚好对应目标重量W=2，直接返回2，和预期结果一致。

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