15.3　经典题型：背包与最长递增子序列

学习目标：学完本节，你能

• 写出 0/1 背包的二维写法和一维写法，并说清它们为什么等价；
• 解释一维写法为什么必须逆序遍历 —— 以及写成正序会得到什么；
• 说清 0/1 背包与完全背包的区别，以及它如何体现在一个循环的方向上；
• 实现 LIS 的 $O(n^2)$ 与 $O(n\log n)$ 两种解法，并说清后者的状态定义。

先修：15.2（状态定义、转移方程）、14.3（0/1 背包的贪心为什么失效）。 固定术语：状态转移方程、动态规划、0/1 背包、分数背包、最长递增子序列。 环境与版本：.NET 8 / C# 12。 预计阅读：40 分钟。

一、直觉：两道题，一个共同点

本节上两个真正的经典题：

它们的共同点是：都能用一句话说清的转移方程，但都有一个"不写出来就会踩"的细节：

• 背包的细节是【遍历方向】 —— 逆序还是正序，决定了解的是哪道题
• LIS 的细节是【状态定义】 —— 定义换了，复杂度就从 $O(n^2)$ 掉到 $O(n\log n)$

这两个细节，正是本节的全部内容。

二、0/1 背包：从二维到一维

问题回顾（14.3 节）：容量固定，每件物品要么整个拿走、要么不拿，求最大总价值。

第一步：定义状态

用 15.2 节的四问过一遍：

$dp[i][c]$ = 只考虑前 $i$ 件物品，背包容量为 $c$ 时，能装下的最大价值

• 够吗？ "考虑前几件"和"还剩多少容量"决定了后续的一切 ✓
• 多吗？ 每个 $(i, c)$ 对应一个真实局面 ✓
• 算得动吗？ $(n+1) \times (cap+1)$ 个格子 ✓
• 转移只看它吗？ 是 —— 不需要知道"前面具体拿了哪几件" ✓

第二步：枚举最后一步

第 $i$ 件物品，只有两种可能：

• 不拿它 → 那就只能在前 $i-1$ 件里做文章，容量不变 → $dp[i-1][c]$
• 拿它 → 先扣掉它的重量，再在前 $i-1$ 件里做文章 → $dp[i-1][c - w_i] + v_i$

$$dp[i][c] = \max\Big(dp[i-1][c],\ \ dp[i-1][c - w_i] + v_i\Big)$$

代码：

for (int i = 1; i <= n; i++)
    for (int c = 0; c <= cap; c++)
    {
        dp[i, c] = dp[i - 1, c];                                   // 不拿第 i 件
        if (c >= w[i - 1])
            dp[i, c] = Math.Max(dp[i, c], dp[i - 1, c - w[i - 1]] + v[i - 1]);   // 拿
    }

第三步：压成一维

看那个转移方程：dp[i][c] 只依赖 dp[i-1][...] —— 也就是"上一行"。

既然只用上一行，那还需要存整张表吗？

不需要 —— 一个长度为 $cap+1$ 的一维数组，边算边覆盖就行。

但这里有个陷阱：覆盖的方向。

for (int i = 0; i < w.Length; i++)
    for (int c = cap; c >= w[i]; c--)              // ★ 逆序
        dp[c] = Math.Max(dp[c], dp[c - w[i]] + v[i]);

为什么必须逆序？下一节用实测回答。

三、实测一：正序会错成什么样

把上面那个循环的方向换成正序，其他一个字不改：

  数据：容量 10，物品 X(重3, 值5)、Y(重7, 值9)

    实现                                 结果
    --------------------------------    --------
    二维 dp[i][c]                        14
    一维 dp[c]，容量【逆序】遍历          14
    一维 dp[c]，容量【正序】遍历          15   <- 错！
    暴力枚举所有子集（真值）              14

  逆序版对不对：True；正序版对不对：False

正序版多算了 1。为什么？

看这两行代码在 c 上的差别：

关键在最后一句：正序时，dp[c-w] 里可能已经包含了一件第 $i$ 件物品 —— 再让它加上 $v_i$，就等于【同一个物品被拿了两次】。

用具体数字走一遍（物品 X：重 3、值 5；容量 10）：

  正序（错）：c 从 3 走到 10
    dp[3]  = max(0, dp[0] + 5) = 5      ← 拿了 1 个 X
    dp[6]  = max(0, dp[3] + 5) = 10     ← dp[3] 里已经有 X 了，又加一个  → 拿了 2 个 X
    dp[9]  = max(0, dp[6] + 5) = 15     ← 又加一个                        → 拿了 3 个 X
  最终 dp[10] = 15（3 个 X 重 9）

  逆序（对）：c 从 10 走到 3
    dp[10] = max(0, dp[7] + 5)          ← dp[7] 是上一轮的，还没有 X
    ...
    dp[3]  = max(0, dp[0] + 5) = 5
  最终 dp[10] = 14（X + Y）

正序版在 dp[3] 里放了一个 X，然后 dp[6] 又"基于含 X 的 dp[3]"再加了一个 X —— 这就是重复拿。

错得有多频繁？

  2000 组随机数据（3~10 件物品，容量 8~40）：

    一维【逆序】版： 2000 / 2000 组正确（100.0%）
    一维【正序】版：   67 / 2000 组正确（3.4%）

逆序 100%，正序只有 3.4%。

而且错的方向是固定的：正序版的答案只会【变大】 —— 因为完全背包的约束更松，能塞得更满。它绝不会给出一个偏小的值。

这反而更危险：一个"只会偏大"的结果，看起来像是"优化得更好"。

四、完全背包：逆序与正序是两道不同的题

现在把问题本身改掉：

完全背包：每种物品可以拿任意多件（不是"要么拿一个、要么不拿"）。

实测：

    完全背包（一维，容量【正序】遍历）    15
    暴力枚举所有取法（真值）              15

同一份正序代码，在这里是正确的。

把两件事放在一起看：

代码	在 0/1 背包上	在完全背包上
一维 + 逆序	✅ 正确	❌ 错（少拿了）
一维 + 正序	❌ 错（多拿了）	✅ 正确

所以"逆序"和"正序"不是"哪种更快"的问题 —— 它们是两道不同的题。

为什么会这样？一句话：

继续实测验证这个说法：

  验证：把「正序版」当成完全背包的解法，2000 组随机数据上正确 2000 组（100.0%）

100% ✓ —— 那份"写错了的 0/1 背包代码"，恰好是一份完全正确的完全背包代码。

这也解释了一个常见的困惑：

很多人第一次学背包时会想："0/1 背包和完全背包的代码长得几乎一样，为什么一个要逆序一个要正序？"

答案不是"记口诀"，而是：内层循环的方向，本身就在表达"这件物品还能不能再用"。

你写的是逆序，代码读作"只能用一次"；你写的是正序，代码读作"可以反复用"。

五、LIS：从 $O(n^2)$ 到 $O(n\log n)$

15.2 节用 LIS 演示了"状态定义差一个词"，那里给的是 $O(n^2)$ 的解法：

$$dp[i] = \max_{\substack{j < i \ a_j < a_i}} dp[j] + 1$$

15.2 练习 15.2.5 预告了另一种状态定义，能把复杂度降到 $O(n\log n)$。现在把它实现出来。

换一个状态：不看"以谁结尾"，看"结尾最小是多少"

$tails[k]$ = 所有长度为 $k+1$ 的递增子序列中，结尾最小的那个值

为什么这个状态够用？ 回到 15.2 的第一问（"它够吗"）：

对于同一个长度，我们只需要保留结尾最小的那个 —— 因为结尾越小，后面能接上的数就越多，它在任何情况下都不会比别的差。

这就是"状态压缩"：同一规模下有多个局面时，如果其中一个支配了其余所有，就只留它一个。

tails 是递增的，所以能二分

15.2 练习 15.2.5(b) 已经证过：$tails[0] < tails[1] < \dots$（严格递增）。

于是每一步只需要：

foreach (int x in a)
{
    int pos = tails.BinarySearch(x);
    if (pos < 0) pos = ~pos;            // 没找到：~pos 是第一个大于 x 的位置
    if (pos == tails.Count) tails.Add(x);   // 比所有结尾都大 -> 增长度
    else tails[pos] = x;                    // 否则：把这个长度的结尾改小
}

最后 tails.Count 就是 LIS 的长度。

注意最后一行是"替换"而不是"插入" —— 这就是"把结尾改小"，让后面更容易接上。

实测

  样例：[10, 9, 2, 5, 3, 7, 101, 18]
    O(n^2) 解法    ：4
    O(n log n) 解法：4（tails = [2, 3, 7, 18]）

  2000 组随机数组：两种解法结果不一致的组数 = 0

看 tails = [2, 3, 7, 18]：

长度 4 ✓ 和 $O(n^2)$ 解法一致。

⚠️ 一个必须点破的坑：tails 数组本身【不是】一个递增子序列 ——

它是"每个长度能达到的最小结尾"的记录。比如上面 2, 3, 7, 18 恰好能连成子序列， 但那只是巧合；换一个数组，tails 里相邻两项在原数组里的位置可能是倒过来的。

tails.Count 是答案，tails 的内容不是答案。

性能实测

  性能对比（随机数组，n = 5,000，各跑 3 轮取最快）：
    O(n^2)     ：   11.1 ms
    O(n log n) ：    0.1 ms
    快 75 倍

n = 5000 时差 75 倍；n 再大 10 倍，差距会拉到近千倍（一个是 $n^2$，一个是 $n\log n$）。

两个解法的代码差别并不大 —— 变的只是"状态是什么"。

这正是 15.2 节那句话的实证：状态定义是 DP 里最值钱的一步。

六、练习

练习 15.3.1（手工跑背包） 容量 8，物品 A(重 3, 值 4)、B(重 4, 值 5)、C(重 5, 值 6)。

(a) 写出 $dp[i][c]$ 转移方程，并手工填出二维表（至少填到 $i=3$）。 (b) 最优解是多少？拿了哪几件？ (c) 如果改成完全背包，最优解是多少？

练习 15.3.2（判断遍历方向） 判断下面几种改动会让代码变成"解哪道题"：

(a) 0/1 背包的一维写法，内层 c 从 cap 递减到 w[i] (b) 同上，但改成从 w[i] 递增到 cap (c) 完全背包的一维写法，内层从 cap 递减到 w[i] (d) 二维写法（dp[i][c] 依赖 dp[i-1][...]），内层 c 的方向有影响吗？

练习 15.3.3（LIS 的 tails） 对数组 [3, 1, 4, 1, 5, 9, 2, 6]：

(a) 手工跑一遍 $O(n\log n)$ 的 tails 更新过程，写出每一步之后 tails 的内容。 (b) 最终的 LIS 长度是多少？ (c) tails 的最终内容是不是一个真实的递增子序列？在原数组里找一找。

练习 15.3.4（扩展） 0/1 背包还可以问"恰好装满容量 $cap$ 时的最大价值"（而不是"不超过"）。

(a) 转移方程要改哪里？ (b) 初始值要怎么设？为什么不能全设成 0？ (c) 如果装不满，答案该怎么表示？

练习 15.3.5（挑战·为什么背包没有更快的解法） LIS 能从 $O(n^2)$ 优化到 $O(n\log n)$，但 0/1 背包不能。

(a) 0/1 背包的复杂度是多少？（物品数 $n$、容量 $cap$） (b) 为什么它被称作"伪多项式"算法？$n = 30$、$cap = 10^9$ 时会怎样？ (c) 这说明"问题规模"该怎么衡量？（提示：想想 1.1 节的"输入规模 $n$"到底指什么）

七、练习答案

15.3.1

(a) 二维表

转移方程：

$$dp[i][c] = \max\Big(dp[i-1][c],\ \ dp[i-1][c - w_i] + v_i\Big) \quad (\text{当 } c \ge w_i)$$

手工填表（行是"考虑前 $i$ 件"，列是容量 $c$）：

逐格说明几个关键的：

• $dp[1][3] = \max(dp[0][3],\ dp[0][0] + 4) = 4$ —— 拿 A
• $dp[1][7] = \max(dp[0][7],\ dp[0][4] + 4) = 4$ —— 只有一个 A 可拿，容量再多也只能是 4
• $dp[2][7] = \max(dp[1][7],\ dp[1][3] + 5) = \max(4,\ 4+5) = 9$ —— A + B（重 7）
• $dp[3][8] = \max(dp[2][8],\ dp[2][3] + 6) = \max(9,\ 4+6) = 10$ —— A + C（重 8）

注意 $dp[2][7] = 9$ 而 $dp[3][7]$ 仍是 9： 加了物品 C（重 5）之后，容量 7 的最优解没变 —— 因为已经有 A+B 占了 7 格、值 9，而 C 单独放进去只有 6。

这就是"多一个物品不一定更好"在表里的样子。

(b) 最优解是 10，拿 A 和 C（重 $3+5=8$，值 $4+6=10$）。

顺便验证一下 B + C：重 $4+5=9 > 8$，装不下。 A + B：重 7、值 9，不如 A + C。

(c) 完全背包：也可以拿 10。

容量 8 时：

• A + A = 重 6、值 8
• A + A + A = 重 9 > 8 ❌
• B + B = 重 8、值 10 ✓
• A + C = 重 8、值 10 ✓
• C 单独 = 6

所以还是 10（这次有两条路都能达到：B+B 和 A+C）。

这道小题的用意：0/1 背包和完全背包的最优值不一定不同。 很多数据下两者恰好相等 —— 这正是实验一里"正序版仍有 3.4% 正确"的原因。

15.3.2

(d) 是个常被忽略的点："逆序"这个要求【只对一维写法成立】 —— 二维写法因为保留了完整的上一行，方向怎么写都对。

这也说明：空间压缩不是免费的午餐 —— 省掉一维之后，你就必须自己保证"读到的还是上一轮的值"。

15.3.3

数组：[3, 1, 4, 1, 5, 9, 2, 6]

(a) 逐步更新

(b) LIS 长度 = 4（tails.Count）。

真实的 LIS 可以是 1, 4, 5, 9（下标 1、2、4、5）或 1, 2, 5, 6。

(c) 最终的 tails = [1, 2, 5, 6]——在这个例子里恰好是真实子序列。

在下标上验证：

下标是 $1, 6, 4, 7$ —— 不是递增的！

所以 [1, 2, 5, 6] 的【值】递增，但它们在原数组里的【位置】是乱的 —— tails 数组本身【不是】一个真实的递增子序列。

它只是"每个长度能达到的最小结尾"的记录。 答案是它的长度，不是它的内容。

15.3.4

(a) 转移方程不用改，改的是初始值。

"恰好装满"和"不超过"的区别，全部体现在【边界条件】上：

$$dp[i][c] = \max\Big(dp[i-1][c],\ \ dp[i-1][c - w_i] + v_i\Big)$$

方程一模一样 ✓

(b) 初始值要设成 $-\infty$（而不是 0），但 $dp[0][0] = 0$。

为什么不能全设成 0？

0 的含义是"这个容量下能装出的最大价值是 0" —— 对"不超过"来说，这是对的（空着也是一种合法方案，价值 0）。

但对"恰好装满"来说，$dp[0][5] = 0$ 会撒谎： 它宣称"用容量 5 恰好装满、价值 0" —— 而实际上根本没有物品能填满这 5 格。

设成 $-\infty$ 的意思是"这个状态【不可达】"，之后任何从它转移过来的方案都会被自动排除 （$-\infty$ 加上任何价值还是 $-\infty$）。

初始化：

var dp = new long[cap + 1];
Array.Fill(dp, long.MinValue / 2);   // 全部不可达
dp[0] = 0;                           // 只有「容量 0、价值 0」是可达的

(c) 如果装不满，答案是 $-\infty$，表示无解。

实际代码里判断一下：

return dp[cap] < 0 ? -1 : dp[cap];   // -1 表示「无法恰好装满」

这道题演示的是一个通用规律：

"不超过"和"恰好"的差别，几乎从来不在转移方程里，而在【边界条件】上。

1.3 节讲"最好/最坏/平均"时也是同一个道理：边界值的选择定义了问题的语义。

15.3.5

(a) $O(n \times cap)$。

两层循环：外层 $n$ 件物品（或 $n$ 轮状态），内层 $cap + 1$ 个容量。没有别的操作了。

(b) 因为它虽然是多项式的，但"多项式于谁"取决于 $cap$ 的【数值大小】，而不是【输入长度】。

关键区别在这里：

$cap = 10^9$ 时：输入里"10^9"只占 10 个字符（或 30 个二进制位）， 但算法要跑 $10^9$ 次 —— 输入大小只增加了 10 个字符，运行时间涨了十亿倍。

这就是"伪多项式"的定义：复杂度是关于【数值】的多项式，而不是关于【输入长度】的多项式。

换句话说：输入长度是 $\log(cap)$ 级别，而算法是 $cap$ 级别 —— 两者是指数关系。

$n = 30$、$cap = 10^9$ 时：$30 \times 10^9$ 次操作 —— 现代 CPU 也要几十秒以上，实际不可用。

(c) "问题规模"必须按【输入占多少空间】来衡量，而不是"数字有多大"。

1.1 节说"输入规模 $n$"时，指的是【元素个数】 —— 因为数字 $n$ 写成二进制只占 $\log n$ 个比特。

背包问题里，容量 $cap$ 也是一个输入数字，它只占 $\log(cap)$ 个比特 —— 但算法却要跑 $cap$ 步。

所以：背包问题【不是】多项式时间可解的（它是 NP 难的）， 只是当 $cap$ 比较小的时候，这个伪多项式算法【恰好很快、很有用】。

这也回答了 14.3 节留下的那句话：0/1 背包没有多项式时间的精确算法 —— 所以才会有"贪心近似"这一路（虽然它的近似比无界）， 以及在容量可控时用 DP 这条实用路线。

八、常见错误

九、本节总结

1. 0/1 背包的状态：$dp[i][c]$ = 前 $i$ 件物品、容量 $c$ 的最大价值；转移方程 $= \max(\text{不拿},\ \text{拿})$。
2. 二维可以压成一维，因为 $dp[i][c]$ 只依赖上一行。
3. 但压成一维后，内层必须【逆序】—— 本节最重要的实测：
   • 逆序：dp[c-w] 还是上一轮的值 → 物品只用一次 → 0/1 背包 ✓
   • 正序：dp[c-w] 已是本轮的值 → 物品可以复用 → 完全背包
4. 实测数据：容量 10 的例子中，逆序给 14（正确）、正序给 15（错）； 2000 组随机数据上逆序 100%、正序 3.4%。
5. "0/1 背包写错正序 = 完全背包写对正序" —— 2000 组随机数据上，把正序版当完全背包用，正确率 100%。
6. LIS 的 $O(n\log n)$：状态换成 $tails[k]$ = 长度为 $k+1$ 的递增子序列中结尾最小的值； 因为 tails 严格递增，可以用二分更新。
7. 实测：两种解法 2000 组零不一致；n=5000 时 $O(n\log n)$ 快 75 倍（11.1 ms vs 0.1 ms）。
8. 两个细节，一个道理：背包的"方向"和 LIS 的"状态"都不是琐碎的实现细节 —— 它们各自决定了解的是哪道题、以及复杂度是多少。

下一节衔接：本节做了一次"空间优化" —— 把二维表压成了一维数组。

但它是怎么做到的？ 因为 dp[i][c] 只依赖"上一行"。 如果依赖的是"上面一整片"呢？

15.4 节回答这个问题，并给出判断"能不能压、能压到几维"的系统方法：

• 什么时候能滚动？（依赖的宽度决定）
• 滚动之后那个"方向"问题会不会重现？
• 空间省下来了，代价是什么？（可读性、调试难度、以及 2.3 节练习 2.3.4 提过的"状态依赖宽度"）

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "15.3",
  "title": "经典题型：背包与最长递增子序列",
  "covered": [
    "0/1 背包的状态定义（四问自检）与转移方程（枚举最后一步：拿/不拿）",
    "二维到一维的空间压缩及其依据（dp[i][c] 只依赖上一行）",
    "实测一（核心）：逆序 14 正确、正序 15 错误，含逐格推导",
    "「为什么必须逆序」的原理：dp[c-w] 是上一轮还是本轮的值",
    "实测一的对拍：逆序 2000/2000、正序 67/2000（3.4%）",
    "完全背包的定义与「正序即正确」的实测",
    "「0/1 背包写错正序 = 完全背包写对正序」的验证（2000 组 100%）",
    "LIS 的 O(n log n) 状态定义（tails）与其支配性论证",
    "tails 的二分更新（替换而非插入）与实测（样例 4，2000 组零不一致）",
    "「tails 不是真实子序列」的辨析",
    "LIS 两种解法的性能实测（n=5000，11.1 ms vs 0.1 ms，快 75 倍）",
    "「恰好装满」与「不超过」的边界条件差异",
    "背包的伪多项式性质与 NP 难（练习 15.3.5）"
  ],
  "unresolved": [
    "空间优化的系统方法（滚动数组的边界）留到 15.4",
    "多种背包变体（多重背包、分组背包）超出本书范围",
    "背包的 NP 难性只给了直觉论证，未给归约证明"
  ],
  "canonical_terms": {
    "0/1 背包（0/1 Knapsack）": "每件物品要么整个拿走、要么不拿；一维写法需逆序遍历",
    "完全背包（Unbounded Knapsack）": "每种物品可以拿任意多件；一维写法用正序遍历",
    "最长递增子序列（LIS）": "最长的严格递增子序列（不要求连续）；O(n log n) 解法用 tails 数组",
    "伪多项式（Pseudo-polynomial）": "复杂度关于输入的【数值】而非【长度】是多项式的，如 O(n × cap)"
  },
  "symbols_units": {
    "dp[i][c]": "前 i 件物品、容量 c 时的最大价值",
    "tails[k]": "所有长度为 k+1 的递增子序列中，结尾最小的值",
    "n": "物品数 / 数组长度",
    "cap": "背包容量"
  },
  "assumptions": [
    "读者已掌握 15.2 的状态定义方法与四个自检问题",
    "读者理解 14.3 的 0/1 背包问题与贪心为何失效",
    "物品重量与价值均为正整数"
  ],
  "word_count_actual": 3315,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑（AMD Ryzen 7 9700X），输出见正文",
    "项目文件：99-tools/samples/Ch15/Sec153/",
    "实验一：容量 10 的例子上二维 14、逆序 14、正序 15、暴力 14，为实测",
    "实验一的对拍：2000 组随机数据（seed=20260918）逆序 2000/2000、正序 67/2000，为实测",
    "实验二：完全背包正序 15 与暴力一致；正序版当完全背包用 2000 组 100% 正确，为实测",
    "实验三：LIS 样例 [10,9,2,5,3,7,101,18] 两种解法均为 4、tails=[2,3,7,18]；2000 组零不一致；n=5000 性能 11.1 vs 0.1 ms，为实测",
    "术语写法与 glossary.md 一致（0/1 背包、分数背包、状态转移方程）"
  ],
  "known_issues": [
    "实验一对拍初版的说明文字写「正序版也有相当高的正确率」，与实测的 3.4% 完全相反 —— 按实测改写，并补上「答案只会变大」这个方向的解释",
    "练习 15.3.1(a) 手工填表时，初版把 dp[1][7] 错填成 7（只有一个 A 可拿，应为 4）—— 在答案里保留了这个修正过程，并补上第 3 行的完整重算",
    "练习 15.3.4 涉及「恰好装满」的变体，其 long.MinValue/2 的哨兵用法与 15.1 的 -1 缓存标记、13.3 的 int.MaxValue/2 属于同一类技巧 —— 在答案中明确点出「设成 -∞ 表示不可达」的含义，避免读者死记数值"
  ],
  "next": "15.4 空间优化与滚动数组"
}