1. 课程导入与问题定义

背包问题（Knapsack Problem）是组合优化中最具代表性的问题之一：给定一组物品，每件物品有重量和价值，在背包容量上限约束下选择物品子集，使总价值最大。它的现实映射非常广——预算分配、投资组合筛选、云计算资源调度、物流装载、芯片布局中的面积与收益权衡，都可以抽象成"在有限资源下做离散选择"的结构。也正因为如此，它既是算法课的经典例题，也是评估新型计算范式（包括量子优化）能力的常用基准。

本课程的主题是量子背包问题求解与基准对比。这里有两个关键词需要先厘清：一是"量子求解"，即如何把背包问题转化为量子优化算法可处理的模型（通常是二次无约束二值优化，QUBO）并求解；二是"基准对比"，即不能只说"量子方法跑通了"，而要在同一问题实例、同一评价口径下，与经典精确算法和经典启发式算法比较解的质量、求解时间与可扩展性。缺少基准，量子求解的结果就没有意义。

问题定义与数学形式

设物品数量为 n，物品 i 的重量为 w_i、价值为 v_i，背包容量为 C。引入二值决策变量 x_i ∈ {0,1}，x_i=1 表示选中物品 i。0-1 背包问题的标准形式为：

最大化   Σ v_i · x_i
约束     Σ w_i · x_i ≤ C
         x_i ∈ {0, 1},  i = 1..n

这是一个带不等式约束的整数规划。量子优化算法（如量子退火、QAOA）通常处理的是无约束的二值二次模型，因此需要把容量约束"软化"进目标函数：引入罚项系数 P，当超重时施加惩罚。于是得到 QUBO 形式：

最小化   H(x) = -Σ v_i·x_i + P · (Σ w_i·x_i - C + s)²
其中 s 为松弛变量（可用二进制展开表示剩余容量），P 需足够大以保证可行解优于不可行解。

这一步转化是本课程的技术核心之一：罚项系数 P 取多大、松弛变量如何二进制展开、变量数如何随容量增长，直接决定了后续量子求解的规模与效果。P 太小，算法可能返回超重但"看起来价值高"的不可行解；P 太大，能量地形变得陡峭，搜索更容易陷入局部极小。

课程整体框架与学习路径

本课程共 30 章，整体按"问题建模 → 量子求解 → 基准对比 → 工程实践"的主线组织，可划分为四个阶段：

• 建模阶段：背包问题定义、QUBO 转化、罚项与松弛变量设计、小规模实例的手工推演，建立对模型结构的直觉。
• 量子求解阶段：量子退火与 QAOA 的基本原理、比特与耦合的资源映射、参数调节、采样与解码流程，理解"模型如何变成量子线路或伊辛模型"。
• 基准对比阶段：经典精确算法（动态规划、分支定界）、经典启发式（贪心、局部搜索）与量子方法的对照，统一评价指标（最优性差距、可行率、时间、规模上限），并做统计意义上的比较。
• 工程实践阶段：实例生成、实验设计、结果记录与复盘，形成可复现的求解与评测流程。

下图给出本课程的整体框架，以及"量子求解"与"基准对比"两条核心任务之间的关系：

两条核心任务的关系

需要特别强调的是，量子求解与基准对比不是先后两个独立环节，而是同一实验的两面。一个典型的对照实验应当这样组织：先生成一组规模递增的背包实例（例如 n = 8、12、16、20，重量与价值在 1～20 之间随机取值，容量取总重量的 50%），对每个实例分别用动态规划求精确最优值、用贪心求近似解、用量子退火或 QAOA 求采样解；然后统一计算"最优性差距 =（最优值 − 所得解价值）/ 最优值"、可行解比例、以及各自的求解耗时。只有在这套口径下，"量子方法在这个规模上达到了 95% 的最优性、可行率 100%"这样的结论才站得住脚。

同时要建立合理的预期：当前量子硬件受比特数、连通性和噪声限制，能处理的背包规模远小于经典动态规划（后者在容量为整数时是伪多项式时间，中等规模可精确求解）。因此本课程不预设"量子一定更快更好"，而是训练大家用可测量、可复现的方式去回答"在什么规模、什么结构、什么参数下，量子方法表现如何"。