0-1 背包问题

前言：选还是不选？动态规划的起点

你去登山，背包容量有限。面前有 $n$ 件物品，每件有重量和价值。你当然想带价值尽量多的东西，但背包装不下所有。每件物品只有一件——要么带，要么不带。

这就是 0-1 背包问题。它是动态规划（DP）最经典的入门题。

暴力做法：枚举所有 $2^n$ 种选择方案，找出最优的。$n = 30$ 就有 $10^9$ 种方案，$n = 100$ 就有 $10^{30}$ 种——不可能。

DP 的思路完全不同。与其枚举”具体选了哪些物品”，不如只关心两个信息：

• 考虑了前几个物品？
• 用了多少容量？

只要知道”考虑前 $i$ 个物品、用了容量 $j$ 时的最大价值”，就能推导出考虑第 $i+1$ 个物品后的结果——第 $i+1$ 个物品要么选（占用容量、获得价值），要么不选（什么都不变），取两者较优。

这个”状态 + 转移”的思想是 DP 的核心。一旦掌握，你会发现它不仅能解决背包，还能解决一大类优化问题。这篇笔记会从状态定义开始，推导出转移方程，然后给出 C++ 实现，最后通过一道例题巩固。

0-1 背包问题

问题的本质

有 $n$ 个物品，每个物品有重量 $w_i$ 和价值 $v_i$。背包容量为 $W$。每个物品要么选要么不选（0-1），求能装入的最大总价值。

暴力枚举所有 $2^n$ 种组合，$n = 100$ 就有 $2^{100}$ 种——不可行。

关键洞察：不需要记住”选了哪些物品”，只需要记住”用多大容量、考虑了几个物品时的最大价值”。这是一个状态，而状态之间有明确的递推关系——这就是动态规划。

状态定义

$dp[j]$：考虑当前物品时，容量为 $j$ 能获得的最大价值。

状态转移

对每个物品 $i$，枚举容量 $j$：

• 不选：价值不变，$dp[j]$ 维持原值
• 选：占用 $w_i$ 的容量，获得 $v_i$ 的价值，即 $dp[j - w_i] + v_i$

取两者较优：

$$dp[j] = \max(dp[j],\ dp[j - w_i] + v_i)$$

关键细节：内层循环 $j$ 必须从大到小枚举。因为每个物品只能选一次，如果从小到大枚举，$dp[j - w_i]$ 可能已经被当前物品更新过，等于同一个物品选了两次。从大到小枚举保证 $dp[j - w_i]$ 是上一轮（还没考虑当前物品）的值。

实现

int dp[MAXN];  // dp[j] = 容量 j 时的最大价值

int knapsack(int n, int W, int w[], int v[]) {
    for (int i = 1; i <= n; i++)
        for (int j = W; j >= w[i]; j--)     // 从大到小
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[W];
}

空间只需 $O(W)$——滚动数组，每轮复用同一个一维数组。

复杂度

时间 $O(nW)$，空间 $O(W)$。

注意：这是伪多项式时间——$W$ 是数值大小而非输入长度，所以严格来说不是多项式算法。但对 $W \le 10^5$ 级别的实际问题完全够用。

变体速查

变体	区别	改动
完全背包	每个物品可选无限次	$j$ 从小到大枚举
多重背包	每个物品有数量上限	二进制拆分或单调队列优化
分组背包	每组至多选一个	外层加一组循环，组内互斥

例题：采药

有 $T$ 分钟时间和 $n$ 株草药，每株草药需要时间 $t_i$、价值 $v_i$。每株只能采一次，求能采到的最大总价值。

$1 \le T \le 1000$，$1 \le n \le 100$

标准的 0-1 背包，时间就是容量。

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[1001];

int main() {
    int T, n;
    scanf("%d%d", &T, &n);
    for (int i = 0; i < n; i++) {
        int t, v;
        scanf("%d%d", &t, &v);
        for (int j = T; j >= t; j--)
            dp[j] = max(dp[j], dp[j - t] + v);
    }
    printf("%d\n", dp[T]);
    return 0;
}

解析：每株草药就是一个物品，时间 $t_i$ 是重量，$T$ 是背包容量。内层从 $T$ 到 $t_i$ 倒序枚举，确保每株草药只被选一次。最终 dp[T] 就是用满全部时间能获得的最大价值。不需要二维数组——因为转移只依赖上一轮的值，一维滚动即可。