背包 DP

概念讲解

背包问题分类

类型 特点
0-1 背包 每个物品只能选一次
完全背包 每个物品可以选无限次
多重背包 每个物品有数量限制
分组背包 物品分组，每组选一个

0-1 背包

问题

n 个物品，容量 W，每个物品有重量 w[i] 和价值 v[i]，求最大价值。

代码

123456int dp[W+1];
for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {  // 逆序
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

时间复杂度：O(nW)O(nW)

完全背包

123456int dp[W+1];
for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= W; j++) {  // 正序
        dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
    }
}

多重背包

12345678int dp[W+1];
for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        for (int k = 1; k <= s[i] && k*w[i] <= j; k++) {
            dp[j] = max(dp[j], dp[j-k*w[i]] + k*v[i]);
        }
    }
}

考点分析

初赛考查方式

  1. 程序阅读： 背包程序
  2. 编程题： 背包应用

常见考点

  • 0-1 背包
  • 完全背包
  • 遍历顺序

例题精讲

例题 1：0-1 背包

题目： 3 个物品，容量 5，重量 {2,3,4}，价值 {3,4,5}。

解答：

选物品 1 和 2，重量 5，价值 7。

练习题

  1. 0-1 背包和完全背包的区别是什么？
查看答案
特性 0-1 背包 完全背包
物品选择 每个物品只能选一次 每个物品可以选无限次
遍历顺序 逆序 正序
状态转移 dp[j] = max(dp[j], dp[j-w] + v) dp[j] = max(dp[j], dp[j-w] + v)
  1. 为什么 0-1 背包要逆序遍历？
查看答案

逆序遍历保证每个物品只被选一次。

如果正序遍历：

  • dp[j-w] 可能已经包含了当前物品
  • 会导致同一个物品被选多次
  1. 多重背包的时间复杂度是多少？
查看答案

O(n⋅W⋅s)O(n \cdot W \cdot s)

  • n 是物品数量
  • W 是背包容量
  • s 是每个物品的最大数量

可以二进制优化到 O(n⋅W⋅log⁡s)O(n \cdot W \cdot \log s)

易错点

⚠️ 注意：

  1. 0-1 背包逆序，完全背包正序
  2. 注意初始化
  3. 多重背包可以二进制优化
  4. 分组背包要注意遍历顺序