2. 经典背包问题回顾

在进入量子算法之前，必须先有一个“标准答案”的参照系。0-1背包问题之所以成为量子优化算法最常用的基准测试对象，正是因为它同时具备三个特征：组合爆炸、约束清晰、经典最优解可精确计算。本节将系统回顾其数学模型、动态规划解法与分支限界法，并给出复杂度分析，为后续量子求解方案提供可对比的基准。

一、0-1背包问题的数学模型

给定 n 件物品，第 i 件物品重量为 w_i、价值为 v_i，背包容量为 W。每件物品只有“装入”或“不装入”两种状态，用决策变量 x_i ∈ {0,1} 表示。目标是最大化总价值，同时总重量不超过容量：

maximize   Σ(i=1..n) v_i · x_i
subject to Σ(i=1..n) w_i · x_i ≤ W
           x_i ∈ {0, 1},  i = 1..n

这是一个带线性约束的整数规划问题。其可行解空间大小为 2ⁿ，当 n = 50 时约为 10¹⁵，穷举不可行。值得注意的是，0-1背包问题具有“最优子结构”和“重叠子问题”两个性质，这正是动态规划能够高效求解的根本原因；而它的约束结构又使其天然适合映射为量子优化中的伊辛模型或 QUBO 形式。

二、动态规划解法

动态规划的核心思想是：用二维状态表记录“前 i 件物品、容量为 j 时的最大价值”。定义 dp[i][j] 表示从前 i 件物品中选取、总重量不超过 j 的最大价值，则状态转移方程为：

dp[i][j] = dp[i-1][j]                             若 w_i > j
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_i] + v_i)  若 w_i ≤ j

边界条件为 dp[0][j] = 0。最终答案为 dp[n][W]。以 4 件物品、容量 5 为例：物品重量 [2,3,1,2]、价值 [3,4,2,3]，逐行填表后可得最优值为 8（选取物品1、3、4，总重 5）。

该算法的时间复杂度为 O(nW)，空间复杂度经滚动数组优化后可降为 O(W)。这里有一个关键点：O(nW) 是伪多项式复杂度——当 W 的数值随输入位数指数增长时（例如容量为 2^k 量级），算法实际耗时仍会爆炸。因此动态规划并非在所有情形下都“高效”，它依赖容量数值本身不太大。这一点在构造量子对比基准时必须明确说明，否则容易得出不公平的结论。

三、分支限界法

分支限界法通过系统枚举解空间树并剪枝来寻找最优解。常用策略是“按单位价值降序排序 + 上界估计”：将物品按 v_i/w_i 从大到小排列，在搜索树的每个节点计算当前已选价值加上“剩余容量按分数背包松弛得到的最大可能价值”作为上界。若某节点的上界不超过当前已知最优解，则整棵子树被剪掉。

以同样的 4 件物品为例，单位价值分别为 1.5、1.33、2.0、1.5，排序后优先探索高性价比物品。分支限界法在最好情况下接近 O(n log n)，最坏情况仍为 O(2ⁿ)，属于指数级算法，但其实际表现通常远优于穷举，是中小规模精确求解的常用手段。

四、复杂度分析与基准设定

三种方法的复杂度对比如下：

建立量子对比基准时，需要固定三类参数：问题规模 n、容量 W、物品重量与价值的分布（如均匀随机或强相关）。建议采用“小规模精确校验 + 中规模性能对比”的两级策略：在 n ≤ 20 时用动态规划给出精确最优值，验证量子算法输出是否正确；在 n = 30～50 时记录经典 DP 与分支限界的实际耗时，作为量子加速比的参照分母。同时应明确记录 DP 的伪多项式特性——若 W 取值极大，DP 耗时会显著上升，此时对比结论需单独说明，避免把“容量数值小”误读为“经典算法天然快”。