01背包

一、问题定义

01 背包问题是动态规划中的经典问题，它是为了解决以下问题：

在物品只能选或不选（0或1）的前提下，在容量有限的背包中，如何选择物品以获得最大总价值。

装杯式描述如下：

有 $n$ 件物品，每件物品有：

• 体积 $w_i$
• 价值 $v_i$

现在有一个容量为 $W$ 的背包。每种物品最多只能选一次，问在不超过容量 $W$ 的前提下，最多能选出多少价值的物品。

---

二、状态转移原理与证明

状态转移原理

我们设状态转移数组 $f[i][j]$ 表示：前 $i$ 件物品中选择若干件放入容量为 $j$ 的背包时，所能获得的最大价值。

我们要从 $f[0][0]$ 状态出发，逐步扩展到 $f[n][W]$。

状态转移推导如下：

• 不选第 $i$ 件物品：
  此时最大价值为 $f[i-1][j]$

• 选第 $i$ 件物品：
  此时前提是容量 $j \ge w_i$，那么就要从 $f[i-1][j - w_i]$ 这个状态转移来，并加上 $v_i$ 的价值。

所以，有如下状态转移方程：

$$f[i][j] = \begin{cases} f[i-1][j] & \text{if } j < w_i \\ \max(f[i-1][j],\ f[i-1][j - w_i] + v_i) & \text{else} \end{cases}$$

边界条件：

$$f[0][j] = 0,\quad \text{对于所有 } j \in [0, W]$$

---

证明

我们先假设背包体积为 $V$，最优解为$E$，而E中含有某个物品为$A$（体积为$v$，价值为$w$）。那么 $V - v$ 的最优解也一定是 $E - A$.

证明：采用反证法
假设 $E - A$ 不是 $V - v$ 的最优解，那么假设 $V - v$ 的最优解为 $F$，则F的价值大于 $E - A$ 的价值，那么 $F + A$ 肯定可以是$V$的一种选择，而它的价值则高于$E$，$E$不是最优解，矛盾，因此 $V - v$ 的最优解也一定是 $E - A$ 。

---

三、图示说明

以如下样例为例：

• 背包容量 $W = 5$
• 物品数量 $n = 3$
• 物品信息如下：

物品编号	体积 $w_i$	价值 $v_i$
1	1	2
2	3	4
3	4	5

初始状态（$f[0][j] = 0$）：

$i =0$	0	1	2	3	4	5
状态值 $f[0][j]$	0	0	0	0	0	0

处理第 1 件物品（$w_1=1, v_1=2$）：

$$f[1][j] = \max(f[0][j],\ f[0][j - 1] + 2)$$

$i=1$	0	1	2	3	4	5
状态值 $f[1][j]$	0	2	2	2	2	2

处理第 2 件物品（$w_2=3, v_2=4$）：

$$f[2][j] = \max(f[1][j],\ f[1][j - 3] + 4)$$

$i=2$	0	1	2	3	4	5
状态值 $f[2][j]$	0	2	2	4	6	6

处理第 3 件物品（$w_3=4, v_3=5$）：

$$f[3][j] = \max(f[2][j],\ f[2][j - 4] + 5)$$

$i=3$	0	1	2	3	4	5
状态值 $f[3][j]$	0	2	2	4	6	7

最终答案为：$\boxed{7}$

在这里可以发现 $i = 3$ 的情况只需要用到 $i = 2$，所以我们可以使用滚动数组来节约空间。

---

四、实战题 + 实现代码 + 优化方式

洛谷 P1048：采药问题（01背包）

题目链接：洛谷 P1048

题意简述：

• 背包容量为总时间 $T$
• 有 $M$ 种草药，每种草药：
  • 采集耗时 $w_i$
  • 获得药效 $v_i$
• 每种草药最多采集一次
• 求在总时间不超过 $T$ 的前提下获得的最大药效总和

---

二维数组写法（标准 DP）

int dp[105][1005];
memset(dp,0,sizeof(dp))
for (int i = 1; i <= M; i++) {
    for (int j = 0; j <= T; j++) {
        if (j < w[i]) dp[i][j] = dp[i-1][j];
        else dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
    }
}

时间复杂度 $O(nW)$，空间复杂度 $O(nW)$

---

一维数组写法（空间优化）

int dp[1005];
memset(dp,0,sizeof(dp))
for (int i = 1; i <= M; i++) {
    for (int j = T; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

• 优化思路：当前状态只依赖于上一行，因此可以使用一维数组倒序更新
• 时间复杂度仍为 $O(nW)$，空间复杂度降为 $O(W)$

---

五、总结

• 01 背包问题是每种物品最多选一次的背包问题

• 使用动态规划可以有效避免重复计算

• 状态转移方程：

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

• 可使用滚动数组优化空间

• 常用于：资源有限，选/不选(0/1)物品的最优组合场景