背包问题完全指南#

背包问题是动态规划中的经典问题，也是面试和竞赛中的高频考点。本文将系统性地介绍各类背包问题的原理、解法和例题。

背包问题分类体系#

graph TB A[背包问题] --> B[01背包] A --> C[完全背包] A --> D[多重背包] A --> E[分组背包] A --> F[混合背包] A --> G[二维费用背包] B --> B1[每件物品最多选一次] C --> C1[每件物品无限次使用] D --> D1[每件物品有数量限制] E --> E1[每组最多选一件] F --> F1[混合多种类型] G --> G1[两个维度限制] style B fill:#e1f5ff style C fill:#fff4e1 style D fill:#ffe1f5 style E fill:#e1ffe1 style F fill:#f5e1ff style G fill:#ffe1e1

一、01 背包问题#

问题描述#

有 N 件物品和一个容量为 V 的背包。第 i 件物品的体积是 w[i]，价值是 v[i]。每件物品最多只能选一次，求解将哪些物品装入背包可使价值总和最大。

决策树图解#

graph TD A[物品1: 选或不选] --> B[选: 剩余容量V-w1] A --> C[不选: 剩余容量V] B --> D[物品2: 选或不选] C --> E[物品2: 选或不选] D --> F[...] E --> G[...] style A fill:#e1f5ff style B fill:#d4edda style C fill:#f8d7da

状态定义#

dp[i][j] 表示前 i 件物品放入容量为 j 的背包中的最大价值。

状态转移方程#

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

dp[i-1][j]：不选第 i 件物品
dp[i-1][j-w[i]] + v[i]：选第 i 件物品（前提是 j >= w[i]）

空间优化（一维数组）#

由于 dp[i] 只依赖于 dp[i-1]，可以用一维数组优化：

1
for (int i = 1; i <= n; i++) {
2
    for (int j = V; j >= w[i]; j--) {  // 逆序遍历
3
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
4
    }
5
}

关键点：逆序遍历是为了保证每个物品只被使用一次。

01 背包遍历方向图解#

graph LR A[容量 V] -->|逆序| B[V-1] B --> C[V-2] C --> D[...] D --> E[w_i] style A fill:#e1f5ff style E fill:#d4edda F[原因: 防止物品被重复使用] -.-> A

例题：AcWing 2. 01背包问题 #

题目描述：有 N 件物品和一个容量是 V 的背包。每件物品只能用一次。第 i 件物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

代码实现：

1
import java.util.Scanner;
2

3
public class Knapsack01 {
4
    static final int MAXN = 1005;
5
    static int n, V;
6
    static int[] w = new int[MAXN];
7
    static int[] v = new int[MAXN];
8
    static int[] dp = new int[MAXN];
9

10
    public static void main(String[] args) {
11
        Scanner sc = new Scanner(System.in);
12
        n = sc.nextInt();
13
        V = sc.nextInt();
14

15
        for (int i = 1; i <= n; i++) {
16
            w[i] = sc.nextInt();
17
            v[i] = sc.nextInt();
18
        }
19

20
        for (int i = 1; i <= n; i++) {
21
            for (int j = V; j >= w[i]; j--) {
22
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
23
            }
24
        }
25

26
        System.out.println(dp[V]);
27
        sc.close();
28
    }
29
}

二、完全背包问题#

问题描述#

有 N 种物品和一个容量为 V 的背包。第 i 种物品的体积是 w[i]，价值是 v[i]。每种物品有无限件可用，求解将哪些物品装入背包可使价值总和最大。

状态转移方程#

1
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

注意与 01 背包的区别：这里是 dp[i][j-w[i]] 而不是 dp[i-1][j-w[i]]，因为物品可以重复选择。

空间优化（一维数组）#

1
for (int i = 1; i <= n; i++) {
2
    for (int j = w[i]; j <= V; j++) {  // 正序遍历
3
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
4
    }
5
}

关键点：正序遍历，允许物品被重复使用。

完全背包遍历方向图解#

graph LR A[容量 w_i] -->|正序| B[w_i+1] B --> C[w_i+2] C --> D[...] D --> E[V] style A fill:#fff4e1 style E fill:#d4edda F[原因: 允许物品被重复选择] -.-> A

例题：AcWing 3. 完全背包问题 #

题目描述：有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。第 i 种物品的体积是 vi，价值是 wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

代码实现：

1
import java.util.Scanner;
2

3
public class CompleteKnapsack {
4
    static final int MAXN = 1005;
5
    static int n, V;
6
    static int[] w = new int[MAXN];
7
    static int[] v = new int[MAXN];
8
    static int[] dp = new int[MAXN];
9

10
    public static void main(String[] args) {
11
        Scanner sc = new Scanner(System.in);
12
        n = sc.nextInt();
13
        V = sc.nextInt();
14

15
        for (int i = 1; i <= n; i++) {
16
            w[i] = sc.nextInt();
17
            v[i] = sc.nextInt();
18
        }
19

20
        for (int i = 1; i <= n; i++) {
21
            for (int j = w[i]; j <= V; j++) {
22
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
23
            }
24
        }
25

26
        System.out.println(dp[V]);
27
        sc.close();
28
    }
29
}

三、多重背包问题#

问题描述#

有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 s[i] 件，每件体积是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。

朴素解法（三重循环）#

1
for (int i = 1; i <= n; i++) {
2
    for (int j = V; j >= w[i]; j--) {
3
        for (int k = 1; k <= s[i] && k * w[i] <= j; k++) {
4
            dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i]);
5
        }
6
    }
7
}

时间复杂度：O(V * Σs[i])

二进制优化#

将每种物品的 s[i] 件拆分成若干组，每组的数量为 2 的幂次（1, 2, 4, 8, …），然后转化为 01 背包问题。

拆分原理：任何正整数都可以用若干个 2 的幂次表示。例如 s[i] = 10，可以拆分为 1, 2, 4, 3（1+2+4+3=10）。

二进制拆分图解#

graph LR A[10件物品] --> B[拆分为] B --> C[1件] B --> D[2件] B --> E[4件] B --> F[3件] C --> G[可组合出 0-10 的任意数量] D --> G E --> G F --> G style A fill:#ffe1f5 style G fill:#d4edda

代码实现：

1
import java.util.Scanner;
2

3
public class MultipleKnapsack {
4
    static final int MAXN = 25005;
5
    static int n, V;
6
    static int[] w = new int[MAXN];
7
    static int[] v = new int[MAXN];
8
    static int[] dp = new int[MAXN];
9

10
    public static void main(String[] args) {
11
        Scanner sc = new Scanner(System.in);
12
        n = sc.nextInt();
13
        V = sc.nextInt();
14

15
        int cnt = 0;  // 拆分后的物品总数
16
        for (int i = 1; i <= n; i++) {
17
            int a = sc.nextInt();  // 体积
18
            int b = sc.nextInt();  // 价值
19
            int s = sc.nextInt();  // 数量
20

21
            int k = 1;
22
            while (k <= s) {
23
                cnt++;
24
                w[cnt] = k * a;
25
                v[cnt] = k * b;
26
                s -= k;
27
                k *= 2;
28
            }
29
            if (s > 0) {
30
                cnt++;
31
                w[cnt] = s * a;
32
                v[cnt] = s * b;
33
            }
34
        }
35

36
        // 01 背包
37
        for (int i = 1; i <= cnt; i++) {
38
            for (int j = V; j >= w[i]; j--) {
39
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
40
            }
41
        }
42

43
        System.out.println(dp[V]);
44
        sc.close();
45
    }
46
}

例题：AcWing 4. 多重背包问题 I #

使用二进制优化解法，时间复杂度降低到 O(V * Σlog(s[i]))。

四、分组背包问题#

问题描述#

有 N 组物品和一个容量为 V 的背包。第 i 组物品有 s[i] 件，同一组内的物品最多只能选一件。每件物品有体积和价值。求解将哪些物品装入背包可使价值总和最大。

分组背包图解#

graph TD A[第1组] --> B[物品1-1] A --> C[物品1-2] A --> D[物品1-3] E[第2组] --> F[物品2-1] E --> G[物品2-2] H[最多选一件] -.-> A I[最多选一件] -.-> E style A fill:#e1ffe1 style E fill:#e1ffe1 style B fill:#fff4e1 style C fill:#fff4e1 style D fill:#fff4e1 style F fill:#ffe1f5 style G fill:#ffe1f5

状态转移方程#

1
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i][k]] + v[i][k])  // k 枚举第 i 组的所有物品

空间优化（一维数组）#

1
for (int i = 1; i <= n; i++) {  // 枚举组
2
    for (int j = V; j >= 0; j--) {  // 逆序枚举体积
3
        for (int k = 1; k <= s[i]; k++) {  // 枚举组内物品
4
            if (j >= w[i][k]) {
5
                dp[j] = Math.max(dp[j], dp[j - w[i][k]] + v[i][k]);
6
            }
7
        }
8
    }
9
}

例题：AcWing 9. 分组背包问题 #

代码实现：

1
import java.util.Scanner;
2

3
public class GroupKnapsack {
4
    static final int MAXN = 105;
5
    static int n, V;
6
    static int[] s = new int[MAXN];  // 每组物品数量
7
    static int[][] w = new int[MAXN][MAXN];  // 每组物品的体积
8
    static int[][] v = new int[MAXN][MAXN];  // 每组物品的价值
9
    static int[] dp = new int[MAXN];
10

11
    public static void main(String[] args) {
12
        Scanner sc = new Scanner(System.in);
13
        n = sc.nextInt();
14
        V = sc.nextInt();
15

16
        for (int i = 1; i <= n; i++) {
17
            s[i] = sc.nextInt();
18
            for (int j = 1; j <= s[i]; j++) {
19
                w[i][j] = sc.nextInt();
20
                v[i][j] = sc.nextInt();
21
            }
22
        }
23

24
        for (int i = 1; i <= n; i++) {
25
            for (int j = V; j >= 0; j--) {
26
                for (int k = 1; k <= s[i]; k++) {
27
                    if (j >= w[i][k]) {
28
                        dp[j] = Math.max(dp[j], dp[j - w[i][k]] + v[i][k]);
29
                    }
30
                }
31
            }
32
        }
33

34
        System.out.println(dp[V]);
35
        sc.close();
36
    }
37
}

五、混合背包问题#

问题描述#

有的物品只能用一次（01背包），有的物品可以无限用（完全背包），有的物品有数量限制（多重背包）。

解法#

根据物品类型分别处理：

1
for (int i = 1; i <= n; i++) {
2
    if (物品类型 == 01背包) {
3
        for (int j = V; j >= w[i]; j--) {
4
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
5
        }
6
    } else if (物品类型 == 完全背包) {
7
        for (int j = w[i]; j <= V; j++) {
8
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
9
        }
10
    } else if (物品类型 == 多重背包) {
11
        // 使用二进制优化
12
    }
13
}

六、二维费用背包#

问题描述#

物品不仅有重量限制，还有体积限制。第 i 件物品的重量是 w[i]，体积是 v[i]，价值是 val[i]。背包的最大重量是 W，最大体积是 V。

状态定义#

dp[i][j][k] 表示前 i 件物品，重量不超过 j，体积不超过 k 的最大价值。

空间优化（二维数组）#

1
for (int i = 1; i <= n; i++) {
2
    for (int j = W; j >= w[i]; j--) {
3
        for (int k = V; k >= v[i]; k--) {
4
            dp[j][k] = Math.max(dp[j][k], dp[j - w[i]][k - v[i]] + val[i]);
5
        }
6
    }
7
}

例题：AcWing 8. 二维费用的背包问题 #

代码实现：

1
import java.util.Scanner;
2

3
public class TwoDimensionalKnapsack {
4
    static final int MAXN = 105;
5
    static int n, W, V;
6
    static int[] w = new int[MAXN];
7
    static int[] v = new int[MAXN];
8
    static int[] val = new int[MAXN];
9
    static int[][] dp = new int[MAXN][MAXN];
10

11
    public static void main(String[] args) {
12
        Scanner sc = new Scanner(System.in);
13
        n = sc.nextInt();
14
        W = sc.nextInt();
15
        V = sc.nextInt();
16

17
        for (int i = 1; i <= n; i++) {
18
            w[i] = sc.nextInt();
19
            v[i] = sc.nextInt();
20
            val[i] = sc.nextInt();
21
        }
22

23
        for (int i = 1; i <= n; i++) {
24
            for (int j = W; j >= w[i]; j--) {
25
                for (int k = V; k >= v[i]; k--) {
26
                    dp[j][k] = Math.max(dp[j][k], dp[j - w[i]][k - v[i]] + val[i]);
27
                }
28
            }
29
        }
30

31
        System.out.println(dp[W][V]);
32
        sc.close();
33
    }
34
}

七、背包问题变种#

1. 求方案数#

在普通背包的基础上，统计有多少种方案可以达到最大价值。

状态定义：

dp[j]：容量为 j 的最大价值
cnt[j]：达到最大价值的方案数

转移方程：

1
if (dp[j - w[i]] + v[i] > dp[j]) {
2
    dp[j] = dp[j - w[i]] + v[i];
3
    cnt[j] = cnt[j - w[i]];
4
} else if (dp[j - w[i]] + v[i] == dp[j]) {
5
    cnt[j] += cnt[j - w[i]];
6
}

2. 求具体方案#

使用二维数组 dp[i][j] 记录状态，然后倒推出选了哪些物品。

1
// 倒推方案
2
List<Integer> path = new ArrayList<>();
3
int j = V;
4
for (int i = n; i >= 1; i--) {
5
    if (dp[i][j] == dp[i-1][j - w[i]] + v[i]) {
6
        path.add(i);
7
        j -= w[i];
8
    }
9
}

3. 恰好装满背包#

初始化时，dp[0] = 0，其他 dp[j] = -∞（表示不可达状态）。

1
Arrays.fill(dp, Integer.MIN_VALUE / 2);
2
dp[0] = 0;

4. 求第 k 优解#

维护每个状态的前 k 个最优值。

八、经典例题汇总#

题目	类型	链接
AcWing 2. 01背包问题	01背包	链接
AcWing 3. 完全背包问题	完全背包	链接
AcWing 4. 多重背包问题 I	多重背包	链接
AcWing 5. 多重背包问题 II	多重背包（二进制优化）	链接
AcWing 9. 分组背包问题	分组背包	链接
AcWing 8. 二维费用的背包问题	二维背包	链接
LeetCode 416. 分割等和子集	01背包变种	链接
LeetCode 322. 零钱兑换	完全背包变种	链接
LeetCode 518. 零钱兑换 II	完全背包（方案数）	链接

九、总结对比#

核心差异对比表#

背包类型	特点	内层循环方向	时间复杂度
01 背包	每件物品最多选一次	逆序（V → 0）	O(NV)
完全背包	每件物品无限次	正序（0 → V）	O(NV)
多重背包	每件物品最多 s 次	逆序 + 二进制优化	O(V·Σlog(s))
分组背包	每组最多选一件	逆序	O(N·V·S)
混合背包	混合多种类型	根据类型决定	-
二维费用	两个维度限制	双重逆序	O(N·W·V)

决策流程图#

flowchart TD Start[开始] --> Q1{每件物品可用多少次?} Q1 -->|最多1次| A[01背包] Q1 -->|无限次| B[完全背包] Q1 -->|有限制s次| C[多重背包] Q1 -->|组内互斥| D{是否分组?} D -->|是| E[分组背包] Q1 -->|混合类型| F[混合背包] Q1 -->|多维限制| G{几个维度?} G -->|2个| H[二维费用背包] A --> End[选择对应模板] B --> End C --> End E --> End F --> End H --> End style A fill:#e1f5ff style B fill:#fff4e1 style C fill:#ffe1f5 style E fill:#e1ffe1 style F fill:#f5e1ff style H fill:#ffe1e1

十、刷题建议#

基础阶段：先刷 AcWing 的背包九讲，掌握基本模板
进阶阶段：LeetCode 上的背包变种题，理解状态转移的本质
综合应用：Codeforces、AtCoder 等平台的动态规划题

背包问题的核心是理解状态定义和状态转移方程，熟练掌握后可以轻松应对各种变种！

参考资料：

如果觉得本文有帮助，欢迎分享给更多的朋友！

Lovely firefly!

背包问题完全指南

背包问题完全指南#

背包问题分类体系#

一、01 背包问题#

问题描述#

决策树图解#

状态定义#

状态转移方程#

空间优化（一维数组）#

01 背包遍历方向图解#

例题：AcWing 2. 01背包问题#

二、完全背包问题#

问题描述#

状态转移方程#

空间优化（一维数组）#

完全背包遍历方向图解#

例题：AcWing 3. 完全背包问题#

三、多重背包问题#

问题描述#

朴素解法（三重循环）#

二进制优化#

二进制拆分图解#

例题：AcWing 4. 多重背包问题 I#

四、分组背包问题#

问题描述#

分组背包图解#

状态转移方程#

空间优化（一维数组）#

例题：AcWing 9. 分组背包问题#

五、混合背包问题#

问题描述#

解法#

六、二维费用背包#

问题描述#

状态定义#

空间优化（二维数组）#

例题：AcWing 8. 二维费用的背包问题#

七、背包问题变种#

1. 求方案数#

2. 求具体方案#

3. 恰好装满背包#

4. 求第 k 优解#

八、经典例题汇总#

九、总结对比#

核心差异对比表#

决策流程图#

十、刷题建议#

支持与分享

目录

例题：AcWing 2. 01背包问题 #

例题：AcWing 3. 完全背包问题 #

例题：AcWing 4. 多重背包问题 I #

例题：AcWing 9. 分组背包问题 #

例题：AcWing 8. 二维费用的背包问题 #