15.2.5 背包问题概述

背包问题是一类容量受限的选择问题：有若干物品，每个物品有重量和价值；背包容量有限，目标是在不超过容量的前提下，让装入物品的总价值尽可能大。

下午算法题先怎么读

课程开头先讲了软件设计师下午题的形态。算法应用题一般不是让你完整发明算法，而是给你一段题干、变量说明和 C 语言代码，让你补关键空。

题目组成	作用	读题方法
自然语言描述	说明问题背景和算法过程	先圈出“可分割/不可分割”“最优/满意”“回退/递推”等关键词
变量说明	告诉数组、变量、边界含义	代码填空时优先回到这里查变量意义
C 语言代码/伪代码	给出算法骨架	看循环边界、递归调用、数组初始化、返回值
问题	代码填空、策略判断、复杂度、实例结果	先拿策略和复杂度，再做代码细节

备考目标可以务实一些：算法题总分 15 分，策略判断、复杂度判断和基础代码填空往往能构成 6 到 8 分的核心得分区。

背包模型的形式化描述

假设有 $n$ 个物品，第 $i$ 个物品的价值为 $v_i$，重量为 $w_i$，背包容量为 $W$。通常有：

$$v_i\ge 0,w_i\ge 0,W\ge 0$$

如果用 $x_i$ 表示第 $i$ 个物品是否放入背包，那么 0-1 背包可以写成：

$$max\sum _{i=1}^n{v}_i{x}_i$$

约束条件是：

$$\sum _{i=1}^n{w}_i{x}_i\le W,x_i\in \{0,1\}$$

这里 $x_i=1$ 表示选第 $i$ 个物品，$x_i=0$ 表示不选。满足容量约束的选择方案叫可行解；可行解中总价值最大的方案叫最优解。

两类最重要的背包

类型	物品能否拆分	决策变量	典型策略	关键差异
部分背包	可以拆分	$0\le x_i\le 1$	贪心法	最后一件可取一部分
0-1 背包	不可拆分	$x_i\in \{0,1\}$	回溯法、动态规划法	每件物品只有选/不选

部分背包像装沙子、粮食、液体或可以切割的材料。若剩余容量不够，可以取一部分继续填满。0-1 背包像装衣服、电脑、书本，不能为了凑容量把一件物品切开。

三种策略如何理解

课程用同一个背包问题串联三种策略，这样最容易看出差异。

策略	在背包问题中的行为	适合解决什么
贪心法	每一步按当前最优规则选物品，例如单位价值最高	部分背包、装箱问题中的近似/满意方案
回溯法	对每件物品试“选/不选”，不合适就退回	0-1 背包的搜索与剪枝
动态规划法	用状态表记录“前 $i$ 件物品、容量 $j$ 的最大价值”	0-1 背包的最优值

flowchart LR
  A["背包问题"] --> B{"物品可拆分?"}
  B -- 是 --> C["部分背包: 单位价值贪心"]
  B -- 否 --> D["0-1 背包"]
  D --> E["回溯: 搜索所有可行方案并剪枝"]
  D --> F["动态规划: 用状态表求最优值"]

为什么 0-1 背包不能随便贪心

部分背包按单位价值选能保证最优，因为最后放不下时可以切一部分，容量不会被“浪费”。0-1 背包不同：某个物品单位价值高，但放进去后可能占掉关键容量，导致几个组合价值更高的物品放不进。

一个简单反例：

物品	重量	价值	单位价值
A	10	60	6
B	20	100	5
C	30	120	4

背包容量为 50。若按单位价值贪心，会选 A 和 B，总价值 160；但最优方案是 B 和 C，总价值 220。这个例子说明：0-1 背包有最优子结构，但仅凭“当前单位价值最大”不能保证全局最优。

代码填空的通用抓手

代码现象	可能考点
变量未初始化	补 i=0、k=1、max=... 等初值
循环条件缺失	看数组下标范围和题干是否从 0 或 1 开始
max、min 变量	补比较条件和更新语句
递推式旁边缺空	按题干公式翻译成代码
回溯代码缺空	补 k--、撤销重量/价值、恢复选择标记
分治代码左右对称	参考另一半递归调用或边界写法

本节小结

背包问题的核心是“容量约束下最大化价值”。部分背包因为可拆分，单位价值贪心成立；0-1 背包因为不可拆分，通常要用回溯搜索或动态规划求最优。下午题中，读懂题干和变量说明比死背代码更重要。

单选

每件物品要么完整装入背包，要么完全不装入，不能取一部分。这描述的是哪类问题？

A部分背包B0-1 背包C计数排序D二分查找