软考笔记

Appearance

难度基础（★）
建议时长45分钟

15.2.7 背包问题（回溯法） ​

回溯法解决 0-1 背包时，把每个物品都看成一次二选一决策：选，或者不选。所有决策组合构成一棵解空间树。算法从根结点出发做深度优先搜索，遇到不可能产生更好解的分支就剪掉，搜索不下去时再回退。

0-1 背包的搜索树 ​

对于第 k 个物品：

  • 左分支通常表示选第 k 个物品，记为 xk=1。
  • 右分支通常表示不选第 k 个物品，记为 xk=0。

若有 n 个物品，不剪枝时最多有 2n 种选择组合。

mermaid
flowchart TD
  R["开始"] --> A["x1=1"]
  R --> B["x1=0"]
  A --> C["x2=1"]
  A --> D["x2=0"]
  B --> E["x2=1"]
  B --> F["x2=0"]
  C --> G["继续到 x3..."]
  D --> H["继续到 x3..."]

这就是回溯法复杂度可能很高的原因：它本质上在系统枚举组合，只是通过约束和限界减少无意义分支。

变量在代码中的含义 ​

字幕里的伪代码和 C 代码围绕这些变量展开：

变量含义
W背包总容量
n物品个数
w[]重量数组
v[]价值数组
cw当前背包重量
cp当前已获得价值
fw当前最优方案对应的重量
fp当前已找到的最大价值
k当前考虑的物品编号
y[]当前部分解
x[]当前最优解

代码填空时先不要急着猜语法，要把变量意义翻译回来：如果选了物品，就应更新 cw、cp、y[k]；如果回退，就应撤销这些更新。

约束函数与限界函数 ​

回溯法的剪枝有两类。

剪枝类型判断问题背包中的例子
约束剪枝当前方案是否已经不合法？cw + w[k] > W，超过容量不能选
限界剪枝当前分支是否还有希望超过最优解？估计最大可能价值 bound(...) <= fp，继续搜索也没用

限界函数的思想是“乐观估计”。它估计从当前结点继续扩展，理论上最多还能得到多少价值。如果这个上界都不超过当前最优值 fp，那该分支不可能产生更好解，可以直接剪掉。

回溯的动作：选、深入、撤销 ​

一段典型逻辑可以抽象成：

c
if (cw + w[k] <= W) {
    y[k] = 1;
    cw += w[k];
    cp += v[k];
    search(k + 1);
    cp -= v[k];
    cw -= w[k];
    y[k] = 0;
}

y[k] = 0;
search(k + 1);

这里最重要的是“撤销”。如果选了第 k 个物品后继续探索，返回上一层时必须把重量、价值、选择标记恢复，否则会污染右分支或其他兄弟分支。

伪代码填空的常见答案来源 ​

字幕中提到，早年真题可能给伪代码。伪代码没有严格语法标准，但上下文会给出逻辑。

缺失位置推理方式常见填法
k 初值物品编号从 1 开始，循环到 nk = 1
放入物品后的重量更新已有 cp = cp + v[k]，重量要同步cw = cw + w[k]
继续探索下一件当前物品处理完k = k + 1
回退到上一层回溯核心动作k = k - 1
撤销选择选中标记和累计值恢复y[k]=0; cw-=w[k]; cp-=v[k]

如果题干数组从 0 开始，初值和边界要相应变成 k=0、k<n 等。考试答案必须服从题干的编号约定。

搜索结果怎么读 ​

题目可能要求根据搜索树判断最优解。读树时要看：

  • 边上的 1/0 表示该层物品是否选择。
  • 结点旁的重量/价值表示当前部分解。
  • 旁边的上界值表示继续扩展最多可能得到的价值。
  • 若某结点上界不超过当前最优值，就不会继续扩展。

课程例子中，某些分支可能得到方案 100、011 之类。100 表示选第 1 个、不选第 2 和第 3 个；011 表示不选第 1 个、选第 2 和第 3 个。比较它们时必须同时满足容量约束，再看价值大小。

回溯法的优劣势 ​

优点缺点为什么还要学
能系统搜索解空间，不容易漏解最坏接近 O(2n)下午题常用它考“探索、剪枝、回退”
剪枝后可减少大量无效分支限界函数设计需要经验代码填空常围绕约束和回退
能输出最优方案本身大规模时不如动态规划稳定适合理解 0-1 选择结构
单选
0-1 背包回溯搜索中，若当前重量已经超过背包容量，应如何处理？

本节小结 ​

回溯法是“选、试、剪、退”。在 0-1 背包中，每层对应一个物品，每个分支对应选或不选。代码填空最常考累计重量/价值、k 的前进与回退、最优解更新和限界剪枝。