01 背包

一句话算法

01 背包的核心是“每个物品只能选一次”：处理第 $i$ 个物品时，答案只分成选它和不选它两种情况。

问题模型

给定 $n$ 个物品和一个容量为 $C$ 的背包。第 $i$ 个物品有：

• 重量 $w_i$；
• 价值 $v_i$；
• 每个物品最多只能选一次。

要求选择若干物品，使总重量不超过 $C$，并让总价值最大。

输入格式通常为：

n C
w1 v1
w2 v2
...
wn vn

核心直觉

面对第 $i$ 个物品时，只有两条路：

1. 不选它：答案沿用前 $i-1$ 个物品在容量 $c$ 下的最优值。
2. 选它：先给它留出 $w_i$ 的容量，再加上它的价值 $v_i$。

因此，所有选择都能按“最后一个物品选不选”分成两类。

这就是 01 背包最重要的分类方式。

状态设计

定义：

表示只考虑前 $i$ 个物品，背包容量为 $c$ 时能得到的最大价值。

边界：

表示没有物品可选时，最大价值为 $0$。

状态转移

第 $i$ 个物品不选：

第 $i$ 个物品选：

前提是 $c\ge w_i$。

所以完整转移为：

最终答案是：

算法步骤

1. 读入 $n,C$ 和每个物品的 $w_i,v_i$。
2. 初始化 dp[0][c] = 0。
3. 枚举物品 i = 1..n。
4. 枚举容量 c = 0..C。
5. 先继承不选第 i 个物品的值。
6. 如果 c >= w[i]，尝试选第 i 个物品并取最大值。
7. 输出 dp[n][C]。

算法证明

核心不变量：计算完第 $i$ 行后，dp[i][c] 等于只使用前 $i$ 个物品、容量不超过 $c$ 的最大价值。

1. 边界正确

   当 $i=0$ 时，没有物品可选，任意容量下最大价值都是 $0$。

2. 分类完整

   任意一个只使用前 $i$ 个物品的最优方案，对第 $i$ 个物品只有两种可能：选或不选。

3. 不选第 $i$ 个物品

   方案完全来自前 $i-1$ 个物品，价值为：

   $$dp[i-1][c]$$

4. 选第 $i$ 个物品

   剩余容量为 $c-w_i$，其余物品只能从前 $i-1$ 个中选，价值为：

   $$dp[i-1][c-w_i]+v_i$$

5. 取最大值

   两类方案覆盖所有可能，且互不遗漏。取两者最大值，就是当前状态的最优值。

因此状态转移正确，算法正确。

复杂度分析

• 二维写法时间复杂度：$O(nC)$。
• 二维写法空间复杂度：$O(nC)$。
• 一维优化写法时间复杂度：$O(nC)$。
• 一维优化写法空间复杂度：$O(C)$。

代码实现

二维写法

二维写法最容易理解，也方便之后恢复选了哪些物品。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

int main() {
    int n, capacity;
    cin >> n >> capacity;

    vector<int> weight(n + 1), value(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            dp[i][c] = dp[i - 1][c];
            if (c >= weight[i]) {
                dp[i][c] = max(dp[i][c],
                               dp[i - 1][c - weight[i]] + value[i]);
            }
        }
    }

    cout << dp[n][capacity] << "\n";
    return 0;
}
    

一维写法

一维写法是竞赛中最常用的 01 背包模板。

关键点：容量必须倒序枚举。

        
1

        for (int c = capacity; c >= weight; c--)
    

倒序的原因是：第 $i$ 个物品只能选一次，更新 dp[c] 时必须使用上一轮物品留下的 dp[c-weight]，不能使用本轮刚更新出来的值。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

int main() {
    int n, capacity;
    cin >> n >> capacity;

    vector<int> dp(capacity + 1, 0);

    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int c = capacity; c >= weight; c--) {
            dp[c] = max(dp[c], dp[c - weight] + value);
        }
    }

    cout << dp[capacity] << "\n";
    return 0;
}
    

Python 一维写法

Python 写法和 C++ 一维写法完全一致，核心仍然是容量倒序枚举：

        
1
2
3
4
5

        dp = [0] * (C + 1)

for w, v in items:
    for c in range(C, w - 1, -1):
        dp[c] = max(dp[c], dp[c - w] + v)
    

完整可运行版本如下：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

        import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, C = data[0], data[1]
    dp = [0] * (C + 1)

    pos = 2
    for _ in range(n):
        w, v = data[pos], data[pos + 1]
        pos += 2

        # 01 背包必须倒序枚举容量，避免同一个物品被重复使用。
        for c in range(C, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)

    print(dp[C])


if __name__ == "__main__":
    main()
    

恰好装满

如果题目要求“恰好装满容量 $C$”，初始化要区分可达和不可达：

• dp[0] = 0：容量为 $0$ 可以什么都不选；
• 其他 dp[c] = -INF：一开始这些容量都不可达。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

int main() {
    int n, capacity;
    cin >> n >> capacity;

    const int NEG_INF = -1e9;
    vector<int> dp(capacity + 1, NEG_INF);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int c = capacity; c >= weight; c--) {
            if (dp[c - weight] == NEG_INF) continue;
            dp[c] = max(dp[c], dp[c - weight] + value);
        }
    }

    if (dp[capacity] == NEG_INF) {
        cout << "Impossible\n";
    } else {
        cout << dp[capacity] << "\n";
    }

    return 0;
}
    

测试用例

输入：

5 7
2 6
2 3
6 5
5 4
4 6

输出：

12

解释：最优选择是第 1 个和第 5 个物品，总重量为 $2+4=6$，总价值为 $6+6=12$。

应用分类详解

01 背包的本质是：每个对象只有“选一次”或“不选”两种决策。只要题目要求从一批对象中挑一部分，并且每个对象不能重复使用，就应该先尝试 01 背包模型。

一、容量限制下最大价值

典型模式： 有重量、有价值、有容量，求最大价值。

识别信号： 出现“每个物品只能选一次”“总时间不超过”“总费用不超过”。

核心建模： 重量可以是时间、费用、体积，价值可以是收益、得分、满意度。

二、恰好装满和可达性

典型模式： 不一定要求最大价值，而是判断某个容量能否达到。

识别信号： 出现“恰好”“能否组成”“有多少种重量可以称出”。

核心建模： dp[c] 表示容量 c 是否可达，或可达时的最优值。

三、附加维度的 01 背包

典型模式： 除容量外，还要控制数量、分组、人数等额外条件。

识别信号： 出现“选恰好 $k$ 个”“两队人数相同”“预算和数量同时限制”。

核心建模： 在容量维度外再加一个维度，例如 dp[k][c] 表示选了 k 个、容量为 c 的状态。

四、作为其他背包的基础

典型模式： 完全背包、多重背包、分组背包都可以从 01 背包的“选或不选”理解开始。

识别信号： 出现“每种可选多次”“每组最多选一个”“每种有数量限制”。

核心建模： 先明确每个物品的使用次数限制，再决定容量枚举方向和状态转移。

经典例题

1. luogu-P1048

最基础的 01 背包。每株草药最多采一次，时间是容量，价值是收益。

2. luogu-P1164

恰好凑出金额的方案数。状态从最大价值改成方案数，转移仍然是 01 背包。

3. luogu-P1855

二维费用 01 背包。每个物品只能选一次，但同时消耗两个资源。

练习题目

id: dynamic-programming-knapsack-01knapsack-practice title: practice description: 01 背包的练习题目：采药、干草出售、小A点菜。 tags: [“动态规划”, “背包”, “01背包”, “练习题”]

练习题目

• luogu-P1048 [NOIP2005 普及组] 采药 背包入门
• luogu P2925 [USACO08DEC]干草出售 标准01背包
• luogu-P1164 小A点菜 恰好装满入门题目,计数DP
• 砝码称重 恰好装满
• 积木城堡 来源：vijos P1059
• 开心的金明
• 金明的预算方案 来源：NOIP2006 第二题
• 猫狗大战 恰好装满
• 新年趣事之打牌 来源： vijos P1071

参考

• 旧版文章：Rbook_ejs_old/book/dynamic_programming/knapsack/01knapsack/index.md
• 本书后续：完全背包、分组背包、多重背包