DP 系列（三）：背包 DP

本讲定位：背包是竞赛中出现频率最高的 DP 模型，也是”选或不选”类问题的总模板。本讲覆盖四种基本背包（01、完全、多重、分组）和方案数变形，核心目标只有一个——把循环顺序背后的道理彻底讲透，让学生以后写背包时是”推出来的”，不是”背出来的”。

前置知识：专题一（递推）、专题二（状态设计的基本感觉）。

标注 ⭐ 的小节为进阶内容。

1. 背包问题全家福

共同的舞台：容量为 $W$ 的背包、$n$ 个物品，第 $i$ 个物品重 $w_i$、价值 $v_i$，求不超过容量时的最大总价值。区别只在每个物品能选几次：

先把 01 背包彻底吃透——其余三种都是它的变奏。

2. 01 背包（洛谷 P1048 采药，NOIP 2005 普及组）

题意：总时间 $T \le 1000$，$m \le 100$ 株草药，第 $i$ 株耗时 $t_i$、价值 $v_i$，每株最多采一次，求最大总价值。

样例：T=70, m=3，草药 (71,100) (69,1) (1,2) → 答案 3（采后两株，时间 $70$，价值 $1+2=3$）。

2.1 状态设计：两个进度缺一不可

只用”考虑到第几个物品”做状态是不够的——还剩多少容量直接决定后面能装什么。所以状态必须同时记录两个量：

$$ f[i][j] = \text{只考虑前 } i \text{ 个物品、时间不超过 } j \text{ 时的最大价值} $$

对第 $i$ 个物品做”选或不选”的分类讨论：

• 不采：问题变成”前 $i-1$ 个物品、容量还是 $j$“，得 $f[i-1][j]$；
• 采（要求 $j \ge t_i$）：占掉 $t_i$ 的时间，剩下的问题是”前 $i-1$ 个物品、容量 $j - t_i$“，得 $f[i-1][j-t_i] + v_i$。

$$ f[i][j] = \max\big(f[i-1][j],\ f[i-1][j-t_i] + v_i\big) $$

边界 $f[0][j] = 0$。答案 $f[m][T]$。复杂度 $O(mT)$。

#include<bits/stdc++.h>
using namespace std;

int t[105], v[105];
int f[105][1005];   // f[i][j]：前 i 株草药、时间不超过 j 的最大价值

int main() {
    int T, m;
    scanf("%d%d", &T, &m);
    for (int i = 1; i <= m; i++) scanf("%d%d", &t[i], &v[i]);

    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= T; j++) {
            f[i][j] = f[i - 1][j];                              // 不采第 i 株
            if (j >= t[i])
                f[i][j] = max(f[i][j], f[i - 1][j - t[i]] + v[i]); // 采第 i 株
        }
    printf("%d\n", f[m][T]);
    return 0;
}

注意转移里全部是 $f[i-1][\cdot]$——每个物品只考虑一次，“选它”的来源必须是还没考虑过它的世界。这句话是理解下一节的钥匙。